Heap Implementation

[Cem Karan]

On Feb 9, 2016, at 9:27 AM, Mark Lawrence <breamoreboy at yahoo.co.uk> wrote:

> On 09/02/2016 11:44, Cem Karan wrote:
>> 
>> On Feb 9, 2016, at 4:40 AM, Mark Lawrence <breamoreboy at yahoo.co.uk> wrote:
>> 
>>> On 09/02/2016 04:25, Cem Karan wrote:
>>>> 
>>>> No problem, that's what I thought happened.  And you're right, I'm looking for a priority queue (not the only reason to use a heap, but a pretty important reason!)
>>>> 
>>> 
>>> I'm assuming I've missed the explanation, so what is the problem again with https://docs.python.org/3/library/queue.html#queue.PriorityQueue or even https://docs.python.org/3/library/asyncio-queue.html#asyncio.PriorityQueue ?
>> 
>> Efficiently changing the the priority of items already in the queue/deleting items in the queue (not the first item).  This comes up a LOT in event-based simulators where it's easier to tentatively add an event knowing that you might need to delete it or change it later.
>> 
>> Thanks,
>> Cem Karan
>> 
> 
> Thanks for that, but from the sounds of it sooner you than me :)

Eh, its not too bad once you figure out how to do it.  It's easier in C though; you can use pointer tricks that let you find the element in constant time, and then removal will involve figuring out how to fix up your heap after you've removed the element.

Thanks,
Cem Karan