Heap Sort Algorithm: Mastering Efficient Sorting with Heaps

7.2.4 Heap Sort Algorithm

Heap Sort is a comparison-based sorting technique based on a binary heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements.

Understanding Heap Sort

Heap Sort works by leveraging the heap data structure, specifically a binary heap, to sort elements. The algorithm involves two main phases: building a heap and repeatedly extracting the maximum element to achieve a sorted array.

Steps of Heap Sort:

1. Build a Max-Heap from the input data.
2. Extract the maximum element from the heap and swap it with the last element of the heap.
3. Reduce the heap size by one, effectively removing the last element from the heap.
4. Heapify the root element to maintain the heap property.
5. Repeat the process until the heap is empty.

The key operation in heap sort is maintaining the heap property, which ensures that the parent node is always greater than or equal to its child nodes in a max-heap.

Implementing Heap Sort in JavaScript

To implement heap sort, we need to define a MaxHeap class that supports operations like building the heap and heapifying elements.

class MaxHeap {
  constructor() {
    this.heap = [];
    this.heapSize = 0;
  }

  buildHeap(array) {
    this.heap = array;
    this.heapSize = array.length;
    for (let i = Math.floor(this.heapSize / 2) - 1; i >= 0; i--) {
      this.heapifyDownFromIndex(i);
    }
  }

  heapifyDownFromIndex(index) {
    let largest = index;
    const left = 2 * index + 1;
    const right = 2 * index + 2;

    if (left < this.heapSize && this.heap[left] > this.heap[largest]) {
      largest = left;
    }

    if (right < this.heapSize && this.heap[right] > this.heap[largest]) {
      largest = right;
    }

    if (largest !== index) {
      [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
      this.heapifyDownFromIndex(largest);
    }
  }
}

function heapSort(array) {
  const heap = new MaxHeap();
  heap.buildHeap(array);

  for (let i = array.length - 1; i > 0; i--) {
    [heap.heap[0], heap.heap[i]] = [heap.heap[i], heap.heap[0]];
    heap.heapSize = i;
    heap.heapifyDownFromIndex(0);
  }

  return heap.heap;
}

// Example usage:
const unsortedArray = [3, 19, 1, 14, 8, 7];
console.log(heapSort(unsortedArray)); // Output: [1, 3, 7, 8, 14, 19]

Characteristics of Heap Sort

• Time Complexity: Heap Sort has a time complexity of O(n log n) for all cases (best, average, and worst). This is due to the heapify operation, which takes O(log n) time and is called n times.
• Space Complexity: O(1) if sorting is done in place, meaning no additional arrays are used.
• Stability: Heap Sort is not a stable sort, meaning it does not preserve the relative order of equal elements.

Comparing Heap Sort with Other Sorting Algorithms

Heap Sort, Quick Sort, and Merge Sort are all efficient sorting algorithms with their own strengths and weaknesses.

• Quick Sort: Often faster in practice than Heap Sort due to better cache performance, but has a worst-case time complexity of O(n^2). It is not stable.
• Merge Sort: Stable and has a time complexity of O(n log n) for all cases, but requires additional space for merging.
• Heap Sort: Consistent O(n log n) time complexity and in-place sorting, but not stable.

Practical Examples and Test Cases

To validate the implementation, consider testing with various types of input arrays:

1. Sorted Array: [1, 2, 3, 4, 5]
2. Reverse Sorted Array: [5, 4, 3, 2, 1]
3. Random Array: [3, 19, 1, 14, 8, 7]
4. Array with Duplicates: [3, 3, 3, 3, 3]

const testArrays = [
  [1, 2, 3, 4, 5],
  [5, 4, 3, 2, 1],
  [3, 19, 1, 14, 8, 7],
  [3, 3, 3, 3, 3]
];

testArrays.forEach(arr => {
  console.log(`Original: ${arr}`);
  console.log(`Sorted: ${heapSort([...arr])}`);
});

Visualization of Heap Sort

To better understand how heap sort works, consider the following visualization of the heap structure and sorting process:

    graph TD;
	    A[Unsorted Array] --> B[Build Max-Heap];
	    B --> C[Extract Max];
	    C --> D[Swap with Last Element];
	    D --> E[Reduce Heap Size];
	    E --> F[Heapify Root];
	    F --> C;
	    F --> G[Sorted Array];

Best Practices and Optimization Tips

• In-Place Sorting: Ensure that the sorting is done in place to optimize space usage.
• Heapify Efficiency: Optimize the heapify process to minimize the number of swaps and comparisons.
• Edge Cases: Consider edge cases like empty arrays and arrays with a single element.

Common Pitfalls

• Index Errors: Be cautious of off-by-one errors when calculating child indices in the heap.
• Heap Size Management: Properly manage the heap size during extraction to avoid accessing out-of-bounds elements.

Conclusion

Heap Sort is a powerful sorting algorithm that provides consistent performance across different types of input data. While it may not be the fastest in practice compared to Quick Sort, its predictable time complexity and in-place sorting make it a valuable tool in a programmer’s toolkit.

Quiz Time!