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?

Community · Accepted Answer · 2017-05-23 12:16:18Z

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, 2017 at 12:16

CommunityBot

11 silver badge

answered Jul 10, 2016 at 20:56

Leon

32.8k4 gold badges77 silver badges102 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

enaJ Over a year ago

Thanks for your inputs! what is the purpose of accessing the smallest key?

Leon Over a year ago

@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?

enaJ Over a year ago

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.

Leon Over a year ago

@enaJ And how does the min-heap assist in that?

enaJ Over a year ago

I want to be able to change any certain item in a heap. Not necessarily the smallest one

|

Collectives™ on Stack Overflow

Python - hash heap implementation

1 Answer 1

10 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related