Algorithms Design   |   C language   |   Index

Heapsort

Consider the sorting problem discussed in another chapter. Namely, consider the problem of permuting the elements of an array v[1 .. n] to put them in increasing order. In other words, rearrange the elements of the array so that v[1] ≤ . . . ≤ v[n].

The other chapter analysed some simple algorithms for the problem. The present chapter examines Heapsort, an algorithm discovered by J. W. J. Williams in 1964. Unlike the simple algorithms, Heapsort is linearithmic, even in the worst case.

We shall assume that the indices of the array are  1 .. n ,  rather than the usual 0 .. n-1 .  This convention will make the code a little simpler.

Arrays and binary trees

In order to discuss the Heapsort, we must learn to see the binary tree hidden in any array.  The set of indices of any array  v[1..m]  can be understood as a binary tree in the following way:

• the index 1 is the root of the tree;
• the parent of any index  c  is  c/2  (of course 1 has no parent);
• the left child of um index  p  is  2p  (this child exists only if 2p ≤ m );
• the right child of  p  is  2p+1  (this child exists only if 2p+1 ≤ m ).

To make the binary tree stand out, we can draw the array in layers, so that every child sits in the layer immediately below that of its parent.  The figure below is such a drawing of the array v[1..56]. (The numbers in the boxes are the indices i rather than the values v[i].)  Observe that each layer, except perhaps the last, has twice as many elements as the previous one. It follows that the number of layers in an array v[1..m] is exactly  1 + lg(m),  where lg(m) is the floor of log m.

Exercises 1

Heap

The mechanism behind the Heapsort algorithm is a data structure, known as heap, that sees the array as a binary tree.  There are two flavors of the structure: max-heap and min-heap; we shall consider here only the first flavor and omit the max- prefix.

A heap, then, is an array in which the value of each parent is greater than or equal to the value of each of its two children. More precisely, an array v[1..m] is a  heap  if

v[c/2] ≥ v[c]

for c = 2, . . . , m .  Here, as in the rest of this chapter, we shall agree that expressions figuring as indices of arrays are always computed in integer arithmetic. Hence, the value of the expression c/2 is  ⌊c/2⌋ , i.e., the floor of c/2.

Occasionally, we consider certain defective heaps:  we say that an array v[1..m] is a heap except perhaps for index k if the inequality v[c/2] ≥ v[c] holds for every c distinct from k.

Exercises 2

Building a heap

It is easy to rearrange the elements of an array v[1..m] of integers so that it becomes a heap.  Just repeat the following process: while the value of a child is larger than the value of its parent, swap the values of parent and child and move one step up, towards the root.  More precisely, while v[c/2] < v[c], do swap (v[c/2], v[c]) and then c = c/2.  The swap operation is

#define swap (A, B) {int t = A; A = B; B = t;}

Here is the complete code:

// Rearranges an array v[1..m] so that
// it decomes a heap.

static void 
buildheap (int m, int v[])
{
   for (int k = 1; k < m; ++k) {                   
      // v[1..k] is a heap
      int c = k+1;
      while (c > 1 && v[c/2] < v[c]) {  // 5
         swap (v[c/2], v[c]);  // 6
         c /= 2;  // 7
      }
   }
}

(The keyword static indicates that buildheap is an auxiliary function that cannot be called directly by the user of Heapsort.)

At the beginning of every iteration controlled by the for, the array v[1..k] is a heap.  In the course of the iteration, v[k+1] moves up the heap (towards the root) until it finds its correct place and is thus incorporated into the heap.

In each repetition of the pair of lines 6-7, the index c jumps from one layer of the array to the previous layer. Hence, this pair of lines can be repeated at most lg(k) times for each fixed k. As a consequence, the total number of comparisons (line 5 of the code) between elements of the array is at most

m lg(m) .

(As we shall see further down, it is possible to do the job with just m comparisons.)

Exercises 3

The sieve function

The core of many algorithms that manipulate heaps is a function that, unlike buildheap, moves down the heap, away from the root.  This function, which we call sieve, receives an arbitrary array v[1..m] and

