Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

PriorityQueue's changePriority method works in linear time #83

Open
eush77 opened this issue Aug 2, 2014 · 3 comments
Open

PriorityQueue's changePriority method works in linear time #83

eush77 opened this issue Aug 2, 2014 · 3 comments

Comments

@eush77
Copy link
Contributor

eush77 commented Aug 2, 2014

We can do better, namely in O(log n).

@felipernb
Copy link
Owner

Yeah, it's possible.

But in order to do that without changing the interface we need to add another structure to keep track of the relation: item -> position in the heap and the code can get a little convoluted, but I'll put some thought into it.

@eush77
Copy link
Contributor Author

eush77 commented Aug 3, 2014

I think this can be achieved by overloading _swap to capture swaps (in order to update positions to pass to _siftUp, _siftDown) and changing heap comparator so that it looks up priorities in the PriorityQueue._items rather than in a separate container.

function PriorityQueue(initialItems) {
  MinHeap.call(this, function (a, b) {
    return self._items[a].priority < self._items[b].priority ? -1 : 1;
  });
  /* ... */
}

@ghost
Copy link

ghost commented Jul 12, 2018

@felipernb @eush77 I've made a pull reuest with proposed implementation, can you have a look and check it out. Link : #129

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants