Heap Sort Using Dynamic Array

Introduction

In this lab, you will learn how to implement the Heap Sort algorithm using dynamic arrays in C++. Heap sort is a comparison-based sorting algorithm that works by dividing the input into a sorted and an unsorted region and iteratively shrinking the unsorted region by extracting the largest or smallest element and moving that to the sorted region.

Creating the Dynamic Array

We will create a new file named main.cpp in the ~/project directory using the following command:

touch ~/project/main.cpp

First, we will create a dynamic array to store elements. We will use the new operator to dynamically allocate memory during the program's runtime.

int* arr;
arr = new int[size];

Heapify Function

Next, we will create the heapify() function to reorder the elements in the array. The purpose of the heapify() function is to maintain the heap property, which means that each node is greater than or equal to its children.

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

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

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

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

Heap Sort Function

After implementing the heapify() function, we will create the heapSort() function to sort the array in ascending order.

void heapSort(int* arr, int n) {
    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);
    }
}

Main Function

Lastly, we will create the main() function to read the elements from the user and to display the sorted array using the heap sort algorithm.

int main() {
    int size;
    cout << "Enter the number of elements: ";
    cin >> size;

    int* arr;
    arr = new int[size];

    cout << "Enter the elements: ";
    for (int i = 0; i < size; i++) {
        cin >> arr[i];
    }

    heapSort(arr, size);

    cout << "Sorted Array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    delete[] arr;
    return 0;
}

Summary

In this lab, you learned how to implement the Heap Sort algorithm using dynamic arrays in C++. You also learned about creating a dynamic array, heapifying the array, and sorting the array to display the sorted array in ascending order. Follow the instructions to run the sample code and practice implementing the Heap Sort algorithm.