In this week we will study the HeapSort algorithm.  Your assignment is to thoroughly understand what a heap is, how HeapSort works, and specifically the attached code in preparation for a quiz on HeapSort on Friday Mar-16.

Good luck.

DK

///////////////////////////////////////////////////////
///////////////////////////////////////////////////////
//////  Heap Accessors (parent, leftChild, rightChild)
///////////////////////////////////////////////////////
///////////////////////////////////////////////////////

// These simple functions provide the accessors which
// allow us to view a vector as though it is a binary tree.

int getParentIndex(int index)     { return (index - 1) / 2; }
int getLeftChildIndex(int index)  { return (2*index) + 1; }
int getRightChildIndex(int index) { return (2*index) + 2; }

///////////////////////////////////////////////////////
///////////////////////////////////////////////////////
//////  HeapSort
///////////////////////////////////////////////////////
///////////////////////////////////////////////////////

// As noted at the head of this file, this section
// sorts a vector via the heapsort algorithm, which
// places all the elements of vector in-place into a
// heap (addNodesToHeap), then removes then all in
// order (removeNodesFromHeap), leaving a sorted vector.
// This is done in nlogn (hence, optimal) time.

void addNodesToHeap(intVectorByReference v)
{
 int index, parent, cursor, len = v.length();
 for (cursor = 1; cursor < len; cursor++)
 {
  // add the node at v[cursor] to the heap
  // assuming v[0]...v[cursor-1] are already a heap.
  // Do this by percolating the value at v[cursor]
  // up towards the root until it is either the root
  // itself or its parent is >= to it.
  index = cursor;
  while (index > 0)
  {
   parent = getParentIndex(index);
   if (v[parent] >= v[index])
    // it is in the right place now, so break
    break;
   // it is in the wrong place, so swap and keep going up
   swap(v[parent],v[index]);
   index = parent;
  }
 
 }
}

void removeNodesFromHeap(intVectorByReference v)
{
 int cursor, index, leftChild, rightChild, largerChild;
 for (cursor = v.length()-1;cursor > 0; cursor--)
 {
  // swap the node at v[cursor] with the value at
  // the root -- v[0] -- which also is the largest
  // remaining value in the heap.
  swap(v[0],v[cursor]);
 
  // Now we must reestablish the partially-sorted
  // heap property by percolating the root value
  // down through the larger child at each level until
  // it is either a leaf or is larger than both children.
  index = 0;
  while (true)
  {
   // 1. Get left child, and stop if there isn't one
   leftChild = getLeftChildIndex(index);
   if (leftChild >= cursor)
    // if there is no left child, then we have
    // pushed the value down to a leaf and we're done
    break;
 
   // 2. Get the right child, and determine the larger child
   rightChild = getRightChildIndex(index);
   if ((rightChild >= cursor) ||
    (v[leftChild] >= v[rightChild]))
    largerChild = leftChild;
   else
    largerChild = rightChild;
 
   // 3. Stop if the node is >= the larger child
   if (v[index] >= v[largerChild])
    break;
 
   // 4. It's not, so percolate down and keep going
   swap(v[index],v[largerChild]);
   index = largerChild;
  }
 
 }
}

void heapSort(intVectorByReference v)
{
 addNodesToHeap(v);
 removeNodesFromHeap(v);
}