Search code examples
algorithmclrsmax-heap

Deleting a node A[i] from a Max-Heap

CLRS Exercise: 6.5-8

The operation HEAP-DELETE(A,i) deletes the item in node i from heap A. Give an implementation of HEAP-DELETE that runs in O(lg n) time for an n-element max-heap.

enter image description here

I wonder if the algorithm is wrong for the input A[10]={84,22,19,21,3,10,6,5,20}(Index starts with 1) and with A[6]=10 being deleted. Replacing the last node with A[6] would result in violating heap property, overlooking the parent value.

I wrote an algorithm for this and wanted to know if it works right or where am I going wrong ?

HEAP-DELETE(A,i)
  A[i]=A[A.heapsize]
  A.heapsize-=1
  while i>1 and A[parent(i)]<A[i]
    swap A[i] with A[parent(i)]
    i=parent(i);
Solution

  • When deleting a node from a max heap, the first thing we need to do is swap the target element with the last element, then delete the last element.

    Now, we're faced with the problem of fixing the max heap since we just moved an element around. Let's refer to that element that we just moved as x.

    There are three cases:

    • x is greater than its parent
    • x is less than its parent
    • x is equal to its parent

    If x is equal to its parent, that's easy - we do nothing.

    If x is less than its parent, all we need to do is a MAX-HEAPIFY (which I'm assuming you understand how that works from the comments), because we need to fix any mistakes below x.

    If x is greater than its parent, we run into the issue that you've brought up. Handling this isn't too tricky - we just need to compare x to its parent, and if x is greater than the parent, we swap them. Continue this process until x is no longer greater than its parent or we reach the root (when x has no parents).

    With that being said, the pseudocode you've posted looks right to me. Nice work :)