Heap Sort Explained: How to Sort Data Efficiently Using Heaps

Heap Sort is one of the most efficient and reliable sorting algorithms, widely used in various applications, from database indexing to computer graphics. In this guide, we’ll dive deep into the mechanics of Heap Sort, explain its complexity, and provide practical examples.

What is Heap Sort?

Heap Sort is a comparison-based sorting technique based on a binary heap data structure. It operates in two main phases: building a heap and then repeatedly extracting the maximum (or minimum) element from the heap and rebuilding the heap until it’s empty.

How Heap Sort Works

Heap Sort is a straightforward process when you have a heap data structure at your disposal. The algorithm consists of two main steps: building the heap and repeatedly extracting elements from it until the list is sorted.

1. Build the Heap:
   • Start by creating a heap out of the unsorted input array using the MakeHeap / Heapify operations. This step is done in linear time – O(n).
2. Extract and Sort:
   • Once the heap is built, repeatedly remove the root element (the largest or smallest element, depending on the heap type) using the heap’s removal method. Removing the root element from the heap has a time complexity of O(logn).
   • After each removal, the heap adjusts itself to maintain its order, making sure the next largest (or smallest) element is ready for extraction.
   • Continue this process getting the largest / smallest element every time until the heap is empty, and the array is fully sorted.

Complexity: By leveraging the heap’s ability to quickly access and remove the highest-priority element in O(logn) time, Heap Sort efficiently sorts the array with with a time complexity of O(n log n) by repeating the removal operation n times.

Here is a short video demonstrating HeapSort where the heap is abstracted. If you want to see the internals of the heap, we suggest you read our post about heaps linked above.

Implementation

import heapq

def heap_sort(arr):
    heapq.heapify(arr)  # Transform the list into a heap in-place
    sorted_arr = []
    
    while arr:
        sorted_arr.append(heapq.heappop(arr))  # Pop the smallest element from the heap
    
    return sorted_arr

Explanation

• heapq.heapify(arr): This function transforms the list arr into a heap, in-place, in linear time.
• heapq.heappop(arr): This function pops and returns the smallest item from the heap, maintaining the heap invariant. In this case, we repeatedly pop elements from the heap and append them to the sorted_arr list.