The Heap Sort Algorithm Explained

The Heap

A heap is a specialized binary tree data structure that satisfies the heap property. In a heap, each node has at most two children, and the key (the value) of each node is greater than or equal to (in a max heap) or less than or equal to (in a min heap) the keys of its children. The binary tree representation of a heap is a complete binary tree, meaning that all levels of the tree are completely filled except possibly for the last level, which is filled from left to right.

Heap Sort

Heap sort is a comparison-based sorting algorithm that uses a max heap to sort elements in ascending order. The algorithm works by first building a max heap from the input array. It then repeatedly extracts the maximum element from the heap and places it at the end of the array. This process is repeated until all elements have been extracted and the array is sorted in ascending order.

Heap sort has a time complexity of O(nlogn) and is an in-place sorting algorithm, meaning it does not require any additional memory beyond the input array.

An array can be used to represent the heap structure by using the following indexing scheme:

• The root of the heap is at index 0.
• For any node at index i, its left child is at index 2*i+1 and its right child is at index 2*i+2.

Using this indexing scheme, we can represent a heap as an array and perform heap operations on it efficiently.

For example, to build a max heap from an array, we can start at the last non-leaf node (which is at index n/2-1, where n is the size of the array) and perform the heapify operation on each node from this index down to the root. The heapify operation ensures that the node is the largest of the three by swapping it with the largest child if necessary. By calling heapify on each node from the last non-leaf node down to the root, we ensure that the entire array represents a max heap.

An C++ Example

Here is an C++ example that builds a max heap based on the input vector:

void heapify(std::vector<int>& vec, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && vec[left] > vec[largest]) {
        largest = left;
    }

    if (right < n && vec[right] > vec[largest]) {
        largest = right;
    }

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

void build_max_heap(std::vector<int>& vec) {
    int n = vec.size();

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

The build_max_heap function constructs a max heap from a given vector of integers. A max heap is a binary tree where the value of each node is greater than or equal to the values of its children. The build_max_heap function starts by finding the index of the last non-leaf node in the binary tree, which is n/2 - 1, where n is the size of the vector.

It then iterates from this index down to the root of the tree, calling the heapify function on each node.

The heapify function takes a node and its two children and ensures that the node is the largest of the three by swapping it with the largest child if necessary. By calling heapify on each node from the last non-leaf node down to the root, the build_max_heap function ensures that the entire binary tree is a max heap.

Now we call this function and construct a max heap:

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

    // create a maximum heap
    build_max_heap(vec);

    // print the maximum element
    std::cout << "Maximum element: " << vec.front() << std::endl;

    // print the whole vector
    std::cout << "The heap: ";
    for (auto i : vec) {
        std::cout << i << " ";
    }

    return 0;
}

The output is:

Maximum element: 9
The heap: 9 6 4 5 5 3 2 1 1 3 5

If we append a new number 12 to the end of the vector and re-construct the max heap:

vec.push_back(12);
build_max_heap(vec);

std::cout << "\nThe heap: ";
for (auto i : vec) {
	std::cout << i << " ";
}

The output is:

The heap: 12 6 9 5 5 4 2 1 1 3 5 3

We will see that, after re-construct the max heap, the newly appended element 12 becomes to the top element of this max heap.

The Heap In C++ Standard Library

std::make_heap and std::priority_queue are both C++ standard library containers that are used to implement heaps. However, they have some differences in their functionality and usage:

• std::make_heap is a function that takes a range of elements and rearranges them into a heap. It does not provide any additional functionality beyond constructing the heap. Once the heap is constructed, you can use other algorithms like std::sort_heap or std::pop_heap to manipulate the heap.

• std::priority_queue is a container adapter that provides a priority queue data structure. It is implemented using a heap and provides additional functionality beyond just constructing the heap. It allows you to insert elements into the priority queue, remove the highest-priority element, and access the highest-priority element without removing it. It also provides a way to customize the comparison function used to determine the priority of elements.

The Heap Related LeetCode Problems

215. Kth Largest Element in an Array

347. Top K Frequent Elements

703. Kth Largest Element in a Stream