Heap Sort Algorithm in DSA C++ - Build from Scratch

Heap Sort Algorithm

📖 Scenario: You are working on a program that needs to sort a list of numbers efficiently. Heap sort is a great way to do this by using a special tree structure called a heap.Imagine you have a messy pile of books and you want to arrange them from smallest to largest by height. Heap sort helps you organize them step by step.

🎯 Goal: Build a C++ program that sorts an array of integers using the heap sort algorithm. You will create the array, set up helper variables, write the heapify function, and then perform the sorting. Finally, you will print the sorted array.

📋 What You'll Learn

Create an integer array with exact values: 12, 11, 13, 5, 6, 7

Create an integer variable n to store the size of the array

Write a heapify function that maintains the max heap property

Implement the heap sort logic using the heapify function

Print the sorted array in ascending order separated by spaces

💡 Why This Matters

🌍 Real World

Heap sort is used in systems where guaranteed O(n log n) sorting time is needed, such as in embedded systems or real-time applications.

💼 Career

Understanding heap sort helps in technical interviews and improves problem-solving skills related to priority queues and efficient sorting.

1

Create the array and its size

Create an integer array called arr with these exact values: 12, 11, 13, 5, 6, 7. Then create an integer variable called n and set it to the size of arr.

DSA C++

# Create the array 'arr' and integer 'n' for its size
// Your code here

Hint

Use int arr[] = {12, 11, 13, 5, 6, 7}; to create the array. Use sizeof(arr) / sizeof(arr[0]) to find the size.

2

Write the heapify function

Write a function called heapify that takes three parameters: an integer array arr, an integer n for the size of the heap, and an integer i for the index to heapify. This function should maintain the max heap property by comparing the parent node with its children and swapping if needed.

DSA C++

#include 
using namespace std;

void heapify(int arr[], int n, int i) {
    // Your code here
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    return 0;
}

Hint

Remember to check left and right children indices and swap with the largest if needed. Use recursion to heapify the affected subtree.

3

Implement the heap sort logic

In the main function, first build a max heap by calling heapify on all non-leaf nodes from n/2 - 1 down to 0. Then, extract elements one by one from the heap by swapping the root with the last element and calling heapify on the reduced heap.

DSA C++

#include 
using namespace std;

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left  arr[largest])
        largest = left;

    if (right  arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Build max heap
    // Your code here

    // Extract elements from heap
    // Your code here

    return 0;
}

Hint

First build the max heap by heapifying from the middle to the start. Then swap the root with the last element and heapify the reduced heap repeatedly.

4

Print the sorted array

After sorting, print the elements of arr separated by spaces in one line using a for loop.

DSA C++

#include 
using namespace std;

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left  arr[largest])
        largest = left;

    if (right  arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }

    // Print the sorted array
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Hint

Use a for loop from 0 to n-1 and print each element followed by a space. End with cout << endl;.