Sorting Algorithm: Heap Sort

Sorting Algorithms

• Various sorting algorithms which we will study in this chapter are ‒

1. Insertion sort

2. Merge sort

3. Quick sort

4. Heap sort

 

Sorting Algorithm: Heap Sort

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

Heap sort: Heap construction, Deletion of maximum key

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 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.

}

 

Example : 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.

Solution : 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 ‒

Stage II : Delete root node and heapify repeatedly

Step 1 a : Delete root

Step 1 b : Heapify

Step 2 a : Delete root

Step 2 b : Heapify

Step 3 a : Delete root

Step 3 b : Heapify

Step 4 a : Delete root node

Step 4 b : Heapify

Step 5 a : Delete root node

Step 5 b : Heapify

Step 6 a : Delete root node

Delete it and insert it at the end of heap array

Step 6 b :

 

Example : 2

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

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

Solution :

Stage I: Construction of heap

We will construct a min heap, as we have to sort in descending order.

Stage II : Deletion of root node and hepify repeatedly.

Step 1 a : Delete root

Step 1 b : Heapify

Step 2 a : Delete root

Step 2 b : Heapify

Step 3 a : Delete root

Step 3 b : Heapify

Step 4 a : Delete root

Step 4 b : Heapify

Step 5 a : Delete root

Step 5 b : Heapify

Step 6 : Delete root

Step 7 : Delete single node and insert at the end of heap array

C++ Program

#include <iostream>

using namespace std;

// Function to heapify a subtree rooted at index i

void heapify(int arr[], int n, int i) {

int largest = i;      // Assume root is largest

int left = 2* i + 1;  // Left child index

int right = 2*i + 2;  // Right child index

// If left child is larger than root

if (left<n && arr[left] > arr[largest])

largest = left;

// If right child is larger than largest so far

if (right < n && arr[right]> arr[largest])

largest = right;

// If largest is not the root

if (largest != 1) {

swap(arr[i], arr[largest]);

heapify(arr, n, largest);

}

}

void heapSort(int arr[], int n) {

    // Step 1: Build max heap

    for (int I = n/2 ‒ 1; i >= 0; i‒‒)

    heapify(arr, n, i);

    // Step 2: One by one extract elements from heap

    for (int i = n ‒ 1; i >= 0; i‒‒) {

    // Move current root to end

        swap(arr[0], arr[i]);

    // Call heapify on reduced heap

        heapify(arr, i, 0);

}

}

int main() {

    int arr[] = {38, ‒10, ‒11, 72, 98, 62, 44};

    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    cout << "Sorted array: ";

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

    cout << endl;

    return 0;

}

Output

Sorted array: ‒11 ‒10 38 44 62 72 98

 

Analysis:

Time complexity : The time complexity of heap sort is O(n log n).

Part I: Recurrence relation for heapify()

If height of the heap of h.

So recurrence relation is ‒

T(h) = T(h‒1) + O(1)

T(h) = T(h− 2) + O(1) + O(1)

T(h) = T(h‒3) + 3 . O(1)

…

T(h) = T(0) + h. O(1)

Since height h = log n

T(h) = O(log n)

Time complexity of one heapify = O(log n)

Part II : Heap building

Heap buliding calls heapify on : n/2 nodes

Number of nodes at height h = n/ 2^h+1

Time for each node at height h = O(h)

Total timeT(n)  =