Algorithms in a Nutshell

Heap Sort

We always need at least n−1 comparisons to find the largest element in an array A[0,n), but we want to minimize the number of elements that are compared directly to it. In sports, tournaments are used to find the "best" team from a field of n teams without forcing the ultimate winner to play all other n−1 teams. One of the most popular basketball events in the United States is the NCAA championship tournament, where essentially a set of 64 college teams compete for the championship title.^[11] The ultimate champion team plays five teams before reaching the final determining game, and so that team must win six games. It is no coincidence that 6=log (64). Heap Sort shows how to apply this behavior to sort a set of elements; its pseudocode description is shown in Figure 4-14.

Figure 4-14. Heap Sort fact sheet

A heap is a binary tree whose structure ensures two properties:

Shape property

A leaf node at depth k>0 can exist only if all 2^k−1 nodes at depth k−1 exist. Additionally, nodes at a partially filled level must be added "from left to right."

Heap property

Each node in the tree contains a value greater than or equal to either of its two children, if it has any.

The sample heap labeled (a) in Figure 4-15 satisfies these properties. The root of the binary tree must contain the largest element in the tree; however, note that the smallest element can be any of the leaf nodes. Although the ordering information in the binary tree is limited to the fact that a node is greater than either of its children, Heap Sort shows how to take advantage of the shape property to efficiently sort an array of elements.

Figure 4-15. (a) Sample heap of 16 unique elements; (b) labels of these elements; (c) heap stored in an array

Given the rigid structure imposed by the shape property, a heap can be stored in an array A without losing any of its structural information. Illustration (b) in Figure 4-15 shows an integer label assigned to each node in the heap. The root is labeled 0. For a node with label i, its left child (should it exist) is labeled 2*i+1; its right child (should it exist) is labeled 2*i+2. Similarly, for a non-root node labeled i, its parent node is labeled ⌊(i-1)/2⌋. Using this labeling scheme, we can store the heap in an array by storing the element value for a node in the array position identified by the node's label. The array shown in illustration (c) in Figure 4-15 represents the heap shown in that figure. The order of the elements within A can be simply read from left to right as deeper levels of the tree are explored.

Heap Sort sorts an array by first converting that array "in place" into a heap. Indeed, the heap shown in Figure 4-15 results by executing buildHeap (whose pseudocode is shown in Figure 4-14) on an already sorted array. The progress of buildHeap is shown in Figure 4-16. Each numbered row in this figure shows the result of executing heapify on the initial array from the midway point of ⌊n/2⌋−1 down to the leftmost index 0. heapify (A, i, n) updates A to ensure that element A[i] is swapped with the larger of its two children, A[2*i+1] and A[2*i+2], should either one be larger than A[i]. If the swap occurs, heapify recursively checks the grandchildren (and so on) to properly maintain the Heap property for A. As you can see, large numbers are eventually "lifted up" in the resulting heap (which means they are swapped in A with smaller elements to the left). The grayed squares in Figure 4-16 depict the elements swapped in line 9 of heapify.

Figure 4-16. buildHeap operating on an initially sorted array

Heap Sort sorts an array A of size n by treating it as two distinct subarrays, A[0,m) and A[m, n), which represent a heap of size m and a sorted subarray of n-m elements, respectively. As i iterates from n−1 down to 1, Heap Sort grows the sorted subarray A[i, n) downward by swapping the largest element in the heap (at position A[0]) with A[i] (line 3 of sort in Figure 4-14); it then reconstructs A[0,i) to be a valid heap by executing heapify (whose pseudocode is shown in Figure 4-14). The resulting non-empty subarray A[i, n) will be sorted because the largest element in the heap represented in A[0,i) is guaranteed to be smaller than any element in the sorted subarray A[i, n).

Context

Heap Sort is not a stable sort. Because it moves elements around quite frequently, it should not be used for value-based data.

Forces

Heap Sort avoids many of the nasty (almost embarrassing!) cases that cause Quicksort to perform badly. Nonetheless, in the average case Quicksort outperforms Heap Sort.

Solution

A sample implementation in C is shown in Example 4-9.

Example 4-9. Heap Sort implementation in C

static void heapify (void **ar, int(*cmp)(const void *,const void *),
                     int idx, int max) {
  int left = 2*idx + 1;
  int right = 2*idx + 2;
  int largest;

  /* Find largest element of A[idx], A[left], and A[right]. *
  if (left < max && cmp (ar[left], ar[idx]) > 0) {
    largest = left;
  } else {
    largest = idx;
  }

  if (right < max && cmp(ar[right], ar[largest]) > 0) {
    largest = right;
  }

  /* If largest is not already the parent then swap and propagate. */
  if (largest != idx) {
     void *tmp;
     tmp = ar[idx];

ar[idx] = ar[largest];
     ar[largest] = tmp;

     heapify(ar, cmp, largest, max);
   }
}

static void buildHeap (void **ar,
                       int(*cmp)(const void *,const void *), int n) {
  int i;
  for (i = n/2-1; i>=0; i--) {
    heapify (ar, cmp, i, n);
  }
}

void sortPointers (void **ar, int n,
                   int(*cmp)(const void *,const void *)) {
  int i;
  buildHeap (ar, cmp, n);
  for (i = n-1; i >= 1; i--) {
   void *tmp;
   tmp = ar[0];
   ar[0] = ar[i];
   ar[i] = tmp;

   heapify (ar, cmp, 0, i);
  }
}

Heap Sort succeeds because of the heapify function. It is used in two distinct places, although it serves the same purpose each time.

Analysis

heapify is the central operation in Heap Sort. In buildHeap, it is called ⌊ n/2⌋ −1 times, and during the actual sort it is called n−1 times, for a total of ⌊3*n/2⌋ −2 times. As you can see, it is a recursive operation that executes a fixed number of computations until the end of the heap is reached. Because of the shape property, the depth of the heap will always be ⌊log n⌋, where n is the number of elements in the heap. The resulting performance, therefore, is bounded by (⌊3*n/2⌋−2)*⌊log n⌋, which is O(n log n).

Variations

Non-recursive Heap Sort implementations are available, and Table 4-4 presents a benchmark comparison on running 1,000 randomized trials of both implementations, discarding the best and worst performances of each. The average of the remaining runs is shown for both implementations.

Table 4-4. Performance comparison of non-recursive variation (in seconds)

n	Non-recursive Heap Sort	Recursive Heap Sort
16,384	0.0118	0.0112
32,768	0.0328	0.0323
65,536	0.0922	0.0945
131,072	0.2419	0.2508
262,144	0.5652	0.6117
524,288	1.0611	1.1413
1,048,576	2.0867	2.2669
2,097,152	4.9065	5.3249

---

^[11] Actually, there are 65 teams, with a "buy-in" game to eliminate one team at the start of the tournament.