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

• Status: Open
• Assignee: -
• Target version: -

[rahulk501 (Rahul Kumar)]

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:

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:

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)

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.