//-----------------------------------------------------------------------------
The Max-Heap Data Structure
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
Array Attributes:
   length[A]
   heapSize[A]
Helper Functions:
   parent(i) = floor(i/2)   // for i>=2
   left(i) = 2i
   right(i) = 2i+1
Max Heap Property:
   A[parent(i)] >= A[i]     // for 2<=i<=heapSize[A]
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
Heapify(A, i)  pre: subtrees at left(i) and right(i) are valid heaps
   l = left(i)
   r = right(i)
   if l<=heapSize[A] and A[l]>A[i]
      largest = l
   else
      largest = i
   if r<=heapSize[A] and A[r]>A[largest]
      largest = r
   if largest != i
      A[i] <--> A[largest]  // swap
      Heapify(A, largest)
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
BuildHeap(A)
   n = heapSize[A] = length[A]
   for i=floor(n/2) down to 1
      Heapify(A, i)
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
HeapSort(A)
   BuildHeap(A)
   n = length[A]
   for i=n down to 2
      A[1] <--> A[i]  // swap
      heapSize[A]--
      Heapify(A, 1)
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
Priority Queue Algorithms
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
HeapMaximum(A)  pre: heapSize[A]>=1
   return A[1]
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
HeapDeleteMax(A)  pre: heapSize[A]>=1
   A[1] <--> A[heapSize[A]]   // swap
   heapSize[A]--
   Heapify(A, 1)
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
HeapExtractMax(A)  pre: heapSize[A]>=1
   max = A[1]
   HeapDeleteMax(A)
   return max
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
HeapIncreaseKey(A, i, k)  pre: 1<=i<=heapSize[A]
   if k>A[i]
      A[i] = k
      while i>=2 and A[parent(i)]<A[i]
         A[i] <--> A[parent(i)]   // swap
         i = parent(i)
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
HeapInsert(A, k)   pre: heapSize[A]<length[A]
   heapSize[A]++
   A[heapSize[A]] = -inf
   HeapIncreaseKey(A, heapSize[A], k)
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
Exercise:
Re-write all of these algorithms for a Min Heap and Min Priority Queue
//-----------------------------------------------------------------------------