Heap Sort

Overview

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to organize elements. The algorithm builds a max heap from the input data, then repeatedly extracts the maximum element and places it at the end of the sorted array. This process continues until all elements have been sorted.

The algorithm was invented by J.W.J. Williams in 1964 as a method to sort data efficiently without requiring additional memory proportional to the input size. Unlike merge sort, heap sort operates in-place, requiring only a constant amount of extra memory regardless of input size.

Heap sort achieves guaranteed O(n log n) time complexity in all cases - best, average, and worst. This predictable performance makes it suitable for systems where worst-case guarantees matter more than average-case performance. The algorithm sacrifices some practical speed compared to quicksort in exchange for consistency and in-place operation.

The sorting process operates in two phases. First, the algorithm transforms the input array into a max heap structure, where each parent node contains a value greater than or equal to its children. Second, the algorithm repeatedly swaps the root element (maximum value) with the last unsorted element, reduces the heap size, and restores the heap property through a process called heapify.

# Basic heap sort structure
def heap_sort(array)
  # Phase 1: Build max heap
  build_max_heap(array)
  
  # Phase 2: Extract elements
  (array.length - 1).downto(1) do |i|
    array[0], array[i] = array[i], array[0]
    heapify(array, 0, i)
  end
  
  array
end

Key Principles

The heap data structure forms the foundation of heap sort. A binary heap is a complete binary tree where each node satisfies the heap property relative to its children. In a max heap, every parent node contains a value greater than or equal to its children. In a min heap, every parent node contains a value less than or equal to its children. Heap sort uses max heaps.

The array representation stores heap elements sequentially, with the root at index 0. For any element at index i, the left child resides at index 2i + 1 and the right child at index 2i + 2. The parent of any node at index i (where i > 0) is located at index (i - 1) / 2. This implicit structure eliminates the need for pointer-based tree nodes.

The heapify operation maintains the heap property for a subtree rooted at a given index. When a node violates the max heap property, heapify compares it with its children, swaps it with the larger child if necessary, and recursively applies the process to the affected subtree. This operation runs in O(log n) time since the maximum number of swaps equals the tree height.

def heapify(array, root_index, heap_size)
  largest = root_index
  left = 2 * root_index + 1
  right = 2 * root_index + 2
  
  # Compare with left child
  if left < heap_size && array[left] > array[largest]
    largest = left
  end
  
  # Compare with right child
  if right < heap_size && array[right] > array[largest]
    largest = right
  end
  
  # Swap and continue heapifying if needed
  if largest != root_index
    array[root_index], array[largest] = array[largest], array[root_index]
    heapify(array, largest, heap_size)
  end
end

The build heap operation converts an unordered array into a valid max heap. Starting from the last non-leaf node and working backwards to the root, the algorithm applies heapify to each node. The last non-leaf node is located at index (n/2) - 1 where n is the array length. This bottom-up approach runs in O(n) time, not O(n log n) as might be expected, because most nodes are near the bottom of the tree and require few comparisons.

The extraction phase removes the maximum element by swapping the root with the last element in the heap, reducing the heap size by one, and restoring the heap property through heapify. This process repeats until only one element remains. Each extraction requires O(log n) time for heapify, and n-1 extractions occur, yielding O(n log n) total time for this phase.

The heap property guarantees that the maximum element always resides at the root. This invariant enables the efficient extraction of sorted elements in descending order. By placing extracted elements at the end of the array (in positions no longer considered part of the heap), the algorithm achieves in-place sorting without additional arrays.

Ruby Implementation

Ruby arrays provide direct access by index, making them suitable for heap implementation. The language's tuple assignment syntax simplifies swapping elements during heapify operations. Ruby's built-in methods like downto and range operators create readable iteration over heap indices.

