Heap Sort

JavaScript Implementation

function heapSort(arr) {
  const n = arr.length;
  
  // Build max heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
  
  // Extract elements from heap one by one
  for (let i = n - 1; i > 0; i--) {
    // Move current root to end
    [arr[0], arr[i]] = [arr[i], arr[0]];
    
    // Call heapify on the reduced heap
    heapify(arr, i, 0);
  }
  
  return arr;
}

// Heapify a subtree rooted at node i
function heapify(arr, n, i) {
  let largest = i;        // Initialize largest as root
  const left = 2 * i + 1; // Left child
  const right = 2 * i + 2; // Right child
  
  // 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) {
    // Swap and continue heapifying
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

// Example usage
const array = [4, 10, 3, 5, 1];
console.log(heapSort(array)); // Output: [1, 3, 4, 5, 10]

Python Implementation

def heap_sort(arr):
    n = len(arr)
    
    # Build a max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        # Move current root to end
        arr[i], arr[0] = arr[0], arr[i]
        
        # Call heapify on the reduced heap
        heapify(arr, i, 0)
    
    return arr

def heapify(arr, n, i):
    largest = i       # Initialize largest as root
    left = 2 * i + 1  # Left child
    right = 2 * i + 2 # Right child
    
    # If left child exists and is greater than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # If right child exists and is greater than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # If largest is not root
    if largest != i:
        # Swap
        arr[i], arr[largest] = arr[largest], arr[i]
        
        # Recursively heapify the affected sub-tree
        heapify(arr, n, largest)

# Example usage
array = [4, 10, 3, 5, 1]
print(heap_sort(array))  # Output: [1, 3, 4, 5, 10]

Time Complexity

• Build Heap: O(n) - This is not the obvious O(n log n) that you might expect, but can be proven to be O(n)
• Heapify: O(log n) - Each call to heapify takes O(log n) time
• Extract from Heap: O(n log n) - We call heapify n times

Overall time complexity for all cases (best, average, worst):

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

This consistent performance across all scenarios is a significant advantage of heap sort.

Iterative Heapify

The recursive heapify function can be implemented iteratively to save stack space:

function heapifyIterative(arr, n, i) {
  let largest = i;
  let complete = false;
  
  while (!complete) {
    const left = 2 * largest + 1;
    const right = 2 * largest + 2;
    let newLargest = largest;
    
    if (left < n && arr[left] > arr[newLargest]) {
      newLargest = left;
    }
    
    if (right < n && arr[right] > arr[newLargest]) {
      newLargest = right;
    }
    
    if (newLargest !== largest) {
      [arr[largest], arr[newLargest]] = [arr[newLargest], arr[largest]];
      largest = newLargest;
    } else {
      complete = true;
    }
  }
}