Heap Sort

Heap Sort

AU: Dec.-07,08,09,10,11,12, May-10,11,12, Marks 16

In this section we will learn "What is heap?" and "How to construct heap?" and heap sort.

Definition: Heap is a complete binary tree or a almost complete binary tree in which every parent node be either greater or lesser than its child nodes.

Heap can be min heap or max heap.

A Max heap is a tree in which value of each node is greater than or equal to the value of its children nodes.

For example:

A Min heap is a tree in which value of each node is less than or equal to value of its children nodes.

For example:

Parent being greater or lesser in heap is called parental property. Thus heap has two important properties.

Heap Sort

Heap sort is a sorting method discovered by J. W. J. Williams. It works in two stages.

1. Heap construction: First construct a heap for given numbers.

2. Deletion of maximum key: Delete root key always for (n - 1) times to remaining heap. Hence we will get the elements in decreasing order. For an array implementation of heap, delete the element from heap and put the deleted element in the last position in array. Thus after deleting all the elements one by one, if we collect sin buitenoo lliw W these deleted elements in an array starting from last index of array. We get a list of elements in a ascending order.

ADT for heap sort

{

Instances: Heap is a tree data structure denoted by either a maxheap or minheap.

Operations :

1. Create_heap(): This is the first task to be performed for sorting the elements using heap sort. The parent node must be either maximum of its children or minimum than its children. That means a maxheap or minheap should be constructed..

2. Swap(): The root node must be swapped with the node at the last position in tree.

3. Delete_node(): The node at the last position in the heap tree must be deleted.

4. Insert_Q(): The deleted element from the heap must be inserted in the priority queue.

5. Delete_Q(): The element can be deleted from the priority queue by the front end, so that a sorted list can be obtained.

}

 

Ex. 7.4.1: State algorithm to sort elements of a given array in ascending order using heap sort. Sort the following numbers using heap sort: 48, 0, -1, 82, 108, 72, 54.

Sol. Algorithm :

Step 1: Construct the max heap from given set of elements.

Step 2: Swap the root key with the last node key of the heap.

Step 3: Delete the last node and store its key at the end of the array.

Step 4: Heapify the remaining heap structure.

Step 5: Repeat step 2 to 4 until the last remaining node.

Step 6: Delete the last node and store it at the end of the array.

Step 7: Print all the elements of the array. This will display the elements in sorted order.

Consider, 48, 0, 1, 82, 108, 72, 54.

Stage I : Construct heap

We will construct max heap as follows –

Step 1: Insert 48 Step 2: Insert 0 Step 3: Insert - 10 tail s 199 9W

Note that in this heap structure, every parent node has greater value than its child nodes.

Stage II: Delete root node and heapify repeatedly

Step 1 a: Delete root

 

Ex. 7.4.2: State algorithm to sort elements of a given array in ascending order using heapsort. Sort the following numbers using heapsort in descending order:

38, 10, 11, 72, 98, 62, 44.

Sol. :

Step I: Construction of heap

We will construct a min heap

Step II: Deletion of root node and heapify repeatedly

Step 1 a Delete root

Review Question

1. Explain heap sort with example.