class HeapSort
  def self.sort(array)
    return array if array.length <= 1
    
    heap_size = array.length
    
    # Build max heap from bottom up
    ((heap_size / 2) - 1).downto(0) do |i|
      max_heapify(array, i, heap_size)
    end
    
    # Extract elements one by one
    (heap_size - 1).downto(1) do |i|
      array[0], array[i] = array[i], array[0]
      max_heapify(array, 0, i)
    end
    
    array
  end
  
  def self.max_heapify(array, index, heap_size)
    left = 2 * index + 1
    right = 2 * index + 2
    largest = index
    
    largest = left if left < heap_size && array[left] > array[largest]
    largest = right if right < heap_size && array[right] > array[largest]
    
    if largest != index
      array[index], array[largest] = array[largest], array[index]
      max_heapify(array, largest, heap_size)
    end
  end
end

numbers = [64, 34, 25, 12, 22, 11, 90]
HeapSort.sort(numbers)
# => [11, 12, 22, 25, 34, 64, 90]

The iterative heapify approach avoids recursive function calls, reducing call stack overhead. This implementation tracks the current index in a loop and updates it after each swap, continuing until the heap property is satisfied or a leaf node is reached.

def iterative_heapify(array, index, heap_size)
  loop do
    left = 2 * index + 1
    right = 2 * index + 2
    largest = index
    
    largest = left if left < heap_size && array[left] > array[largest]
    largest = right if right < heap_size && array[right] > array[largest]
    
    break if largest == index
    
    array[index], array[largest] = array[largest], array[index]
    index = largest
  end
end

Sorting custom objects requires a comparison mechanism. Ruby's spaceship operator (<=>) works with the heapify logic when objects implement Comparable. The implementation accepts a block for custom comparison criteria, similar to Ruby's built-in sort methods.

class HeapSort
  def self.sort(array, &comparator)
    comparator ||= ->(a, b) { a <=> b }
    heap_size = array.length
    
    ((heap_size / 2) - 1).downto(0) do |i|
      heapify_with_comparator(array, i, heap_size, &comparator)
    end
    
    (heap_size - 1).downto(1) do |i|
      array[0], array[i] = array[i], array[0]
      heapify_with_comparator(array, 0, i, &comparator)
    end
    
    array
  end
  
  def self.heapify_with_comparator(array, index, heap_size, &comparator)
    left = 2 * index + 1
    right = 2 * index + 2
    largest = index
    
    if left < heap_size && comparator.call(array[left], array[largest]) > 0
      largest = left
    end
    
    if right < heap_size && comparator.call(array[right], array[largest]) > 0
      largest = right
    end
    
    if largest != index
      array[index], array[largest] = array[largest], array[index]
      heapify_with_comparator(array, largest, heap_size, &comparator)
    end
  end
end

Person = Struct.new(:name, :age)
people = [Person.new("Alice", 30), Person.new("Bob", 25), Person.new("Charlie", 35)]
HeapSort.sort(people) { |a, b| a.age <=> b.age }
# => [Person("Bob", 25), Person("Alice", 30), Person("Charlie", 35)]

The non-mutating version creates a copy before sorting, preserving the original array. This follows Ruby conventions where methods ending with ! modify the receiver while others return modified copies.

module HeapSortable
  def heap_sort
    self.dup.heap_sort!
  end
  
  def heap_sort!
    heap_size = length
    
    ((heap_size / 2) - 1).downto(0) do |i|
      heap_adjust(i, heap_size)
    end
    
    (heap_size - 1).downto(1) do |i|
      self[0], self[i] = self[i], self[0]
      heap_adjust(0, i)
    end
    
    self
  end
  
  private
  
  def heap_adjust(index, heap_size)
    largest = index
    left = 2 * index + 1
    right = 2 * index + 2
    
    largest = left if left < heap_size && self[left] > self[largest]
    largest = right if right < heap_size && self[right] > self[largest]
    
    if largest != index
      self[index], self[largest] = self[largest], self[index]
      heap_adjust(largest, heap_size)
    end
  end
end

class Array
  include HeapSortable
end

