Heapsort Algorithm#

Welcome to Day 28 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Heapsort algorithm, an efficient, comparison-based sorting algorithm that leverages the properties of a heap data structure.

See it in motion: watch heap sort build a max-heap and extract 100 values in order in our free interactive visualizer.

Introduction to Heapsort#

Heapsort is a sorting algorithm that uses a binary heap data structure to sort elements. It’s an in-place algorithm with an O(n log n) time complexity, making it optimal for large datasets.

How Heapsort Works#

Heapsort works in two main steps:

1. Build a max heap from the input array.
2. Repeatedly extract the maximum element from the heap and place it at the end of the array.

Implementing Heapsort#

Let’s implement the Heapsort algorithm:

 1def heapify(arr, n, i):
 2    largest = i
 3    left = 2 * i + 1
 4    right = 2 * i + 2
 5
 6    if left < n and arr[left] > arr[largest]:
 7        largest = left
 8
 9    if right < n and arr[right] > arr[largest]:
10        largest = right
11
12    if largest != i:
13        arr[i], arr[largest] = arr[largest], arr[i]
14        heapify(arr, n, largest)
15
16def heapsort(arr):
17    n = len(arr)
18
19    # Build a max-heap
20    for i in range(n // 2 - 1, -1, -1):
21        heapify(arr, n, i)
22
23    # Extract elements from the heap one by one
24    for i in range(n - 1, 0, -1):
25        arr[0], arr[i] = arr[i], arr[0]
26        heapify(arr, i, 0)
27
28    return arr
29
30# Example usage
31arr = [12, 11, 13, 5, 6, 7]
32sorted_arr = heapsort(arr)
33print(f"Sorted array: {sorted_arr}")

Time Complexity#

• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n log n)

Heapsort has a consistent time complexity of O(n log n) for all cases, which is one of its main advantages.

Space Complexity#

• O(1) - Heapsort is an in-place sorting algorithm, requiring only a constant amount of additional memory.

Advantages of Heapsort#

1. Efficient time complexity of O(n log n) for all cases.
2. In-place sorting algorithm, requiring no extra space.
3. Relatively simple to implement compared to other efficient sorting algorithms.

Disadvantages of Heapsort#

1. Not stable: Does not preserve the relative order of equal elements.
2. Poor cache performance: The algorithm’s access pattern to memory can lead to many cache misses.
3. Generally slower in practice compared to well-implemented Quicksort on average.

Optimizations for Heapsort#

1. Bottom-up Heap Construction#

Instead of using top-down heapify for initial heap construction, we can use a bottom-up approach which is more efficient:

1def build_max_heap(arr):
2    n = len(arr)
3    for i in range(n // 2 - 1, -1, -1):
4        heapify(arr, n, i)

2. Heap Optimization for Small Arrays#

For small arrays or subarrays, we can switch to insertion sort:

 1def insertion_sort(arr, left, right):
 2    for i in range(left + 1, right + 1):
 3        key = arr[i]
 4        j = i - 1
 5        while j >= left and arr[j] > key:
 6            arr[j + 1] = arr[j]
 7            j -= 1
 8        arr[j + 1] = key
 9
10def optimized_heapsort(arr):
11    n = len(arr)
12    
13    # Use insertion sort for small arrays
14    if n <= 10:
15        insertion_sort(arr, 0, n - 1)
16        return arr
17    
18    # Build a max-heap
19    for i in range(n // 2 - 1, -1, -1):
20        heapify(arr, n, i)
21
22    # Extract elements from the heap one by one
23    for i in range(n - 1, 0, -1):
24        arr[0], arr[i] = arr[i], arr[0]
25        heapify(arr, i, 0)
26
27    return arr

Applications of Heapsort#

1. External Sorting: When dealing with large datasets that don’t fit into memory.
2. K-way Merging: Efficiently merging k sorted arrays.
3. Finding the k largest/smallest elements: Heapsort can be modified to find these efficiently.
4. Priority Queues: The underlying heap structure is used in priority queue implementations.

Comparison with Other Sorting Algorithms#

Exercise#

1. Implement a variation of Heapsort that sorts the array in descending order.
2. Modify the Heapsort algorithm to find the k largest elements in an array.
3. Implement an iterative version of Heapsort (without using recursion for the heapify process).

Summary#

Today, we explored the Heapsort algorithm, an efficient comparison-based sorting algorithm that leverages the heap data structure. We implemented the basic algorithm, discussed its time and space complexity, and looked at some optimizations.

Heapsort’s consistent O(n log n) time complexity and in-place sorting make it a valuable algorithm to understand and use, especially when dealing with large datasets or in memory-constrained environments.

As we conclude our exploration of comparison-based sorting algorithms, it’s important to understand the trade-offs between Heapsort, Quicksort, and Mergesort. Each has its strengths and is suited to different scenarios.

Tomorrow, we’ll dive into a comprehensive comparison of sorting algorithms, analyzing their performance in various scenarios and discussing how to choose the right sorting algorithm for specific use cases. Stay tuned!

Solution#

 1def min_heapify(arr, n, i):
 2    smallest = i
 3    left = 2 * i + 1
 4    right = 2 * i + 2
 5    if left < n and arr[left] < arr[smallest]:
 6        smallest = left
 7    if right < n and arr[right] < arr[smallest]:
 8        smallest = right
 9    if smallest != i:
10        arr[i], arr[smallest] = arr[smallest], arr[i]
11        min_heapify(arr, n, smallest)
12
13def heapsort_descending(arr):
14    n = len(arr)
15    # Build a min-heap
16    for i in range(n // 2 - 1, -1, -1):
17        min_heapify(arr, n, i)
18    # Move the smallest element to the end, then re-heapify the rest
19    for i in range(n - 1, 0, -1):
20        arr[0], arr[i] = arr[i], arr[0]
21        min_heapify(arr, i, 0)
22    return arr
23
24# Example usage
25arr = [12, 11, 13, 5, 6, 7]
26print(f"Sorted (descending): {heapsort_descending(arr)}")  # [13, 12, 11, 7, 6, 5]