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



  gem install binaryheap


By default, an empty max binary heap is created: bh = To create a min binary heap: bh ={|parent, child| child <=> parent} You can assign a self-defined comparator which returns negative, zero or positive values based on comparision result: bh = 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 = bh.insert(-3).insert(6).insert(-5).insert(17) p bh.size #=> 3 # get the underlying array data p #=> [17, 6, -5, -3] until bh.empty? p bh.eject #=> 17, 6, -3, -5 end You can also create a binary heap based on existent array data: array = [-2, 40, 13, 88] bh = until bh.empty? p bh.eject #=> 88, 40, 13, -2 end All array methods will be forwarded to the underlying array data member: bh ={rand (1..99)}) p bh.size # => 10 p bh.first # same as, returns the biggest number in this case


Find the kth max element in an array: ``` def find_kth_max(array, k) return nil if k<1 || array.size<k

bh =
i = 0
until bh.size == k
  i += 1

unless i == array.size
  (i..array.size-1).each do |j|
    e = array[j]
    if e <
      # Instead of using insert and eject which automatically adjust the heap, you can fully control the heap operation:
      # step 1: replace the root (max/min) = e
      # step 2: adjust the heap with direction (:top_down or :bottom_up) 

end ```

Issues Report and Contribute

Please raise issues or send me pull requests.


Hailong Cao ( | twitter )

License and Copyrights

MIT License
Copyright (c) 2017 Hailong Cao