original = [5, 2, 8, 1, 9]
sorted = original.heap_sort
# original => [5, 2, 8, 1, 9]
# sorted => [1, 2, 5, 8, 9]

Performance Considerations

Heap sort maintains O(n log n) time complexity across all input distributions. The build heap phase takes O(n) time through a tight mathematical analysis showing that most nodes require few swaps. The extraction phase performs n-1 heapify operations, each taking O(log n) time, for a total of O(n log n). The worst case occurs when elements are in ascending order, requiring maximum swaps during extraction.

The space complexity is O(1) for the iterative implementation, requiring only a constant number of variables regardless of input size. The recursive heapify version uses O(log n) space for the call stack in the worst case, corresponding to the height of the heap tree. This call stack usage is typically acceptable since log n remains small even for large inputs.

Cache performance suffers compared to algorithms like quicksort. The heapify operation accesses array elements with stride 2i + 1 and 2i + 2, causing poor spatial locality. Sequential access patterns in merge sort or quicksort exhibit better cache utilization. Modern processors prefetch sequential memory access more effectively than the scattered access pattern of heap traversal.

require 'benchmark'

def measure_sort_performance(size)
  array = Array.new(size) { rand(1..10000) }
  
  Benchmark.bm(15) do |x|
    x.report("heap_sort:") { HeapSort.sort(array.dup) }
    x.report("quicksort:") { array.dup.sort }
  end
end

measure_sort_performance(10_000)
# heap_sort:      0.045000   0.000000   0.045000
# quicksort:      0.012000   0.000000   0.012000

The number of comparisons heap sort performs exceeds the theoretical minimum. While the information-theoretic lower bound for comparison sorts is log₂(n!), heap sort typically performs 2n log n comparisons. Quicksort and merge sort approach the theoretical minimum more closely in average cases.

Heap sort is not a stable sort - elements with equal keys may change relative order during sorting. The heapify operation can swap equal elements when maintaining the heap property, destroying the original ordering. Applications requiring stability must use merge sort or insertion sort instead.

The in-place nature provides an advantage when memory is constrained. Unlike merge sort, which requires O(n) auxiliary space, heap sort operates directly on the input array. This makes heap sort preferable in embedded systems or when sorting very large datasets that barely fit in available memory.

Branch prediction struggles with heap sort's comparison patterns. The conditional logic in heapify depends on data values, creating unpredictable branches that modern processors mispredict. Algorithms with more predictable branch patterns, like radix sort for integers, can exploit processor branch prediction more effectively.

Design Considerations

Heap sort fits scenarios requiring guaranteed O(n log n) performance without additional memory. Real-time systems with hard latency requirements benefit from heap sort's consistent worst-case behavior. Unlike quicksort, which can degrade to O(n²) on adversarial input, heap sort never exceeds O(n log n) time.

The algorithm suits situations where in-place sorting is mandatory. Embedded systems with limited RAM cannot allocate O(n) auxiliary space for merge sort. Mobile applications with memory constraints favor heap sort over memory-intensive alternatives. Database systems sorting large tables that exceed available memory use heap sort or external sort variants.

Quicksort outperforms heap sort in typical cases due to better cache locality and fewer total comparisons. For general-purpose sorting where input distribution is unknown, quicksort with median-of-three pivot selection or introsort (which switches to heap sort on detecting O(n²) behavior) provides better average performance while maintaining worst-case guarantees.

Merge sort is preferable when stability is required. Sorting employee records by salary while preserving the existing ordering by hire date requires a stable sort. Merge sort maintains element ordering while heap sort does not. The O(n) space cost of merge sort is acceptable when stability matters.

Insertion sort beats heap sort on small arrays (typically n < 10-20). The constant factors in heap sort's implementation overhead outweigh its asymptotic advantage for small inputs. Hybrid approaches like introsort switch to insertion sort for small subarrays while using quicksort or heap sort for larger portions.

