Heap Sort

 

A heapsort algorithm works by first organizing the data to be sorted into a special type of binary tree called a heap. Any kind of data can be sorted either in ascending order or in descending order using a heap tree. It does this with the following steps:

1. Build a heap tree with a given set of data.

2. a. Remove the topmost item (the largest) and replace it with the last

element in the heap.

b. Re-heapify the complete binary tree.

c. Place the deleted node in the output.

3. Continue step 2 until the heap tree is empty.

ALGORITHM + PSEUDOCODE:

This algorithm sorts the elements a[n]. Heap sort rearranges them in-place in nondecreasing order. First, transform the elements into a heap.

heapsort(a, n)

{

heapify(a, n);

for i = n to 2 by – 1 do

{

temp = a[i];

a[i] = a[1];

a[1]=temp;

adjust (a, 1, i – 1);

}

}

heapify (a, n)

//Readjust the elements in a[n] to form a heap.

{

for i <- ⎣ n/2 ⎦ to 1 by – 1 do adjust (a, i, n);

}

adjust (a, i, n)

// The complete binary trees with roots a(2*i) and a(2*i + 1) are combined with a(i) to

form a single heap, 1 < i < n. No node has an address greater than n or less than 1. //

{

j = 2 *i ;

item = a[i] ;

while (j < n) do

{

if ((j < n) and (a (j) < a (j + 1)) then j <-  j + 1;

// compare left and right child and let j be the larger child

if (item > a (j)) then break;

// a position for item is found

else a[  ⎣ j / 2 ⎦ ] = a[j] // move the larger child up a level

j = 2 * j;

}

a [  ⎣ j / 2 ⎦  ] = item;

}

PROTOTYPE CODE:

heapSort(array a, int n) {

heapify(a,n)

for( j = n ; j > 1 ; j-- ) {

swap a[1] and a[j]

bubbleDown(1,a,j-1)

}

}

FUNCTIONING DIAGRAM:

COMPLEXITY ANALYSIS:

Each ‘n’ insertion operations takes O(log k), where ‘k’ is the number of elements in the

heap at the time. Likewise, each of the ‘n’ removes operations also runs in time O(log

k), where ‘k’ is the number of elements in the heap at the time.

Since we always have k ≤ n, each such operation runs in O(log n) time in the worst

case.

Thus, for ‘n’ elements it takes O(n log n) time, so the priority queue sorting algorithm

runs in O(n log n) time when we use a heap to implement the priority queue.