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