Priority queue implementation represents the primary use case for heap structures rather than pure sorting. When repeatedly extracting minimum or maximum elements, maintaining a heap throughout operations is more efficient than repeated sorting. Task schedulers, event simulation systems, and Dijkstra's shortest path algorithm use heaps for efficient priority operations.

External sorting of datasets larger than memory combines heap sort principles with disk-based algorithms. The k-way merge sort uses a heap to track the minimum element across k sorted runs stored on disk. This approach minimizes disk seeks while maintaining O(n log n) complexity for out-of-core sorting.

Practical Examples

Sorting fixed-size arrays in embedded systems demonstrates heap sort's in-place advantage. Consider a microcontroller with 2KB RAM processing sensor data. The system cannot allocate additional arrays for merge sort but can sort in place.

class SensorDataProcessor
  MAX_READINGS = 1000
  
  def initialize
    @readings = []
  end
  
  def add_reading(temperature)
    @readings << temperature
    
    # Sort when buffer is full
    if @readings.length >= MAX_READINGS
      sort_and_process
    end
  end
  
  def sort_and_process
    # In-place sort to conserve memory
    heap_sort_in_place(@readings)
    
    median = @readings[@readings.length / 2]
    process_median(median)
    
    @readings.clear
  end
  
  private
  
  def heap_sort_in_place(array)
    heap_size = array.length
    
    ((heap_size / 2) - 1).downto(0) do |i|
      heapify(array, i, heap_size)
    end
    
    (heap_size - 1).downto(1) do |i|
      array[0], array[i] = array[i], array[0]
      heapify(array, 0, i)
    end
  end
  
  def heapify(array, index, heap_size)
    largest = index
    left = 2 * index + 1
    right = 2 * index + 2
    
    largest = left if left < heap_size && array[left] > array[largest]
    largest = right if right < heap_size && array[right] > array[largest]
    
    if largest != index
      array[index], array[largest] = array[largest], array[index]
      heapify(array, largest, heap_size)
    end
  end
  
  def process_median(value)
    # Process the median value
  end
end

Finding the kth largest element uses partial heap sort efficiently. Building a heap and extracting k elements finds the kth largest in O(n + k log n) time, better than full sorting when k << n.

def find_kth_largest(array, k)
  return nil if k > array.length || k < 1
  
  # Build max heap
  heap_size = array.length
  ((heap_size / 2) - 1).downto(0) do |i|
    heapify(array, i, heap_size)
  end
  
  # Extract k-1 elements
  (k - 1).times do |i|
    array[0], array[heap_size - 1 - i] = array[heap_size - 1 - i], array[0]
    heapify(array, 0, heap_size - 1 - i)
  end
  
  array[0]
end

scores = [95, 87, 92, 78, 88, 91, 85]
third_highest = find_kth_largest(scores.dup, 3)
# => 91

Task scheduling with priority queues demonstrates heap operations beyond pure sorting. A max heap tracks tasks by priority, extracting the highest priority task efficiently.

class TaskScheduler
  Task = Struct.new(:name, :priority, :deadline)
  
  def initialize
    @tasks = []
  end
  
  def add_task(name, priority, deadline)
    @tasks << Task.new(name, priority, deadline)
    bubble_up(@tasks.length - 1)
  end
  
  def get_next_task
    return nil if @tasks.empty?
    
    # Swap root with last element
    @tasks[0], @tasks[-1] = @tasks[-1], @tasks[0]
    task = @tasks.pop
    
    # Restore heap property
    heapify_down(0) if @tasks.any?
    
    task
  end
  
  private
  
  def bubble_up(index)
    while index > 0
      parent = (index - 1) / 2
      break if @tasks[parent].priority >= @tasks[index].priority
      
      @tasks[parent], @tasks[index] = @tasks[index], @tasks[parent]
      index = parent
    end
  end
  
  def heapify_down(index)
    loop do
      left = 2 * index + 1
      right = 2 * index + 2
      largest = index
      
      if left < @tasks.length && @tasks[left].priority > @tasks[largest].priority
        largest = left
      end
      
      if right < @tasks.length && @tasks[right].priority > @tasks[largest].priority
        largest = right
      end
      
      break if largest == index
      
      @tasks[index], @tasks[largest] = @tasks[largest], @tasks[index]
      index = largest
    end
  end
