Heaps and Heapsort

Here are details about heaps and the heapsort algorithm.

1. A heap is an object with the properties:
   • the heap has n elements and resides in an array A, with indexes from 1 to n inclusive. (Normally one doesn't use the element A[0], but saves for other purposes. We will not show that here.)

   • There is also a value heapsize(A), which is <= n. (This says that only array elements up to and including heapsize(A) are regarded as part of the heap.)

   • One regards this array as a complete binary tree (all links filled in up to the end), where A[1] is the root. In this case, for any node i,
     1. Parent(i) = floor(i/2)
     2. LeftChild(i) = 2*i
     3. RightChild(i) = 2*i + 1

   • A heap must have the heap property:

        
     A[Parent(i)] >= A[i], for every node i except the root,
     where 1 < i && i <= heapsize.
     

2. Restoring the heap property, if violated at node i:

   
   MaxHeapify(A, i)
      l = LeftChild(i)
      r = RightChild(i)
      if (l <= heapsize(A) && A[l] > A[i]) largest = l
                                      else largest = i
      if (r <= heapsize(A) && A[r] > A[largest]) largest = r
      if (largest != i) {
          exchange(A[i], A[largest])
          MaxHeapify(A, largest)
      }
   

3. Building a heap, starting with array A[1], ..., A[n] and heapsize(A) == n.

   
   BuildMaxHeap(A)
      heapsize(A) = n
      for (i = floor(n/2); i >= 1; i--)
         MaxHeapify(A, i)
   

4. Heapsort algorithm, starting with array A[1], ..., A[n]

   
   Heapsort(A)
      BuildMaxHeap(A)
      for (i = n; i >= 2; i--) {
         exchange(A[1], A[i])
         heapsize(A)--
         MaxHeapify(A, 1)
      }
   

1. Start with an array A holding n priority numbers in locations A[1], ..., A[n].
2. Use BuildMaxHeap(A) to turn A into a heap.
3. Repeatedly remove the largest remaining element from A, using the following, which is about the same as one step of the heapsort algorithm:

   
   HeapExtractMax(A)
      if (heapsize(A) < 1)
         error("Heap underflow")
      max = A[1]
      A[1] = A[heapsize(A)]
      heapsize(A)--
      MaxHeapify(A, 1)
      return max
   

4. Another useful algorithm lets us increase a value in the array and restore the heap property:

   
   HeapIncreaseKey(A, i, key)
      if (key < A[i])
         error("New key smaller than old")
      A[i] = key
      while (i > 1 && A[Parent(i)] < A[i]) {
         exchange(A[i], A[Parent(i)])
         i = Parent(i)
      }
   

5. Finally, we can insert a new element into the array:

   
   MaxHeapInsert(A, key)
      heapsize(A)++
      A[heapsize(A)] = -infinity
      HeapIncreaseKey(A, heapsize(A), key)
   

• Building a heap from an array in random order: Building a heap.
• Running heapsort from an array in random order: Heapsort.
• Repeatedly extracting the maximum from a heap: Extract Maximum.
• Repeatedly inserting a new element into a heap: Inserting Into a Heap.