Skip to main content

Heapsort: An Efficient Comparison-Based Sorting Algorithm

Introduction to Heapsort​

Heapsort is a comparison-based sorting algorithm that leverages the properties of a binary heap data structure. It combines the best features of other sorting algorithms:

  • O(n log n) worst-case time complexity like Merge Sort
  • In-place sorting like Insertion Sort (with no extra memory beyond a constant amount)
  • Simple implementation similar to Selection Sort, but with better efficiency

Heapsort operates in two main phases:

  1. Build a max heap from the input data
  2. Repeatedly extract the maximum element and rebuild the heap

Understanding Binary Heaps​

Before we dive into the algorithm, it's crucial to understand binary heaps—the data structure at the heart of Heapsort.

What is a Binary Heap?​

A binary heap is a complete binary tree with a specific ordering property:

  • Max Heap: Each parent node is greater than or equal to its children
  • Min Heap: Each parent node is less than or equal to its children

For Heapsort, we typically use a max heap.

Array Representation of Heaps​

While heaps are conceptually trees, they're efficiently implemented using arrays, with the following index relationships:

  • For a node at index i:
    • Parent: Math.floor((i - 1) / 2)
    • Left child: 2 * i + 1
    • Right child: 2 * i + 2

This representation eliminates the need for pointer-based tree structures, leading to better memory locality and simpler implementation.

class MaxHeap {
  constructor() {
    this.heap = [];
  }
  
  // Helper methods for index calculations
  parent(i) {
    return Math.floor((i - 1) / 2);
  }
  
  leftChild(i) {
    return 2 * i + 1;
  }
  
  rightChild(i) {
    return 2 * i + 2;
  }
  
  // Utility methods
  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }
  
  size() {
    return this.heap.length;
  }
}

Core Heap Operations​

1. Heapify: Maintaining the Heap Property​

The heapify operation ensures that the heap property is maintained for a subtree rooted at a given node. It's the fundamental operation that powers Heapsort.

// Heapify a subtree rooted at index i
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
  
  // Check if left child exists and is greater than root
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }
  
  // Check if right child exists and is greater than current largest
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }
  
  // If largest is not the root
  if (largest !== i) {
    // Swap root with the largest element
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    
    // Recursively heapify the affected subtree
    this.heapify(arr, n, largest);
  }
}

Time Complexity: O(log n) in the worst case, as we might need to traverse from a leaf node to the root.

2. Build Heap: Creating a Heap from an Unordered Array​

To transform an arbitrary array into a heap, we need to run heapify on each non-leaf node in reverse order.

// Build a max heap from an unordered array
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--) {
    this.heapify(arr, n, i);
  }
  
  return arr;
}

Time Complexity: While a naive analysis suggests O(n log n), a more careful analysis reveals this operation actually runs in O(n) time.

3. Extract Max: Removing the Root Element​

In a max heap, the maximum element is always at the root. Extracting it involves:

  1. Swap the root with the last element
  2. Remove the last element (the old root)
  3. Heapify the new root to restore the heap property
// Extract the maximum element from the heap
extractMax() {
  if (this.size() === 0) {
    return null;
  }
  
  const max = this.heap[0];
  const lastItem = this.heap.pop();
  
  if (this.size() > 0) {
    this.heap[0] = lastItem;
    this.heapify(this.heap, this.size(), 0);
  }
  
  return max;
}

Time Complexity: O(log n) due to the heapify operation.

Heapsort Algorithm​

With these operations in place, the heapsort algorithm becomes straightforward:

function heapsort(arr) {
  if (arr.length <= 1) return arr;
  
  // Build max heap
  buildMaxHeap(arr);
  
  // Extract elements one by one
  for (let i = arr.length - 1; i > 0; i--) {
    // Move current root (maximum) to the end
    [arr[0], arr[i]] = [arr[i], arr[0]];
    
    // Call heapify on the reduced heap
    heapify(arr, i, 0);
  }
  
  return arr;
}

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

function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }
  
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }
  
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

Complete Implementation with Example​

Let's put everything together with a more detailed implementation:

class HeapSort {
  constructor() {
    this.comparisons = 0;
    this.swaps = 0;
  }
  
  // Resets counters for tracking algorithm efficiency
  resetCounters() {
    this.comparisons = 0;
    this.swaps = 0;
  }
  
  // Sort array using heap sort
  sort(arr) {
    this.resetCounters();
    const n = arr.length;
    
    // Build max heap
    this.buildMaxHeap(arr);
    
    // 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]];
      this.swaps++;
      
      // Call heapify on the reduced heap
      this.heapify(arr, i, 0);
    }
    
