Python - hash heap implementation

Question

I have a stream data coming, and I am maintaining them by pushing them one by one into a heap (priority queue), the resulting heap looks like:

[(a,1), (b,2), (c, 7), (d, 2), ...]

Because I need to update the items (e.g., change (a,1) to (a, 2), or delete (c,7)) continously through out the time. To effciently find and remove an items in a heap, I want to construct a hash table with the location of every items in the heap stored in the hash table.

So that each time I want to update an item, I can use the hashtable to find it and make changes easily in the heap, simutinouly updating the position of every item in the hash table.

The same question has been asked in this post: How to implement O(1) deletion on min-heap with hashtable with c++ code as following:

template<typename state, typename CmpKey, class dataStructure>
bool AStarOpenClosed<state, CmpKey, dataStructure>::HeapifyUp(unsigned int index)
{
        if (index == 0) return false;
        int parent = (index-1)/2;
        CmpKey compare;

        if (compare(elements[theHeap[parent]], elements[theHeap[index]]))
        {
                // Perform normal heap operations
                unsigned int tmp = theHeap[parent];
                theHeap[parent] = theHeap[index];
                theHeap[index] = tmp;
                // Update the element location in the hash table
                elements[theHeap[parent]].openLocation = parent;
                elements[theHeap[index]].openLocation = index;
                HeapifyUp(parent);
                return true;
        }
        return false;
}

I have little experience with c++, wondering if anyone can help me explain the idea or provide a python version code of such an implementation?

score 2 · Answer 1 · edited May 23 '17 at 12:16

2

My understanding is that the first item in your pair serves as the key, and the second item as the data payload. Then I would propose an approach the other way around, somewhat similar to this answer, but simpler.

Let the hashtable be your primary data structure for data storage and the min-heap be an auxiliary data structure for maintaining the current smallest key in your data set.
Insert new item: add the data into both hashtable and min-heap.
Update the value for the given key: update the value in the hashtable only.
Delete the item with the given key: delete the entry with the given key from the hashtable only.
Access the smallest key: if the element at the top of the heap is not found in the hashtable, drop it; repeat, until the top key is present in the hashtable.

edited May 23 '17 at 12:16

Community

1
1

answered Jul 10 '16 at 20:56

Leon

31,443
4
72
97

Thanks for your inputs! what is the purpose of accessing the smallest key? – enaJ Jul 10 '16 at 21:47
@enaJ You should know better. That's the main functionality of min-heap data structure. If you don't need to access the smallest key, why is your question built around min-heap? – Leon Jul 10 '16 at 21:50
The first item in my pair represent a node, the second represent the edges that connect with this nodes. The big picture of this problem is to update a graph with vertex and nodes in a rolling time-window of 1 minute. – enaJ Jul 10 '16 at 21:52
@enaJ And how does the min-heap assist in that? – Leon Jul 10 '16 at 21:53
I want to be able to change any certain item in a heap. Not necessarily the smallest one – enaJ Jul 10 '16 at 21:53
@enaJ Yes, but why on earth are you considering using min-heap at all? Can't you get along with a hashtable alone? – Leon Jul 10 '16 at 21:55
I want to the hash table to assist the heap. So the hash table is auxiliary data structure – enaJ Jul 10 '16 at 21:55
@enaJ Still it is not clear to me what you need the min-heap for. – Leon Jul 10 '16 at 21:56
Because the ultimate goal is to use heap to find the median number of this collection, which it has an advantage in terms of sort than hash table. – enaJ Jul 10 '16 at 21:57
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/116945/discussion-between-leon-and-enaj). – Leon Jul 10 '16 at 21:59

Python - hash heap implementation

1 Answers1