CMPT 225: Basic Heap Algorithms


Abstract Versions

/* Abstract heap extract-min() */
// removes and returns the min (root) element on the heap.
extract_min(){

    k <- key of the root;
    replace the root node with the ``right-most'' leaf at the deapest level;

    // Restore the order invariant with a trickle_down from the root.
    v <- root; 
    while((v is not a leaf) AND (v has a child with a key smaller than key(v))){
        let c be the child of v with the smallest key 
        swap the keys of v and c
        v <- c  
    }
    return k
}
/* Abstract heap insert(k) */
// inserts key k into heap.
insert(k){

    add a new node with key k at the "bottom right";

    // Restore the order invariant with a trickle_up from the new node.
    v <- the newly added leaf ;
    while((v is not root) AND ( key(parent(v)) > key(v)){
        swap the keys of v and parent(v);
        v <- parent(v);
    }
}

Pseudo-code for array-based heap

extract_min(){
// Assumes heap implemented in array A, with root at A[0], and n elements.
// This version uses the "trick" of avoiding checking for existence of children 
// during trickle down by setting A[i] to "infinity" for i >= n. 
// This requies we have an array of size at least 2n+1, and also a value 
// that is largr than any value that will be on the heap to use as "infinity".
    temp <- A[0] ;
    n <- n-1 ;
    A[0] <- A[n] ;
    A[n] <- infinity ;
    // trickle down from the root
    i <- 0 ;
    while( A[i] > A[2i+1] OR A[i] > A[2i+2] ){
       if( A[2i+1] < A[2i+2] ){  
         swap A[i] and A[2i+1]
         i <- 2i+1 
       }else{
         swap A[i] and A[2i+2]
         i <- 2i+2 
      }
    } 
    return temp 
}
insert(k){
// Assumes heap implemented in array A, with root at A[0], and n elements.
    A[n] <- k ;
    // trickle_up (from the new leaf)
    i <- n ;
    while( i > 0 AND A[i] < A[(i-1)/2] ){
       swap A[i] and A[(i-1)/2] ;
       i <- (i-1)/2 ;
    }
    n <- n+1 ;
}

Efficiently transforming an array of elements into a heap

MakeHeap( A, n ){
// A is an array (of size at least n), n is the size of the heap we are making;
// The root will be at A[0]; the last element at A[n-1].
    for( i = floor(n/2)-1 down to 0 ){
       TrickleDown( A, n, i )
    }
}
 

TrickleDown( A, n, i ){
// A is an array, n the size of the heap we are making.
// Performs a trickle-down from the node A[i].
// This version of trickle-down is recursive, and explicitly checks 
// for existence of children.
    swap <- 2i+1 // index of left child of i, if it exists
    if ( 2i+1 < n ){
       // i has a left child, so there is something to do
       if( 2i+2 < n && A[2i+2] < A[2i+1] ){
          // i is has a right child, and its key is smaller than the key of the left child,
          swap <- 2i+2 
       }
       // here, swap is the child of i with the smaller key
       if( A[i] > A[swap] ){
          // if the child has a smaller key than i, swap them and continue.
          swap A[i] with A[swap]
          trickleDown( A, n, swap )
       }
    }
}        

TrickleDown( A, n, i ){
// An alternate version of trickleDown.
// It may be simpler, but makes more unnecessary comparisons.
    swap <- 0
    left <- 2i+1 
    if( left < n && A[left] < A[i] )
       swap <- left ;
    }
    right <- 2i+2 ;
    if( right < n && A[right] < A[left] ){
       swap <- right ; 
    }
    if( swap > 0 ){
       swap A[i] and A[swap] ;
       trickleDown( A, n, swap )
    }
}