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

3 Dec 2025

      Issue #21720 has been updated by herwin (Herwin W).

```ruby
Heap.heapify(array)
Heap.heappush(array, value)
Heap.heappop(array)
```
This looks like a very fragile API to me:
```ruby
Heap.heapify(array)
array << 'something random' # The heap is not encapsulated, so we can perform any Array operation
Heap.heappush(array, 123)   # And this probably breaks, since array is no longer a heap
```

----------------------------------------
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-115439

* 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/