How do I perform a deletion of the kth element on a min-max heap?

Question

A min-max heap can be useful to implement a double-ended priority queue because of its constant time find-min and find-max operations. We can also retrieve the minimum and maximum elements in the min-max heap in O(log₂ n) time. Sometimes, though, we may also want to delete any node in the min-max heap, and this can be done in O(log₂ n) , according to the paper which introduced min-max heaps:

...

The structure can also be generalized to support the operation Find(k) (determine the kth smallest value in the structure) in constant time and the operation Delete(k) (delete the kth smallest value in the structure) in logarithmic time, for any fixed value (or set of values) of k.

...

How exactly do I perform a deletion of the kth element on a min-max heap?

Answer 1

I don't consider myself an "expert" in the fields of algorithms and data structures, but I do have a detailed understanding of binary heaps, including the min-max heap. See, for example, my blog series on binary heaps, starting with http://blog.mischel.com/2013/09/29/a-better-way-to-do-it-the-heap/. I have a min-max implementation that I'll get around to writing about at some point.

Your solution to the problem is correct: you do indeed have to bubble up or sift down to re-adjust the heap when you delete an arbitrary node.

Deleting an arbitrary node in a min-max heap is not fundamentally different from the same operation in a max-heap or min-heap. Consider, for example, deleting an arbitrary node in a min-heap. Start with this min-heap:

      0
  4       1
5   6   2   3

Now if you remove the node 5 you have:

      0
  4       1
    6   2   3

You take the last node in the heap, 3, and put it in the place where 5 was:

      0
  4       1
3   6   2   

In this case you don't have to sift down because it's already a leaf, but it's out of place because it's smaller than its parent. You have to bubble it up to obtain:

      0
  3       1
4   6   2   

The same rules apply for a min-max heap. You replace the element you're removing with the last item from the heap, and decrease the count. Then, you have to check to see if it needs to be bubbled up or sifted down. The only tricky part is that the logic differs depending on whether the item is on a min level or a max level.

In your example, the heap that results from the first operation (replacing 55 with 31) is invalid because 31 is smaller than 54. So you have to bubble it up the heap.

One other thing: removing an arbitrary node is indeed a log₂(n) operation. However, finding the node to delete is an O(n) operation unless you have some other data structure keeping track of where nodes are in the heap. So, in general, removal of an arbitrary node is considered O(n).