Heap Sort as a Priority Queue

Heap

A heap is a binary tree satisfying the following restrictions:

• All leaves are on two adjacent levels
• All leaves on the lowest level occur at left of the tree
• All leaves above the lowest level are completely filled
• Both children of any node are again heaps
• The value stored at any node is at least as largest (or smallest) as the value in its two children

The most useful property of a heap is that the largest/smallest node in the tree is always the root.

Fig: A Heap

Heap as a Priority Queue

The most common application of a heap isas a 'priority queue'. In a priority queue, each element is assigned a unique priority. Elements with the highest priority should be the first to leave the queue.

A heap can either be a Max Heap or a Min Heap. A max (or min) heap is an almost complete or complete binary tree with the property that the value at each node is at least as large as (or as small as) the value of its children.

Array Implementation of Heaps

In practice, heaps are usually implemented as arrays. A heap is a special kind of binary tree that leaves no gaps in an array implementation. So, array representation of the tree will be memory efficient. To represent an almost complete or complete binary tree as an array:

• The root node is A[1]
• Node i is A[i], i = 1, 2, 3, ...
• The parent of node i is A[i/2]
• The left child of node i is A[2i]
• The right child of node is A[2I+1]

is converted as:

Construction of Heap

While constructing a heap, we always must fill up the first left field and then the right field and the root node is always greater (or smaller) than its children.

Eg: Create a min heap of data given in the order: 4, 8, 3, 1, 5, 2

Fig: Min Heap of 4, 8, 3, 1, 5, 2

Building a Heap:

a) BuildMaxHeap(A)

Input: An array A[1. . . n]

Output: A heap A[1. . . n]

n = length[A]

for i = floor(n/2) downto 1

then MaxHeapify(A,i)

stop

MaxHeapify(A,i)

l = LEFT(i)

r = RIGHT(i)

if l <= n and A[l] > A[i]

then largest = l

else largest = i

if r <= n and A[r] > A[largest]

then largest = r

if largest != i

exchange A[i], A[largest]

MaxHeapify(A,largest)

Endif

Stop

Here,

PARENT(i) = floor(i/2)

LEFT(i) = 2i

RIGHT(i) = 2i + 1

Heap Sort

Heap sort was invented by W.J Williams in 1964. By using a heap-based priority queue, we can sort a sequence of n elements in O(nlogn) time. The resulting algorithm is called heap-sort.

Heap sort is much faster than quadratic sorting algorithms, such as insertion-sort and selection-sort. The heap sort algorithm can be divided into two parts:

• In the first step, Construct the heap from the given data
• In the second step, a sorted array is created by repeatedly removing the largest (or smallest) element from the heap (the root of the heap), and inserting it into the array. The heap is updated after each removal to maintain the heap.

To sort the elements in the descending order, we use a Min Heap.

To sort the elements in the ascending order, we use a Max Heap.

Concept:

• Start by building a max-heap on all elements in A. Maximum element is in the root, A[1]
• Move the maximum element to its correct final position. Exchange A[1] with A[n]
• Discard A[n] - it is now sorted. Decrement heap-size[A]
• Restore the max-heap property on A[1..n-1]. Call MaxHeapify(A,1,n-1)
• Repeat until heap-size[A] is reduced to 2.

Heap Sort Algorithm:

1. BuldMaxHeap(A)

2. for i = length[A] downto 2

exchange A[1], A[i]

heap-size[A] = heap-size[A] - 1

MaxHeapify(A,1)

Endloop

3. Stop

Heap Sort Example: A= [7, 4, 3, 1, 2]

References:

1. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”

2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction to Algorithms”

3. G. Brassard and P. Bratley, “Fundamentals of Algorithms”

4. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program designin C”