Here are details about heaps and the heapsort algorithm.

1. A heap is an object with the properties:
   1. 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. (See ( ii ) below for a natural use of A[0].) Even in Java and C, we will start heaps at index 1. It's also possible to create heaps of size n that reside at indexes 0 through n-1. Because of our text, this would be too confusing.)

   2. There is also a value A.heapsize, which is <= n. This says that only array elements up to and including A.heapsize are regarded as part of the heap. One could use the location A[0] as a place to store the heapsize.

      Remark: For a commercial program, one should create the heap data type in Java or C++ as an Abstract Data Type, using a class for the implementation. Java provides a library priority queue based on a heap, and C++ also provides a library priority queue more explicitly based on a heap, and one of these would be an even better choice for a commercial program. In this course we are learning how these types work, and for simplicity might use a "trick" such as storing the heapsize in the 0th array element.

   3. One regards this array as a complete binary tree (all nodes filled in up to the end), where A[1] is the root. In this case, for any node i,

      Parent( i ) = floor( i / 2 ) Left( i ) = 2 * i Right( i ) = 2 * i + 1

      Above, if 2*i > A.heapsize, then there is no left child, and similarly if 2*i + 1 > A.heapsize, then there is no right child.

   4. The elements of A have a linear order to them ( <, >, >=, <=, ==, !=) such as numbers or strings.

   5. A heap must have the heap property:

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

2. Restoring the heap property, if violated at node i: (Takes time O(log(n)).)

   MaxHeapify(A, i) l = Left(i) r = Right(i) if (l <= A.heapsize && A[l] > A[i]) largest = l else largest = i if (r <= A.heapsize && 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 A.heapsize == n. (Surprisingly, takes time O(n), rather than O(n * log(n)) as one might expect.)

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

4. Heapsort algorithm, starting with array A[1], ..., A[n] (Takes time O(n * log(n)).)

   Heapsort(A) BuildMaxHeap(A) for (i = n; i >= 2; i--) exchange(A[1], A[i]) A.heapsize-- 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: (Takes time O(log(n)).)

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

4. Another useful algorithm lets us increase a value in the array and restore the heap property: (Takes time O(log(n)).)

   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: (Takes time O(log(n)).)

   MaxHeapInsert(A, key) A.heapsize++ A[A.heapsize] = -infinity HeapIncreaseKey(A, A.heapsize, 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.