/* 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); } }

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 ; }

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 ) } }