MinMax Heap

The MinMax Heap gem provides a high-performance minmax heap implementation for Ruby, written in Rust. The gem wraps the excellent min-max-heap-rs Rust library. It allows for the creation of a min-max-heap and supporting operations like pushing and popping multiple items, iterating over heap items, and converting heaps to arrays.

• MinMax heap implementation.
• Sorts according to #priority or #to_i by default. Can be overridden using a custom priority block.
• Efficient push and pop operations for single or multiple items.
• Iteration support with #each.
• Convert heap to array with #to_a, #to_a_asc and #to_a_desc.

• You must have a working Rust compiler installed on your system.

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs |

Add this line to your application's Gemfile:

gem 'min_max'

And then execute:

bundle install

Or install it yourself as:

gem install min_max

# or manually specify target . E.g.

CARGO_BUILD_TARGET=x86_64-apple-darwin gem install min_max

Instantiate a heap

heap = MinMax.new
# Alternate syntax
heap = MinMax[6,3,2,6]

# Custom priority block
heap = MinMax.new{|x| -x }
heap = MinMax[1,4,5,-43]{|x| -x }

heap.push(5, 3, 7, 1)

heap.pop_max    # => 7
heap.pop_min(3) # => [1, 3, 5]

heap.each.with_index { |item, i| puts "#{i}: #{item}" }

heap.to_a_asc  # => [1, 3, 5]
heap.to_a_desc # => [5, 3, 1]
heap.to_a # => Heap order

heap.each_asc   #<Enumerator: ...>
heap.each_desc  #<Enumerator: ...>

heap.peek_min # => 1
heap.first # => 1

heap.peek_max # => 1
heap.last # => 1

heap.size # => 4
heap.length # Alias for size

heap.clear

heap.count(item)

heap.contains?(item)

You can run the benchmarks/benchmarks.rb file inside this repository for comparison to other popular heap libraries:

• rb_heap
• algorithms
• ruby-heap
• pqueue

min-max should be the fastest to pop from a large heap, often by a significant margin, while also offering both min and max operations from a single heap. Some options are faster at pushing individual items, but the difference is within the same order of magnitude. Batch pushing to min-max also significantly increases insert speed.