[ruby-core:123958] [Ruby Feature#21720] Add a native Binary Heap / Priority Queue to Ruby's Standard Library (heapify, heappush, heappop)
Issue #21720 has been reported by rahulk501 (Rahul Kumar). ---------------------------------------- Feature #21720: Add a native Binary Heap / Priority Queue to Ruby's Standard Library (heapify, heappush, heappop) https://bugs.ruby-lang.org/issues/21720 * 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/
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/
Issue #21720 has been updated by rahulk501 (Rahul Kumar). herwin (Herwin W) wrote in #note-1:
```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 ```
------------------------------------------------------------ ### Update (response to feedback) Thank you for pointing out the fragility of the module-style API that operates directly on a plain `Array`. I agree that exposing the raw array makes it easy to break the heap by performing unrelated operations on it. To avoid this issue, I'm happy to move the proposal toward an encapsulated class-based design, e.g.: ```ruby heap = Heap.new([3, 1, 4]) heap.push(2) heap.pop ``` This avoids accidental misuse and keeps the internal structure consistent. To refine the proposal correctly, I would appreciate guidance on two specific points: **1. Would a dedicated class name like `Heap` or `BinaryHeap` be preferred for the standard library? 2. Should the initial implementation support only a `min-heap`, or should support for `max-heaps` be included as well?** I’m happy to adjust the proposal based on whichever direction aligns best with Ruby’s design principles. ---------------------------------------- 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-115487 * 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/
participants (2)
-
herwin (Herwin W) -
rahulk501 (Rahul Kumar)