[ruby-core:125697] [Ruby Feature#21720] Add a native Binary Heap / Priority Queue to Ruby's Standard Library (heapify, heappush, heappop)

11 Jun 2026

      Issue #21720 has been updated by matz (Yukihiro Matsumoto).

I agree that a binary heap and priority queue are useful, but I’m not sure whether they should be included in the standard library rather than as gems. Shouldn’t they first be released as gems to gauge the community’s response?

Matz.

----------------------------------------
Feature #21720: Add a native Binary Heap / Priority Queue to Ruby's Standard Library (heapify, heappush, heappop)
https://bugs.ruby-lang.org/issues/21720#change-117558

* Author: rahulk501 (Rahul Kumar)
* Status: Open
----------------------------------------

**Title:** Add a native Binary Heap / Priority Queue to Ruby's Standard Library (`heapify`, `heappush`, `heappop`)

**Problem**

Ruby currently lacks a native binary heap / priority queue data structure in the standard library.
Users frequently reimplement heaps manually, or install third-party gems, simply to access common operations such as:

* `heapify`
* `heappush`
* `heappop`
* efficient priority queues

Meanwhile, languages like Python provide a standard `heapq` module which is widely used in algorithms, AI, scheduling, job queues, pathfinding, graph traversal, and competitive programming.

Because Ruby does not include a heap implementation, developers often write ad-hoc, buggy, or inconsistent versions of a heap. This leads to fragmentation and duplication.

**Proposal**

Introduce a lightweight `Heap` or `BinaryHeap` class to Ruby’s standard library with the following minimal API:

```ruby
heap = Heap.new(array = [])
heap.push(value)
heap.pop       # returns smallest (min-heap)
heap.peek
heap.size
```

Or a module-based functional API similar to Python’s `heapq`:

```ruby
Heap.heapify(array)
Heap.heappush(array, value)
Heap.heappop(array)
```

Both designs are simple and allow backward-compatible extension.

**Why include it in the standard library?**

1. Heaps are a *fundamental data structure*—used in sorting, algorithms, scheduling, and timers.
2. Many languages include them natively (Python, C++ via STL `priority_queue`, Java, Go, Rust `BinaryHeap`).
3. Adding it reduces unnecessary reimplementations in user codebases.
4. A small heap implementation adds little maintenance burden.
5. Existing Ruby solutions (gems like `algorithms`, `priority_queue`, custom code) are not universally available and often exceed what users need.

**Reference Implementation (pure Ruby, minimal example)**

```ruby
module Heap
  def self.heapify(arr)
    (arr.length / 2 - 1).downto(0) { |i| sift_down(arr, i) }
    arr
  end

  def self.heappush(arr, value)
    arr << value
    sift_up(arr, arr.length - 1)
  end

  def self.heappop(arr)
    return nil if arr.empty?
    arr[0], arr[-1] = arr[-1], arr[0]
    min = arr.pop
    sift_down(arr, 0)
    min
  end

  def self.sift_up(arr, i)
    while i > 0
      p = (i - 1) / 2
      break if arr[p] <= arr[i]
      arr[p], arr[i] = arr[i], arr[p]
      i = p
    end
  end

  def self.sift_down(arr, i)
    n = arr.length
    loop do
      left = 2 * i + 1
      right = 2 * i + 2
      smallest = i

      smallest = left if left < n && arr[left] < arr[smallest]
      smallest = right if right < n && arr[right] < arr[smallest]

      break if smallest == i
      arr[i], arr[smallest] = arr[smallest], arr[i]
      i = smallest
    end
  end

  private_class_method :sift_up, :sift_down
end

```

**Optional C implementation**

If accepted, I am willing to provide a minimal C version for performance parity with other stdlib containers.

**Compatibility**

No breaking changes expected.
Naming avoids conflict with existing libraries.

**Conclusion**

Adding a tiny, well-defined heap structure would strengthen Ruby’s built-in algorithmic tools, reduce duplicated code across the ecosystem, and align Ruby with other mainstream languages.

-- 
https://bugs.ruby-lang.org/