How to delete the minimum key in a max heap?

Question

I need to implement a function HEAP-DELETE-MIN(Array) that deletes the lowest integer in a max heap. Im not asking for the function itself, but could someone provide me with some pseudocode to help me get started? It would be a great help. The array should remain a max heap at the end of the function.

Answer 1

Essentially what you will need to do is search through all the leaf nodes of the implicit heap stored in the array. It will be a leaf node of the heap because its parent must be larger than it (max heap property) and we know the leaves are stored from index n/2 and beyond (though this will not hurt our algorithmic complexity). So essentially what you should do is the following:

1) Search the array for the minimum element
2) Place the last-inserted heap element in the position of the minimum element (essentially this is the delete)
3) Upheap the replaced node to restore maximum heap property and correct storage of the heap in the array

This will take O(n) for the search of the minimum element, then O(1) for the switch, and finally O(log n) for the upheap. In total this is linear time, essentially the best you can do.

Remember to be careful with the the index operations, 2*i is the left child of node i and 2*i+1 is the right child of node i in an array based heap (assuming 0th element of the array is always empty and the root of the heap is at index 1)