How to delete in a heap data structure?

Question

I understand how to delete the root node from a max heap but is the procedure for deleting a node from the middle to remove and replace the root repeatedly until the desired node is deleted?

1. Is O(log n) the optimal complexity for this procedure?

2. Does this affect the big O complexity since other nodes must be deleted in order to delete a specific node?

Answer 1

Actually, you can remove an item from the middle of a heap without trouble.

The idea is to take the last item in the heap and, starting from the current position (i.e. the position that held the item you deleted), sift it up if the new item is greater than the parent of the old item. If it's not greater than the parent, then sift it down.

That's the procedure for a max heap. For a min heap, of course, you'd reverse the greater and less cases.

Finding an item in a heap is an O(n) operation, but if you already know where it is in the heap, removing it is O(log n).

I published a heap-based priority queue for DevSource a few years back. The full source is at http://www.mischel.com/pubs/priqueue.zip

Update

Several have asked if it's possible to move up after moving the last node in the heap to replace the deleted node. Consider this heap:

        1     6       2   7   8   3 

If you delete the node with value 7, the value 3 replaces it:

        1     6       2   3   8 

You now have to move it up to make a valid heap:

        1     3       2   6   8 

The key here is that if the item you're replacing is in a different subtree than the last item in the heap, it's possible that the replacement node will be smaller than the parent of the replaced node.

Answer 2

The problem with removing an arbitrary element from a heap is that you cannot find it.

In a heap, looking for an arbitrary element is O(n), thus removing an element [if given by value] is O(n) as well.

If it is important for you to remove arbitrary elements form the data structure, a heap is probably not the best choice, you should consider full sorted data structurs instead such as balanced BST or a skip list.

If your element is given by reference, it is however possible to remove it in O(logn) by simply 'replacing' it with the last leaf [remember a heap is implemented as a complete binary tree, so there is a last leaf, and you know exactly where it is], remove these element, and re-heapify the relevant sub heap.