Heap Sort Algorithm

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure. It divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and moving that to the end of the sorted region. The heap data structure ensures that the largest (or smallest) element is always at the root of the heap, making it easy to extract.

Table of Contents

1. Introduction
2. Heap Data Structure
3. Building a Max Heap
4. Heap Sort Algorithm Steps
5. Code Implementation
6. Time and Space Complexity
7. Best Practices
8. Real-world Applications

Introduction

Heap sort is an efficient sorting algorithm with a time complexity of \(O(n \log n)\) in the worst, average, and best cases. It's not a stable sort, meaning that it does not preserve the relative order of equal elements. However, its performance is consistent across different types of input data, making it suitable for large datasets.

Heap Data Structure

A heap is a specialized tree-based data structure that satisfies the heap property: for any given node \(i\), the value of \(i\) is greater than or equal to (in a max heap) or less than or equal to (in a min heap) the values of its children. This property ensures that the largest element in a max heap is always at the root.

Types of Heaps

• Max Heap: The parent node is always greater than or equal to its child nodes.
• Min Heap: The parent node is always less than or equal to its child nodes.

Building a Max Heap

To perform heap sort, we first need to build a max heap from the input data. This involves rearranging the elements so that they satisfy the max heap property.

Steps to Build a Max Heap

1. Start from the Last Non-Leaf Node: The last non-leaf node is at index \((n/2) - 1\), where \(n\) is the total number of nodes.
2. Heapify Each Node: For each node, ensure that it satisfies the max heap property by comparing it with its children and swapping if necessary.

Code Example for Building a Max Heap

function buildMaxHeap(arr) {
    const n = arr.length;
    // Start from the last non-leaf node and heapify each node
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

function heapify(arr, n, i) {
    let largest = i; // Initialize largest as root
    const left = 2 * i + 1; // Left child index
    const right = 2 * i + 2; // Right child index

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // If largest is not root
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]]; // Swap

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

Heap Sort Algorithm Steps

1. Build a Max Heap: Convert the input array into a max heap.
2. Extract Elements: Repeatedly extract the maximum element from the heap (root of the heap) and place it at the end of the sorted region.
3. Reduce Heap Size: After extracting an element, reduce the size of the heap by one and call heapify on the root to restore the max heap property.

Code Example for Heap Sort

function heapSort(arr) {
    const n = arr.length;

    // Build a max heap
    buildMaxHeap(arr);

    // One by one extract an element from heap
    for (let i = n - 1; i > 0; i--) {
        // Move current root to end
        [arr[0], arr[i]] = [arr[i], arr[0]];

        // Call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

// Example usage:
const data = [12, 11, 13, 5, 6, 7];
heapSort(data);
console.log("Sorted array is:", data);

Time and Space Complexity

• Time Complexity: \(O(n \log n)\)

  • Building the max heap takes \(O(n)\).
  • Each of the \(n\) elements is extracted from the heap with a cost of \(O(\log n)\).

• Space Complexity: \(O(1)\)

  • Heap sort is an in-place sorting algorithm, requiring only a constant amount of additional memory space.

Best Practices

1. Use for Large Datasets: Heap sort is efficient for large datasets where stability is not a concern.
2. Avoid for Small or Nearly Sorted Data: For small or nearly sorted data, other algorithms like insertion sort might be more efficient.
3. Consider Stability: If maintaining the relative order of equal elements is important, consider using a stable sorting algorithm like merge sort.

Real-world Applications

Heap sort is used in various applications where efficiency and consistency are crucial:

• Operating Systems: For managing tasks and processes based on priority.
• Databases: For indexing and sorting large datasets.
• Network Routing Protocols: For maintaining routing tables with priorities.

By understanding the heap sort algorithm, you can effectively utilize it in scenarios requiring efficient sorting of large datasets.