    return {
      sortedArray: arr,
      stats: {
        comparisons: this.comparisons,
        swaps: this.swaps
      }
    };
  }
  
  // Build a max heap
  buildMaxHeap(arr) {
    const n = arr.length;
    
    // Start from last non-leaf node
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
      this.heapify(arr, n, i);
    }
  }
  
  // Heapify a subtree rooted at node i
  heapify(arr, heapSize, i) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    
    // Check if left child exists and is larger than root
    if (left < heapSize) {
      this.comparisons++;
      if (arr[left] > arr[largest]) {
        largest = left;
      }
    }
    
    // Check if right child exists and is larger than current largest
    if (right < heapSize) {
      this.comparisons++;
      if (arr[right] > arr[largest]) {
        largest = right;
      }
    }
    
    // If largest is not root
    if (largest !== i) {
      // Swap
      [arr[i], arr[largest]] = [arr[largest], arr[i]];
      this.swaps++;
      
      // Recursively heapify the affected sub-tree
      this.heapify(arr, heapSize, largest);
    }
  }
}

// Usage example
const sorter = new HeapSort();
const array = [12, 11, 13, 5, 6, 7];
const result = sorter.sort([...array]);

console.log("Original array:", array);
console.log("Sorted array:", result.sortedArray);
console.log("Performance:", result.stats);

Step-by-Step Walkthrough​

Let's trace the algorithm with a small array: [4, 10, 3, 5, 1]

  1. Build Max Heap:

    • Start with the last non-leaf node (index 1, value 10)
    • Apply heapify: 10 is already larger than its child (1), no change
    • Move to index 0 (value 4)
    • Apply heapify:
      • 10 > 4, so swap 4 and 10
      • Array becomes: [10, 4, 3, 5, 1]
      • Continue heapify at the new position of 4
      • 5 > 4, so swap 4 and 5
      • Array becomes: [10, 5, 3, 4, 1]
    • Heap is built: [10, 5, 3, 4, 1]

  2. Extract elements:

    • Swap 10 with 1: [1, 5, 3, 4, 10]
    • Heapify the reduced heap (excluding 10):
      • 5 > 1, so swap 1 and 5
      • Array becomes: [5, 1, 3, 4, 10]
      • Continue heapify at the new position of 1
      • 4 > 1, so swap 1 and 4
      • Array becomes: [5, 4, 3, 1, 10]
    • Swap 5 with 1: [1, 4, 3, 5, 10]
    • Heapify: [4, 1, 3, 5, 10]
    • Swap 4 with 3: [3, 1, 4, 5, 10]
    • Heapify: [3, 1, 4, 5, 10]
    • Swap 3 with 1: [1, 3, 4, 5, 10]
    • Final sorted array: [1, 3, 4, 5, 10]

Time and Space Complexity Analysis​

Time Complexity​

  • Build Heap: O(n) time
  • Extract Max (n times): Each extraction takes O(log n), so total is O(n log n)
  • Overall: O(n) + O(n log n) = O(n log n)

Worst-case time complexity: O(n log n)
Best-case time complexity: O(n log n)
Average-case time complexity: O(n log n)

Unlike Quicksort, Heapsort maintains its O(n log n) performance even in the worst case.

Space Complexity​

Space complexity: O(1)

Heapsort is an in-place sorting algorithm that requires only a constant amount of additional space, regardless of input size.

Heapsort vs. Other Sorting Algorithms​

1. Heapsort vs. Quicksort​

  • Time Complexity:
    • Heapsort: Always O(n log n)
    • Quicksort: O(n²) worst case, O(n log n) average case
  • Space Complexity:
    • Heapsort: O(1)
    • Quicksort: O(log n) for recursion stack
  • Stability:
    • Both are unstable sorts
  • Practical Performance:
    • Quicksort often outperforms Heapsort due to better cache locality

2. Heapsort vs. Mergesort​

  • Time Complexity:
    • Both are O(n log n) in all cases
  • Space Complexity:
    • Heapsort: O(1)
    • Mergesort: O(n)
  • Stability:
    • Heapsort: Unstable
    • Mergesort: Stable
  • Use Cases:
    • Heapsort is better when memory is constrained
    • Mergesort is better when stability is required

Performance Optimization Techniques​

1. Iterative Implementation​

The recursive heapify function can be rewritten iteratively to avoid stack overhead:

