How to implement O(1) deletion on min-heap with hashtable

Question

Read the following statement somewhere:

An additional hash table can be used to make deletion fast in min-heap.

Question> How to combine priority_queue and unordered_map so that I can implement the idea above?

#include <queue>
#include <unordered_map>
#include <iostream>
#include <list>
using namespace std;

struct Age
{
  Age(int age) : m_age(age) {}
  int m_age;  
};

// Hash function for Age
class HashAge {
  public:
   const size_t operator()(const Age &a) const {
     return hash<int>()(a.m_age);
   }
};

struct AgeGreater
{
  bool operator()(const Age& lhs, const Age& rhs) const {
    return lhs.m_age < rhs.m_age;
  }
};

int main()
{
  priority_queue<Age, list<Age>, AgeGreater> min_heap;          // doesn't work
  //priority_queue<Age, vector<Age>, AgeGreater> min_heap;

  // Is this the right way to do it?
  unordered_map<Age, list<Age>::iterator, HashAge > hashTable;     
}

Question> I am not able to make the following work:

priority_queue<Age, list<Age>, AgeGreater> min_heap;          // doesn't work

I have to use list as the container b/c the iterators of list is not affected by insertion/deletion (Iterator invalidation rules)

I guess I'm wondering why you're using a priority queue to implement a min-heap, since I'm used to it being the other way around. — Dennis Meng, Aug 21 '13 at 17:21
"An additional hash table can be used to make deletion fast in min-heap." While that may or may not be true, the statement is NOT referring to `priority_queue` and `unordered_map` specifically, and I would seriously doubt they can be used together in any effective way, much less in the way the comment discusses. — Mooing Duck, Aug 21 '13 at 17:33
You are right and the book doesn't mention priority_queue or unordered_map. Here, I just want to implement the idea in c++ based on the idea. — q0987, Aug 21 '13 at 17:39

Nathan S. · Answer 1 · 2013-08-21T18:41:34.463

You can't do this with the supplied priority_queue data structure:

In a priority queue you don't know where the elements are stored, so it is hard to delete them in constant time, because you can't find the elements. But, if you maintain a hash table with the location of every element in the priority queue stored in the hash table, then you can find and remove an item quickly, although I would expect log(N) time in the worst case, not constant time. (I don't recall offhand if you get amortized constant time.)

To do this you usually need to roll your own data structures, because you have to update the hash table each time an item is moved around in the priority queue.

I have some example code that does this here:

http://code.google.com/p/hog2/source/browse/trunk/algorithms/AStarOpenClosed.h

It's based on older coding styles, but it does the job.

To illustrate:

/**
 * Moves a node up the heap. Returns true if the node was moved, false otherwise.
 */
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;
}

Inside the if statement we do the normal heapify operations on the heap and then update the location in the hash table (openLocation) to point to the current location in the priority queue.

You get amortized constant with the hash table, but the priority queue can't do better than `log n` without tearing up the implementation of said priority queue — Dennis Meng, Aug 21 '13 at 17:34
... and with that probably destroying the performance of other operations (eg: insert).. — Karoly Horvath, Aug 21 '13 at 17:35
... and for most of those variants that claim O(1) for insert (or delete), it comes with a *huge* constant factor that makes the real world performance worse than with a simple binary heap. — Jim Mischel, Aug 21 '13 at 19:46

How to implement O(1) deletion on min-heap with hashtable

1 Answers1

Linked