The Algorithm Design Manual Second Edition

4.3

Heapsort: Fast Sorting via Data Structures

Sorting is a natural laboratory for studying algorithm design paradigms, since many

useful techniques lead to interesting sorting algorithms. The next several sections

will introduce algorithmic design techniques motivated by particular sorting algo-

rithms.

---

4 . 3

H E A P S O R T : F A S T S O R T I N G V I A D A T A S T R U C T U R E S

109

The alert reader should ask why we review the standard sorting when you

are better off not implementing them and using built-in library functions instead.

The answer is that the design techniques are very important for other algorithmic

problems you are likely to encounter.

We start with data structure design, because one of the most dramatic algo-

rithmic improvements via appropriate data structures occurs in sorting. Selection

sort is a simple-to-code algorithm that repeatedly extracts the smallest remaining

element from the unsorted part of the set:

SelectionSort(A)

For i = 1 to n do

Sort[i] = Find-Minimum from A

Delete-Minimum from A

Return(Sort)

A C language implementation of selection sort appeared back in Section

2.5.1

(page

41

). There we partitioned the input array into sorted and unsorted regions. To

find the smallest item, we performed a linear sweep through the unsorted portion

of the array. The smallest item is then swapped with the ith item in the array

before moving on to the next iteration. Selection sort performs n iterations, where

the average iteration takes n/2 steps, for a total of O(n

2

) time.

But what if we improve the data structure? It takes O(1) time to remove a

particular item from an unsorted array once it has been located, but O(n) time

to find the smallest item. These are exactly the operations supported by priority

queues. So what happens if we replace the data structure with a better priority

queue implementation, either a heap or a balanced binary tree? Operations within

the loop now take O(log n) time each, instead of O(n). Using such a priority queue

implementation speeds up selection sort from O(n

2

) to O(n log n).

The name typically given to this algorithm, heapsort, obscures the relationship

between them, but heapsort is nothing but an implementation of selection sort

using the right data structure.