function heapifyIterative(arr, n, i) {
  let current = i;
  let largest = current;
  let done = false;
  
  while (!done) {
    const left = 2 * current + 1;
    const right = 2 * current + 2;
    
    // Find the largest among current node and its children
    if (left < n && arr[left] > arr[largest]) {
      largest = left;
    }
    
    if (right < n && arr[right] > arr[largest]) {
      largest = right;
    }
    
    // If largest is still the current node, we're done
    if (largest === current) {
      done = true;
    } else {
      // Otherwise, swap and continue
      [arr[current], arr[largest]] = [arr[largest], arr[current]];
      current = largest;
    }
  }
}

2. Bottom-Up Heapsort​

A further optimization involves a bottom-up approach that can reduce the number of comparisons:

function bottomUpHeapsort(arr) {
  const n = arr.length;
  
  // Build heap bottom-up
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(arr, i, n);
  }
  
  // Extract elements
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    siftDown(arr, 0, i);
  }
  
  return arr;
}

function siftDown(arr, start, end) {
  let root = start;
  
  // While the root has at least one child
  while (root * 2 + 1 < end) {
    let child = root * 2 + 1; // Left child
    let swap = root;
    
    // Check if root should be swapped with left child
    if (arr[swap] < arr[child]) {
      swap = child;
    }
    
    // Check if right child exists and if it's larger than what we want to swap with
    if (child + 1 < end && arr[swap] < arr[child + 1]) {
      swap = child + 1;
    }
    
    // If no swap needed, we're done
    if (swap === root) {
      return;
    } else {
      // Swap and continue sifting down
      [arr[root], arr[swap]] = [arr[swap], arr[root]];
      root = swap;
    }
  }
}

Practical Applications of Heap and Heapsort​

1. Priority Queues​

Heaps are the data structure of choice for implementing priority queues:

class PriorityQueue {
  constructor() {
    this.heap = [];
  }
  
  // Add element with priority
  enqueue(value, priority) {
    const element = { value, priority };
    this.heap.push(element);
    this._siftUp(this.heap.length - 1);
    return this;
  }
  
  // Remove the highest priority element
  dequeue() {
    const max = this.heap[0];
    const end = this.heap.pop();
    
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this._siftDown(0);
    }
    
    return max?.value;
  }
  
  // Check the highest priority element
  peek() {
    return this.heap[0]?.value;
  }
  
  isEmpty() {
    return this.heap.length === 0;
  }
  
  _siftUp(idx) {
    let parentIdx = Math.floor((idx - 1) / 2);
    
    while (
      idx > 0 && 
      this.heap[parentIdx]?.priority < this.heap[idx]?.priority
    ) {
      // Swap with parent
      [this.heap[parentIdx], this.heap[idx]] = 
      [this.heap[idx], this.heap[parentIdx]];
      
      // Move up
      idx = parentIdx;
      parentIdx = Math.floor((idx - 1) / 2);
    }
  }
  
  _siftDown(idx) {
    const leftIdx = 2 * idx + 1;
    const rightIdx = 2 * idx + 2;
    const length = this.heap.length;
    let largest = idx;
    
    // Compare with left child
    if (
      leftIdx < length && 
      this.heap[leftIdx].priority > this.heap[largest].priority
    ) {
      largest = leftIdx;
    }
    
    // Compare with right child
    if (
      rightIdx < length && 
      this.heap[rightIdx].priority > this.heap[largest].priority
    ) {
      largest = rightIdx;
    }
    
    // If a child is larger, swap and continue sifting down
    if (largest !== idx) {
      [this.heap[idx], this.heap[largest]] = 
      [this.heap[largest], this.heap[idx]];
      this._siftDown(largest);
    }
  }
}

// Usage example
const taskQueue = new PriorityQueue();
taskQueue.enqueue("Low priority task", 1);
taskQueue.enqueue("High priority task", 10);
taskQueue.enqueue("Medium priority task", 5);

console.log(taskQueue.dequeue()); // "High priority task"
console.log(taskQueue.dequeue()); // "Medium priority task"
console.log(taskQueue.dequeue()); // "Low priority task"

2. Finding k Largest/Smallest Elements​

Using a min-heap to find k largest elements in O(n log k) time:

