Sorting with a Heap

Selection sorting involves the repeated selection of the next element in the sorted sequence from the set of remaining elements. For example, the straight insertion sorting algorithm given in the preceding section builds the sorted sequence by repeatedly selecting the largest remaining element and prepending it to the sorted sequence developing at the right end of the array.

At each step the largest remaining element is withdrawn from the set of remaining elements. A linear search is done because the order of the remaining elements is arbitrary. However, if we consider the value of each element as its priority, we can view the set of remaining elements as a priority queue. In effect, a selection sort repeatedly dequeues the highest priority element from a priority queue.

Chapter  presents a number of priority queue implementations, including binary heaps, leftist heaps and binomial queues. In this section we present a version of selection sorting that uses a binary heap  to hold the elements that remain to be sorted. Therefore, it is called a heapsort . The principal advantage of using a binary heap is that it is easily implemented using an array and the entire sort can be be done in place.

As explained in Section , a binary heap is a complete binary tree  which is easily represented in an array. The n nodes of the heap occupy positions 1 through n of the array. The root is at position 1. In general, the children of the node at position i of the array are found at positions 2i and 2i+1, and the parent is found at position .

The heapsort algorithm consists of two phases. In the first phase, the unsorted array is transformed into a heap. (This is called heapifying  the array). In this case, a max-heap  rather than a min-heap is used. The data in a max heap satisfies the following condition: For every node in the heap that has a parent, the item contained in the parent is greater than or equal to the item contained in the given node.

The second phase of heapsort builds the sorted list. The sorted list is built by repeatedly selecting the largest element, withdrawing it from the heap, and adding it to the sorted sequence. As each element is withdrawn from the heap, the remaining elements are heapified.

• Implementation

Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.