7.2: Removing the Extreme Value

Last updated
Save as PDF

Page ID: 49311

Wikibooks - Data Structures
Wikipedia

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

To remove the minimum element, we must adjust the heap to fill heap.array[1]. This process is called percolation. Basically, we move the hole from node i to either node 2i or 2i+1. If we pick the minimum of these two, the heap invariant will be maintained; suppose array[2i] < array[2i+1]. Then array[2i] will be moved to array[i], leaving a hole at 2i, but after the move array[i] < array[2i+1], so the heap invariant is maintained. In some cases, 2i+1 will exceed the array bounds, and we are forced to percolate 2i. In other cases, 2i is also outside the bounds: in that case, we are done.

Therefore, here is the remove algorithm for min heap:

#define LEFT(i) (2*i)

#define RIGHT(i) (2*i + 1)

REMOVE_MIN(heap)
{  
    savemin=arr[1];
    arr[1]=arr[--heapsize];
    i=1;
    while(i<heapsize){
        minidx=i;
        if(LEFT(i)<heapsize && arr[LEFT(i)] < arr[minidx])
            minidx=LEFT(i);
        if(RIGHT(i)<heapsize && arr[RIGHT(i)] < arr[minidx]) 
            minidx=RIGHT(i);
        if(minidx!=i){
            swap(arr[i],arr[minidx]);
            i=minidx;            
        }
        else 
            break;
    }
}

Why does this work?

   If there is only 1 element, heapsize becomes 0, nothing in the array is valid.
   If there are 2 elements, one min and other max, you replace min with max.
   If there are 3 or more elements say n, you replace 0th element with n-1th element. 
   The heap property is destroyed. Choose the 2 children of root and check which is the minimum.
   Choose the minimum between them, swap it. Now subtree with swapped child is loose heap property.
   If no violations break.