Heap Sort Algorithm / Heapify Function

CODE: 

#include <iostream>

using namespace std;

// A function to heapify the array.

void MaxHeapify(int a[], int i, int n)

{

int j, temp;

temp = a[i];

j = 2*i;   //(left child)

  while (j <= n)                  

{

if (j < n && a[j+1] > a[j])

j = j+1;

// Break if parent value is already greater than child value.

if (temp > a[j])

break;

// Switching value with the parent node if temp < a[j].

else if (temp <= a[j])

{

a[j/2] = a[j];

j = 2*j;

}

};

a[j/2] = temp;

return;

}

void HeapSort(int a[], int n)

{

int i, temp;

for (i = n; i >= 2; i--)

{

// Storing maximum value at the end.

temp = a[i];

a[i] = a[1];

a[1] = temp;

// Building max heap of remaining element.

MaxHeapify(a, 1, i - 1);

}

}

void Build_MaxHeap(int a[], int n)

{

int i;

for(i = n/2; i >= 1; i--)

MaxHeapify(a, i, n);

}

int main()

{

int n, i;

cout<<"\nEnter the number of data element to be sorted: ";

cin>>n;

n++;

int arr[n];

for(i = 1; i < n; i++)

{

cout<<"Enter element "<<i<<": ";

cin>>arr[i];

}

// Building max heap.

Build_MaxHeap(arr, n-1);

HeapSort(arr, n-1);

 

// Printing the sorted data.

cout<<"\nSorted Data ";

 

for (i = 1; i < n; i++)

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

 

return 0;

}

MaxHeapify function: This function is responsible for maintaining the heap property. It takes an array a[], an index i, and the size of the heap n. It compares the parent node with its left and right child nodes and swaps values if necessary to maintain the heap property.

HeapSort function: This function performs the heap sort algorithm. It repeatedly extracts the maximum element from the heap (the root of the heap), swaps it with the last element in the heap, and then restores the heap property using MaxHeapify. It does this until the heap is empty.

Build_MaxHeap function: This function builds a max heap from an array. It starts from the last non-leaf node and calls MaxHeapify for each node until the root node is reached.

Main function:

It prompts the user to enter the number of elements to be sorted (n).

It initializes an array arr[] of size n.

It prompts the user to enter n elements one by one.

It builds a max heap from the array using Build_MaxHeap.

It sorts the array using HeapSort.

It prints the sorted array.

Algorithm:

1. Function MaxHeapify:

   • Inputs:
     • a[]: The array to be heapified.
     • i: Index of the current node.
     • n: Size of the array.
   • Start:
     • Declare variables j and temp.
     • Assign temp as the value at index i of the array.
     • Initialize j as the index of the left child of node i.
     • While j is less than or equal to n, do:
       • If j is less than n and the value of the right child is greater than the left child, increment j.
       • If the value at index i of the array is greater than the value at index j, break the loop.
       • If the value at index i of the array is less than or equal to the value at index j, assign the value at index j of the array to the parent node (a[j/2]) and update j to its child (2*j).
     • Assign temp to the parent node (a[j/2]).

2. Function HeapSort:

   • Inputs:
     • a[]: The array to be sorted.
     • n: Size of the array.
   • Start:
     • Declare variables i and temp.
     • Iterate i from n to 2.
       • Swap the maximum value (at index 1) with the last element of the array.
       • Re-heapify the remaining elements except the last one.

3. Function Build_MaxHeap:

   • Inputs:
     • a[]: The array to be converted into a max heap.
     • n: Size of the array.
   • Start:
     • Iterate i from n/2 to 1.
     • Call MaxHeapify(a, i, n) for each index i.

4. Main Function:

   • Inputs:
     • n: Number of elements to be sorted.
   • Start:
     • Prompt the user to enter the number of elements to be sorted.
     • Read the input value of n.
     • Create an array arr[] of size n+1.
     • Iterate i from 1 to n:
       • Prompt the user to enter element i.
       • Read the input value and store it in arr[i].
     • Call Build_MaxHeap(arr, n-1) to convert arr[] into a max heap.
     • Call HeapSort(arr, n-1) to sort the array.
     • Print the sorted array.