end

scheduler = TaskScheduler.new
scheduler.add_task("Deploy", 10, Time.now + 3600)
scheduler.add_task("Backup", 5, Time.now + 7200)
scheduler.add_task("Security Patch", 15, Time.now + 1800)

next_task = scheduler.get_next_task
# => Task("Security Patch", 15, ...)

Common Pitfalls

Off-by-one errors in index calculations cause frequent bugs. The parent index calculation (i - 1) / 2 uses integer division, which truncates toward zero. Calculating left and right children requires careful handling of the 2i + 1 and 2i + 2 formulas. Testing with small arrays helps catch these errors.

# INCORRECT: Using wrong index calculations
def buggy_heapify(array, index, heap_size)
  left = 2 * index        # Missing + 1
  right = 2 * index + 1   # Should be + 2
  largest = index
  
  # Will access wrong children, breaking heap property
  largest = left if left < heap_size && array[left] > array[largest]
  largest = right if right < heap_size && array[right] > array[largest]
  
  if largest != index
    array[index], array[largest] = array[largest], array[index]
    buggy_heapify(array, largest, heap_size)
  end
end

Forgetting to reduce heap size after each extraction corrupts the sort. The sorted elements must be excluded from heapify operations. Using the full array length instead of the current heap boundary causes heapify to move sorted elements back into the unsorted region.

# INCORRECT: Not reducing heap size
def incorrect_heap_sort(array)
  build_heap(array)
  
  (array.length - 1).downto(1) do |i|
    array[0], array[i] = array[i], array[0]
    # BUG: Using array.length instead of i
    heapify(array, 0, array.length)  # Should be heapify(array, 0, i)
  end
  
  array
end

Starting the build heap phase at the wrong index wastes operations or skips nodes. Leaf nodes occupy indices from n/2 to n-1 and need not be heapified. Starting at index n-1 performs unnecessary heapify calls on leaves. Starting at 0 breaks the bottom-up invariant.

Modifying comparison logic without adjusting swap logic creates subtle bugs. When implementing min heap or custom comparisons, all comparison operators must change consistently. Mixing max heap comparisons with min heap swaps produces an invalid heap.

# INCORRECT: Inconsistent comparison logic
def buggy_min_heapify(array, index, heap_size)
  left = 2 * index + 1
  right = 2 * index + 2
  smallest = index
  
  # Correct: Finding smallest
  smallest = left if left < heap_size && array[left] < array[smallest]
  smallest = right if right < heap_size && array[right] < array[smallest]
  
  if smallest != index
    # BUG: Code assumes max heap elsewhere, breaks min heap
    array[index], array[smallest] = array[smallest], array[index]
    # Recursion continues with wrong assumption
    max_heapify(array, smallest, heap_size)  # Should be min_heapify
  end
end

Stack overflow occurs with deep recursion on large arrays. The recursive heapify can reach O(log n) depth, which is safe for reasonable array sizes. However, Ruby's default stack size may limit extremely large arrays. The iterative version eliminates this concern.

Assuming heap sort is stable causes correctness issues in applications requiring stability. Two employees with equal salaries might reverse order after heap sort, violating application requirements. Testing with duplicate values reveals stability problems.

Comparing heap sort performance on small arrays against algorithms optimized for small inputs creates misleading benchmarks. Heap sort's initialization overhead dominates with n < 20. Benchmarks should test realistic array sizes where O(n log n) complexity matters.

Reference

Algorithm Complexity

Heap Index Calculations

Core Operations

Comparison with Other Sorts

Implementation Checklist

Common Method Signatures