You've likely dealt with sorting arrays, but there are times when you don't need a fully sorted list—you just need to be able to grab the smallest (or largest) item quickly and efficiently. That's where a Min-Heap comes in. It's the backbone of priority queues and algorithms like Dijkstra's. Let's get into how to actually build one in Ruby.

Why use an array instead of a tree of objects?

When people first think of a heap, they imagine a binary tree with nodes and pointers. While that works, it's overkill and slow in Ruby. Because a heap is a "complete" binary tree, we can map it perfectly onto a standard array. I always recommend this approach because it keeps the memory footprint low and the access speeds high.

Here is the mental model for the indexing: if an element is at index i, its left child is always at 2i + 1, its right child is at 2i + 2, and its parent is at (i - 1) / 2. It feels like magic the first time you see it, but it's just basic arithmetic that saves us from creating hundreds of Node objects.

How do I actually implement the "bubble up" and "bubble down" logic?

The core of a Min-Heap is maintaining the "heap property": every parent must be smaller than or equal to its children. When you add an element, you break that rule, so you have to "bubble it up" to its rightful place. When you remove the root, you move the last element to the top and "bubble it down."

Here is a clean implementation. I've used a private swap method to keep the logic readable, as Ruby's parallel assignment makes this incredibly concise.

class MinHeap
  def initialize
    @heap = []
  end

  def push(value)
    @heap << value
    bubble_up(@heap.size - 1)
  end

  def pop
    return nil if @heap.empty?
    
    # Swap the root with the last element, then remove the root
    swap(0, @heap.size - 1)
    min = @heap.pop
    bubble_down(0)
    min
  end

  def peek
    @heap[0]
  end

  private

  def bubble_up(index)
    parent_idx = (index - 1) / 2
    return if index <= 0 || @heap[parent_idx] <= @heap[index]

    swap(index, parent_idx)
    bubble_up(parent_idx)
  end

  def bubble_down(index)
    left_child_idx = 2 * index + 1
    right_child_idx = 2 * index + 2
    smallest = index

    if left_child_idx < @heap.size && @heap[left_child_idx] < @heap[smallest]
      smallest = left_child_idx
    end

    if right_child_idx < @heap.size && @heap[right_child_idx] < @heap[smallest]
      smallest = right_child_idx
    end

    if smallest != index
      swap(index, smallest)
      bubble_down(smallest)
    end
  end

  def swap(i, j)
    @heap[i], @heap[j] = @heap[j], @heap[i]
  end
end

What happens if I want to store objects instead of just numbers?

In a real project, you're rarely storing raw integers. You're probably storing Task objects or NetworkPacket objects. To handle this, you can't just use the < operator unless your objects implement the Comparable module.

If you don't want to mess with the class definition of the objects you're storing, I suggest passing a block to the initialize method or defining a priority method on your objects. For example, if you're building a task scheduler, your Task object might have a priority attribute. You would then replace @heap[index] with @heap[index].priority inside the bubble_up and bubble_down methods.

Just a heads-up: if two items have the same priority, the heap doesn't guarantee "first-in, first-out" order. If you need that, you'll need to add a secondary timestamp or counter to your priority comparison.

📋 Practical Task

Build a Priority-Based Event Processor

Now it's your turn. Imagine you are building a system that processes system events. Some events are "Critical" (Priority 1), some are "Warning" (Priority 2), and some are "Info" (Priority 3). You need to ensure that Critical events are always processed before Warning events, regardless of the order they arrived in.

• Create an Event class that has a name (string) and a priority (integer).
• Modify the MinHeap implementation from the lesson so that it stores Event objects but compares them based on their priority attribute.
• Implement a method process_next_event that pops the highest priority event (the lowest number) from the heap and prints: "Processing [Event Name] with priority [Priority]".
• Test your implementation by pushing 5 events in random order (e.g., an "Info" event, then a "Critical" event, then a "Warning" event) and popping them one by one to verify they come out in the correct priority order.