Binaryheap

A standard binary heap data structure implementation in ruby as a gem. Internally it uses an array as data store and a mutex to keep insert and eject opeations thread-safe (both on CRuby and JRuby).

See Rubydoc

Install

gem install binaryheap

Usage

By default, an empty max heap is created:
bh = BinaryHeap.new
To create a min heap:

bh = BinaryHeap.new{|parent, child| child <=> parent}

To create from an existent array:

  array = [-2, 40, 13, 88]
  bh = BinaryHeap.new(array)
  until bh.empty?
    p bh.eject  #=> 88, 40, 13, -2
  end

You can customize a comparator which returns negative, zero or positive values based on comparision result:

  bh = BinaryHeap.new do |parent, child| 
    if parent.greater_than(child)
      1
    elsif parent.equal_to(child)
      0
    else 
      -1
    end
  end

Use insert (alias push) and eject to add into or remove element from the heap:

  bh = BinaryHeap.new
  bh.insert(-3).insert(6).insert(-5).insert(17)
  p bh.size     #=> 3
  # get the underlying array data
  p bh.data     #=> [17, 6, -5, -3]
  until bh.empty?
    p bh.eject  #=> 17, 6, -3, -5
  end

All Array methods will be forwarded to the underlying array data member:

  bh = BinaryHeap.new(10.times.map{rand (1..99)})
  p bh.size  # => 10
  p bh.first # same as bh.top, returns the biggest number in this case

Issues Report and Contribute

Please raise issues or send me pull requests.

Author

Hailong Cao ( hailengc@gmail.com | twitter )