Heap Sort

Max Heap

A max heap is a binary tree that has heap shape and the value contained at each node is greater than or equal to the values contained in its children. Just like heaps, any subtree of a max heap is also a heap.

Question: What can you say about the value contained at the root of a max heap?

Heap Sort

start: An array, a, whose indices 1 to N are filled with data values.

Reminder: This array is already a heap. The root is a[1].

  int n = N;
  //Initial build of Max Heap from bottom up
  for(i= N/2; i>0; i--)
    siftDown(i,n);
  //
  do {
    swap(1,n);      //move biggest in heap to the end; move value of a[n] to root
    n--;            //heap is now one smaller; 
    siftDown(1,n);  //now its a max heap
  } while(n>1);

Function siftDown

context: An array, a, whose indices 1 to N are filled with data values. This array is already a heap.

void siftDown(int i, int n) //expects: two plug-in values: 
                                // i, a node specified by its index in the array,
                                // and n, the index of the last item in the heap.
                            //expects: that the left and right subtrees of node i 
                                // are either empty or are already max heaps

                            //process: the function will swap values within the
                                // the subtree based at i.
                            // result: subtree based at i is now a max heap

void siftDown(int i, int n) {
  int lc;
  while (lc = bigChildExists(i,n)) {
    swap(lc,i);
    i = lc;
  }
}

Function bigChildExists

int bigChildExists(int i, int n)  // i,n as above
                                  // returns 0 if no child of i has value larger than a[i]
                                  // otherwise returns the index of the largest child