Heap Sort

Heap Sort

There is a good explanation here: https://www.geeksforgeeks.org/dsa/heap-sort/

https://github.com/explorer436/programming-playground/tree/main/java-playground/my-implementations/searching-and-sorting/src/main/java/com/my/company/sorting/algorithms

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements efficiently. It works by transforming the input array into a max-heap (or min-heap, depending on the desired order) and then repeatedly extracting the maximum (or minimum) element to build the sorted output.

Heap Sort is particularly useful when you need a reliable, in-place sorting algorithm with guaranteed O(n log n) performance, though it’s less commonly used in practice compared to Quick Sort due to its higher constant factors and lack of stability.

How Heap Sort Works

1. Build a Max-Heap:
   1. A binary heap is a complete binary tree where each node’s value is greater than or equal to its children (for a max-heap).
   2. The input array is rearranged in-place to satisfy the max-heap property: for any node at index `i`, the value at `i` is greater than or equal to the values at its children (indices `2i+1` and `2i+2`).
   3. This is done by calling a “heapify” function on each non-leaf node, starting from the last non-leaf node (at index `n/2 - 1`, where `n` is the array size) up to the root.
2. Move the root element (the maximum element) to the end of the array and Heapify all the elements except the last element:
   1. Once the max-heap is built, the largest element is at the root (index 0).
   2. Swap the root with the last element of the heap (at index `n-1`).
   3. Reduce the heap size by 1 (effectively placing the largest element at the end of the array).
   4. Call heapify on the root to restore the max-heap property for the remaining elements.
   5. Repeat this process, moving the next largest element to the end, until the heap size becomes 1.
3. Result:
   1. After all elements are processed, the array is sorted in ascending order (since the largest elements are placed at the end one by one).
4. Note: If we start with a MinHeap (instead of using a MaxHeap), when this is done, we will have an array that is sorted in descending order.
   1. We will have to reverse the array to get the array in ascending order.

Complexity analysis

• Time Complexity:
  • Building the heap: O(n)
  • Heapify operations (n times): O(n log n)
  • Total: O(n log n) for all cases (best, average, worst).
• Space Complexity: O(1) (in-place sorting, excluding recursion stack).
• Stability: Not stable (relative order of equal elements may change).
• Advantages: Efficient for large datasets, in-place, and guaranteed O(n log n) performance.
• Disadvantages: Not stable, and not as cache-friendly as some other algorithms like Quick Sort.

Tags

1. Heap (data structure)