moves v[1] down to its correct position,

jumping from one layer to the next.  How is this done?  If v[1] ≥ v[2] and v[1] ≥ v[3], nothing needs to be done.  If v[1] < v[2] and v[2] ≥ v[3], just swap v[1] with v[2] and move v[2] down to its correct position.  In the other two cases, do something similar.  (See a draft of the algorithm in pseudocode.)  In the following example, each line of the figure shows the state of the array at the beginning of an iteration:

We can now write the code of the function.  Each iteration begins with an index p and chooses a child c of p which has the largest value:

static void 
sieve (int m, int v[]) {
   int c = 2;
   while (c <= m) {
      if (c < m && v[c] < v[c+1]) ++c;
      // c is a most valuable child of c/2
      if (v[c/2] >= v[c]) break;
      swap (v[c/2], v[c]);
      c *= 2;
   }
}

The function will be applied to arrays that are heaps except perhaps for one or two indices.  The function can, therefore, be documented as follows:

// Receives an array v[1..m] that is a heap
// except perhaps for indices 2 and 3 and
// rearranges the array so that it becomes
// a heap.

The following version is a little better, because it moves fewer elements of the array from one place to another (and does fewer divisions of c by 2):

static void
sieve (int m, int v[])
{ 
   int p = 1, c = 2, x = v[1];
   while (c <= m) {
      if (c < m && v[c] < v[c+1]) ++c;
      if (x >= v[c]) break;
      v[p] = v[c];
      p = c, c = 2*p;
   }
   v[p] = x;
}

Performance.  The sieve function is very fast. It does at most  lg(m)  iterations, since the array has 1 + lg(m) layers.  Each iteration involves two comparisons between elements of the array and therefore the total number of comparisons is at most

2 lg(m) .

The time spent is proportional to the number de comparisons and therefore proportional to  log m  in the worst case.

Exercises 4

The Heapsort algorithm

We can now put together all the pieces discussed above and write an algorithm that will rearrange an array v[1..n] in increasing order.  The algorithm has two phases: the first transforms the array into a heap and the second pulls elements from the heap in decreasing order. (See a draft of the algorithm.)

// Rearranges the elements of array v[1..n] 
// in increasing order.

void
heapsort (int n, int v[])
{
   buildheap (n, v);
   for (int m = n; m >= 2; --m) {
      swap (v[1], v[m]);
      sieve (m-1, v);
   }
}

At the beginning of each iteration of the for, the following invariant properties hold:

• v[1..m] is a heap,
• v[1..m] ≤ v[m+1..n] ,
• v[m+1..n] is in increasing order, and
• v[1..n] is a permutation of the original array.

The expression  v[1..m] ≤ v[m+1..n]  is a shorthand for  each element of v[1..m] is smaller than or equal to every element of v[m+1..n].

It follows that v[1..n] will be in increasing order when m becomes equal to 1.  This shows that the algorithm is correct.

Animations of Heapsort

The animation at right (copied from Simon Waldherr / Golang Sorting Visualization) shows Heapsort running on an array v[0..79] of positive numbers. Each element v[i] of the array is represented by a point (i,v[i]).  (For some reason, the animation does not execute the last two iterations.)

Here is a sample of other animations:

• Heapsort, Wikipedia entry.
• Heapsort animation, by David Galles (University of San Francisco).
• Animation of 15 sorting algorithms, by Timo Bingmann, on YouTube.
• Sorting Algorithms Animations on Toptal.

Exercises 5

Performance of Heapsort

How many comparisons between elements of the array does the heapsort function execute?  The auxiliary function buildheap does at most  n lg(n)  comparisons.  Next, the sieve function is called approximately n times and each of these calls does at most  2 lg(n)  comparisons.  Hence, the total number of comparisons is at most

3 n lg(n).

The time consumed by heapsort is proportional to the number of comparisons between elements of the array, and therefore proportional to  n log n  in the worst case.  (But the proportionality factor is larger than that of Mergesort and Quicksort.)

Exercises 6