function findKLargest(arr, k) {
  if (k <= 0 || k > arr.length) {
    return [];
  }
  
  // Create min-heap of size k
  const minHeap = [];
  
  // Fill heap with first k elements
  for (let i = 0; i < k; i++) {
    minHeap.push(arr[i]);
    heapifyUp(minHeap, minHeap.length - 1);
  }
  
  // For each remaining element
  for (let i = k; i < arr.length; i++) {
    // If it's larger than the smallest in our heap
    if (arr[i] > minHeap[0]) {
      // Replace the root with this element
      minHeap[0] = arr[i];
      heapifyDown(minHeap, 0);
    }
  }
  
  // Sort the result (optional)
  return minHeap.sort((a, b) => b - a);
  
  function heapifyUp(heap, index) {
    const parentIndex = Math.floor((index - 1) / 2);
    if (parentIndex >= 0 && heap[parentIndex] > heap[index]) {
      [heap[parentIndex], heap[index]] = [heap[index], heap[parentIndex]];
      heapifyUp(heap, parentIndex);
    }
  }
  
  function heapifyDown(heap, index) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let smallest = index;
    
    if (left < heap.length && heap[left] < heap[smallest]) {
      smallest = left;
    }
    
    if (right < heap.length && heap[right] < heap[smallest]) {
      smallest = right;
    }
    
    if (smallest !== index) {
      [heap[index], heap[smallest]] = [heap[smallest], heap[index]];
      heapifyDown(heap, smallest);
    }
  }
}

const array = [7, 10, 4, 3, 20, 15];
console.log(findKLargest(array, 3)); // [20, 15, 10]

3. Heap Sort in Operating Systems​

Many operating systems use heap data structures for memory allocation algorithms:

class MemoryAllocator {
  constructor(totalMemory) {
    this.totalMemory = totalMemory;
    this.allocatedBlocks = new Map();
    this.freeBlocks = new PriorityQueue(); // Min heap by block size
    
    // Initially one large free block
    this.freeBlocks.enqueue({
      address: 0,
      size: totalMemory
    }, -totalMemory); // Negative for min-heap
  }
  
  // Allocate memory block of given size
  allocate(size) {
    if (size <= 0) return null;
    
    // Find the smallest free block large enough
    const block = this.findFreeBlock(size);
    if (!block) return null; // Out of memory
    
    // Allocate memory
    const allocatedBlock = {
      address: block.address,
      size: size
    };
    
    // Update free blocks
    if (block.size > size) {
      this.freeBlocks.enqueue({
        address: block.address + size,
        size: block.size - size
      }, -(block.size - size));
    }
    
    // Track allocated block
    const id = Date.now() + Math.random();
    this.allocatedBlocks.set(id, allocatedBlock);
    
    return {
      id,
      ...allocatedBlock
    };
  }
  
  // Free a previously allocated block
  free(id) {
    const block = this.allocatedBlocks.get(id);
    if (!block) return false;
    
    // Add to free blocks
    this.freeBlocks.enqueue(block, -block.size);
    this.allocatedBlocks.delete(id);
    
    // In a real implementation, we would merge adjacent free blocks here
    return true;
  }
  
  // Find smallest free block that can fit the requested size
  findFreeBlock(size) {
    // Implementation simplified for demonstration
    // In practice, would use a more sophisticated best-fit algorithm
    const blocks = [];
    let bestBlock = null;
    
    // Extract all blocks
    while (!this.freeBlocks.isEmpty()) {
      const block = this.freeBlocks.heap[0];
      this.freeBlocks.dequeue();
      
      if (!bestBlock && -block.priority >= size) {
        bestBlock = block.value;
      }
      
      blocks.push(block);
    }
    
    // Restore heap except the chosen block
    blocks.forEach(block => {
      if (block.value !== bestBlock) {
        this.freeBlocks.enqueue(block.value, block.priority);
      }
    });
    
    return bestBlock;
  }
}

Common Pitfalls and Tips​

1. Index Arithmetic​

When implementing heap operations, be careful with index calculations:

  • Parent of node at index i: Math.floor((i - 1) / 2)
  • Left child: 2 * i + 1
  • Right child: 2 * i + 2

A common mistake is using Math.floor(i / 2) for the parent, which works for 1-indexed heaps but not 0-indexed heaps.

2. Heap Construction​

The efficient O(n) approach for building a heap starts from the last non-leaf node. A common error is starting from the beginning of the array, which would result in O(n log n) time.

3. Stability​

Heapsort is not a stable sorting algorithm. If you need to preserve the relative order of equal elements, consider using Mergesort instead.

Conclusion​

Heapsort stands as an elegant and efficient sorting algorithm that offers the best of both worlds: the fast average-case performance of Quicksort and the guaranteed worst-case bounds of Mergesort, all while using only O(1) extra space.

While it may not always be the fastest option in practice due to cache behavior and other hardware considerations, Heapsort remains an important tool in the algorithm designer's toolkit, particularly when:

  1. Memory is constrained
  2. Worst-case guarantees are required
  3. Implementing priority queues or selection algorithms

In our next article, we'll explore how heaps can be used to implement more advanced data structures and algorithms, including Dijkstra's shortest path algorithm and A* search.