0

Possible Duplicate:
How can I implement decrease-key functionality in Python's heapq?

Hi,

I'm using heapq in Python to implement a priority queue. The items inside the queue get their priorities changed a lot, and when that happens I need to heapify the heapq.
The problem is that heapq only has a heapify function that heapifies the entire heap, rather then heapify that starts off from a certain item inside the heap knowing that the rest is already a well ordered heap (like the classic CS text book heapify).
The difference is significant since each heapify call is O(n) instead of O(lgn). Can it be done without implementing a heap using a standard list?

Thanks!

It seems that my question is a duplicate of How can I implement decrease-key functionality in Python's heapq?
The answer there indicates that there's no way around reimplementing a heap based queue with proper O(lgn) heapify of a specific item.

Community
  • 1
  • 1
Yoav Weiss
  • 2,220
  • 4
  • 17
  • 22
  • Possible duplicate of http://stackoverflow.com/questions/1465662/how-can-i-implement-decrease-key-functionality-in-pythons-heapq – Karl Knechtel Dec 10 '10 at 23:42
  • Yeah, it is close enough (I'm not decrementing, but the principle is the same). I guess I'll reimplement a heap then... – Yoav Weiss Dec 10 '10 at 23:46
  • Or just follow the recommendation Alex Martelli gives at the end of his answer. Voting to close as duplicate. – Sven Marnach Dec 10 '10 at 23:56
  • Since the main heapq functions are all written in C (the python functions are overwritten by C ones from _heapq), it will probably be faster to use the C heapify than to use the Python siftup/siftdown.. Personally, I would be tempted to just use the internal _siftup/_siftdown (which are in C), though I know that it is bad form to do so. – Justin Peel Dec 11 '10 at 03:39

1 Answers1

0

I was able to avoid this particuler issue with heapify by invalidating current heap item (raise a flag inside the item) and push an identical item to the heap (which is O(lgn)).
That may inflate the heap with some invalid items (which I clean at pop()), but avoids reimplementing the heap with heap items aware of their current heap position and a new position based heapify.

Yoav Weiss
  • 2,220
  • 4
  • 17
  • 22