How to implement an indexed Min Heap?

general
,
1

I want to implement an indexed Min Heap so that I don’t have to search an element in order to delete it.
A link of some tutorial will be helpful.

Thank you

1 Like
2

If you want less hassle (and using C++), I would suggest using std::set for that matter.

If you want moderate hassle (and using C++), you can implement a priority queue that can delete elements by indices, in the following manner:

You keep an array, Val[] which will keep the values, and Del[] which will mark the deleted values. Next, take a priority_queue sorted by the following comparator:

bool cmp(int a, int b) {
   return Val[a] > Val[b];
}

When you add a value, you just set Val[ind] = value and push ind in the queue.

When you delete a value, you just “lazily” set Del[i] = 1. Then, to get the min, you do the following:

int getMin() {
   while(Del[pq.top()])
      pq.pop();
   return Val[pq.top()];
}

The following method is still amortized O(log(n)) per deletion, although it can be O(1) at times.

If you want a lot of hassle, you can implement the heap manually, and use the following “trick”:

Keep a Pos[] array, which will track the positions of each index in the queue.

  1. The insert method should return an int to the position in the heap, which will be kept in the Pos array.
  2. Each time you swap two elements, you swap the corresponding positions in the Pos[] array (e.g when you swap Heap[node] with Heap[node x 2] you swap Pos[Heap[node]] with Pos[Heap[node x 2]].

This is the easiest way on top of my head. I only implemented it once and it didn’t take much effort, although I suggest the second method if you want a balance of speed / lines of code. Good luck on your implementation :).

1 Like
3

I can’t understand what Pos[] array stores. “Keep a Pos[] array, which will track the positions of each index in the queue.” Does it store where each index of our original given array is, in the heap array? And in your second point you wrote “Pos[Heap[node]]”, it seems that Pos[] array stores where each “value”, from the given array, is in the heap array, because heap[node] is only a value from our given array. If it is the former, how do I know the index that I want to delete? I only know the value to delete. If latter, values are very large(10^9), so not feasible! Please clarify. Thank you.

4

I am sorry I am too late to answer your question.

To clarify:

In the Heap array you keep a heap array of indices (so the values of the Heap array are between 1 - number_of_insertions)

In the Val array you keep the actual values inserted, in the order they are inserted: Val[1] -> first inserted value, and so on.

The Heap array will keep its “heap” invariant by using the comparator cmp (see above).

The Pos array will have the following meaning: Pos[i] -> the index in the Heap array where the i-th inserted element is.

To find out the position in the heap of i-th inserted element, you access Pos[i]. Every time you swap Heap[i] with Heap[j] in your heapup / heapdown operations, you will have to swap Pos[Heap[i]] with Pos[Heap[j]] (because effectively elements with indices Heap[i] and Heap[j] swapped positions).

1 Like
5

Thanks man!