How can I heapify a heapq in O(lgn)? [duplicate]

This question already has answers here: Closed 12 years ago.

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.

---

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.