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

What led me to develop this solution (which I'm not 100% sure is correct) is the fact that I've actually found a solution to delete any node in a min-max heap, but it's wrong.

The wrong solution is can be found here (implemented in C++) and here (implemented in Python). I'm going to present the just mentioned wrong Python's solution, which is more accessible to everyone:

The solution is the following:

def DeleteAt(self, position):
    """delete given position"""
    self.heap[position] = self.heap[-1]
    del(self.heap[-1])
    self.TrickleDown(position)

Now, suppose we have the following min-max heap:

level 0                            10                        

level 1                92                       56           

level 2         41          54          23          11     

level 3      69    51    55    65    37    31

as far as I've checked this is a valid min-max heap. Now, suppose we want to delete the element 55, which in an 0-based array would be found at index 9 (if I counted correctly).

What the solution above would do is simply put the last element in the array, in this case 31, and put it at position 9:

level 0                            10                        

level 1                92                       56           

level 2         41          54          23          11     

level 3      69    51    31    65    37    55

it would delete the last element of the array (which is now 55), and the resulting min-max heap would look like this:

level 0                            10                        

level 1                92                       56           

level 2         41          54          23          11     

level 3      69    51    31    65    37 

and finally it would "trickle-down" from the position (i.e. where now we have the number 31).

"tricle-down" would check if we're in an even (or min) or odd (or max) level: we're in an odd level (3), so "trickle-down" would call "trickle-down-max" starting from 31, but since 31 has no children, it stops (check the original paper above if you don't know what I'm talking about).

But if you observe that leaves the data structure in a state that is no more a min-max heap, because 54, which is at even level and therefore should be smaller than its descendants, is greater than 31, one of its descendants.

---

This made me think that we couldn't just look at the children of the node at position, but that we also needed to check from that position upwards, that maybe we needed to use "trickle-up" too.

In the following reasoning, let x be the element at position after we delete the element that we wanted to delete and before any fix operations has run. Let p be its parent (if any).

The idea of my algorithm is really that one, and more specifically is based on the fact that:

1. If x is on a odd level (like in the example above), and we exchange it with its parent p, which is on an even level, that would not break any rules/invariants of the min-max heap from the new x's position downwards.

   • The same reasoning (I think) can be done if the situation would be reversed, i.e., x was originally in a even position and it would be greater than its parent.

   • Now, if you noticed, the only thing that could need a fix is that, if x was exchange with its parent and it's now in a even (and respectively odd) position we may need to check if it's smaller (and respectively greater) than the node at the previous even (and respectively odd) level.

This of course didn't seem to be the whole solution to me, and of course I also wanted to check if the previous parent of x, i.e. p, is in a correct position.

• If p, after the exchange with x, is on a odd (and respectively even) level, it means it could be smaller (and respectively greater) than any of its descendants, because it was previously in a even (and respectively odd) level. So, I thought we needed a "trickle-down" here.

• Regarding the fact if p is in a correct position with respect to its ancestors, I think the reasoning would be similar to the one above (but I'm not 100% sure).

Putting this together I came up with the solution:

function DELETE(H, i):

    // H is the min-max heap array
    // i is the index of the node we want to delete
    // I assume, for simplicity, 
    // it's not out of the bounds of the array

    if i is the last index of H:
        remove and return H[i]
    else:
        l = get_last_index_of(H)

        swap(H, i, l)  

        d = delete(H, l)

        // d is the element we wanted to remove initially
        // and was initially at position i
        // So, at index i we now have what was the last element of H

        push_up(H, i)

        push_down(H, i)

        return d

This seems to work according to an implementation of a min-max heap that I made and that you can find here.

Note also that the solution run in O(log₂ n) time, because we're just calling "push-up" and "push-down" which run in that order.

Answer 2

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).