Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

Marks: 10 M

Year: Dec 2014

Heap sort is made up of two phases:

Phase 1: Build a heap using the given elements.

Phase 2: Continuous deletion of root element from the heap.

As we know that in a max-heap, the root element is always the maximum value element of the heap, so after every deletion we would be obtaining the new maximum value at the top.

Phase 2: (The nodes deleted will be the descending order heap-sort)

(Note: Do not go by the length of this sum. Understand the method and you can do it very quickly.)

Algorithm for Heap Sort:

Step 1: For k= 0 to N-1 (where N is the number of values)

Insert_into_heap(arr,N, arr[k])

Step 2: Repeat while N>0

Delete_from_heap (arr,N);

Increase N by 1;

Step 3: END