PairingHeap

PairingHeap is a pure Ruby priority queue implementation using a pairing heap as the underlying data structure. While a pairing heap is asymptotically less efficient than the Fibonacci heap, it is usually faster in practice. This makes it a popular choice for Prim's MST or Dijkstra's algorithm implementations.

PairingHeap is currently being used as the priority queue data structure in RGL.

Also implementation without priority change support is provided(SimplePairingHeap), while the asymptotical complexity of the methods stay the same, bookkeeping of elements is not needed making, the constant smaller.

Installation

Add this line to your application's Gemfile:

gem 'pairing_heap'

And then execute:

$ bundle install

Or install it yourself as:

$ gem install pairing_heap

Documentation

https://rubydoc.info/gems/pairing_heap

Usage

require 'pairing_heap'

# Simple PairingHeap
simple_heap = PairingHeap::SimplePairingHeap.new
simple_heap.push(:a, 1)
simple_heap.push(:b, 2)
simple_heap.push(:c, 3)
simple_heap.peek # => :a
simple_heap.peek_priority # => [:a, 1]
simple_heap.pop_priority # => [:a, 1]
simple_heap.pop # => :b

# Min priority queue
best_defenses = PairingHeap::MinPriorityQueue.new
best_defenses.push('Chelsea', 24)
best_defenses.push('City', 30)
best_defenses.push('Tottenham', 25)
best_defenses.any? # => true
best_defenses.size # => 3
best_defenses.decrease_key('City', 15)
best_defenses.min # => 'City'
best_defenses.pop # => 'City'
best_defenses.extract_min # => 'Chelsea'
best_defenses.extract_min # => 'Tottenham'
best_defenses.any? # => false

# Max priority queue
best_teams = PairingHeap::MaxPriorityQueue.new
best_teams.push('City', 56)
best_teams.push('United', 46)
best_teams.push('Leicester', 46)
best_teams.increase_key('Leicester', 47)
best_teams.max # => 'City'
best_teams.pop # => 'City'
best_teams.extract_max # => 'Leicester'

# Custom comparator(it defaults to :<=.to_proc)
compare_by_length = PairingHeap::PairingHeap.new { |l, r| l.length <= r.length }
compare_by_length.push(:a, '11')
compare_by_length.push(:b, '1')
compare_by_length.push(:c, '11')
compare_by_length.change_priority(:c, '')
compare_by_length.peek # => :c
compare_by_length.pop # => :c
compare_by_length.pop # => :b
compare_by_length.pop # => :a

# SafeChangePriortyQueue
queue = PairingHeap::SafeChangePriorityQueue.new
queue.push(:a, 1)
queue.push(:b, 2)
queue.change_priority(:a, 3) # This works and does not throw an exception
queue.peek # => :b

See also test/performance_dijkstra.rb for a Dijkstra algorithm implementation.

Changes from lazy_priority_queue

This API is a drop-in replacement of lazy_priority_queue with the following differences:

  • Custom comparator provided to constructur, compares weights, not internal nodes
  • change_priority returns self instead of the first argument
  • enqueue returns self instead of the first argument
  • Queue classes are in the PairingHeap namespace, so require 'pairing_heap does not load MinPriorityQueue to the global scope
  • top_condition constructor argument is removed

Time Complexity

Operation Time complexity Amortized time complexity
enqueue O(1) O(1)
peek O(1) O(1)
dequeue O(n) O(log n)
* change_priority O(1) o(log n)
* delete O(n) O(log n)

* Not available in SimplePairingHeap

Benchmarks

I picked the three fastest pure Ruby priority queue implementations I was aware of for the comparison:

  • lazy_priority_queue that uses a lazy binomial heap. This is probably the most popular option. It was used in RGL until PairingHeap replaced it.
  • Pure Ruby implementation of Fibonacci Heap from priority-queue (link to source)
  • rb_heap that uses a binary heap. Note however that this implementation does not support change_priority operation.

All tests except for the third one were executed by benchmark-ips with parameters time = 60 and warmup = 15, on an Intel(R) Core(TM) i7-10700K CPU @ 3.80GHz.

Stress test without changing priority test(N = 1000) source code

Original performance test from lazy_priority_queue

A stress test of 1,000,000 operations: starting with 1,000 pushes/0 pops, following 999 pushes/1 pop, and so on till 0 pushes/1000 pops.

ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) [x86_64-darwin21]
Library Iterations Seconds Iterations per second
pairing_heap (SimplePairingHeap) 23 62.014773 0.371
pairing_heap (PairingHeap) 16 63.135240 0.253(1.46x slower)
rb_heap 14 61.123304 0.229(1.62x slower)
lazy_priority_queue 10 66.208647 0.151(2.46x slower)
Fibonacci 8 66.353147 0.121(3.08x slower)
ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) +YJIT [x86_64-darwin21]
Library Iterations Seconds Iterations per second
pairing_heap (SimplePairingHeap) 25 60.423579 0.414
rb_heap 19 60.869907 0.312(1.33x slower)
pairing_heap (PairingHeap) 17 61.389127 0.277(1.49x slower)
Fibonacci 14 64.417807 0.217(1.90x slower)
lazy_priority_queue 11 63.151856 0.174(2.38x slower)
jruby 9.3.7.0 (2.6.8) 2022-08-16 c79ef237e0 OpenJDK 64-Bit Server VM 17.0.2+8-86 on 17.0.2+8-86 +indy +jit [x86_64-darwin]
Library Iterations Seconds Iterations per second
pairing_heap (SimplePairingHeap) 47 60.391633 0.778
rb_heap 34 60.878639 0.559(1.39x slower)
pairing_heap (PairingHeap) 32 61.211985 0.523(1.49x slower)
Fibonacci 23 60.297670 0.382(2.04x slower)
lazy_priority_queue 23 61.973538 0.371(2.10x slower)
truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE JVM [x86_64-darwin]
Library Iterations Seconds Iterations per second
pairing_heap (SimplePairingHeap) 206 60.191686 3.433
rb_heap 97 60.134011 1.614(1.93x slower)
pairing_heap (PairingHeap) 85 60.193608s 1.434(2.40x slower)
lazy_priority_queue 19 63.212429 0.301(11.45x slower)
Fibonacci 2 83.508571 0.024(143.70x slower)

Stress test with changing priority(N = 1000) source code

A stress test of 1,501,500 operations: starting with 1,000 pushes/1000 change_priorities/0 pops, following 999 pushes/999 change_priorities/1 pop, and so on till 0 pushes/0 change_priorities/1000 pops.

ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) [x86_64-darwin21]
Library Iterations Seconds Iterations per second
pairing_heap 15 62.946988 0.238
lazy_priority_queue 9 61.876691 0.145(1.64x slower)
Fibonacci 8 67.809982 0.118(2.02x slower)
ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) +YJIT [x86_64-darwin21]
Library Iterations Seconds Iterations per second
pairing_heap 16 62.576693 0.256
Fibonacci 13 63.164614 0.206(1.24x slower)
lazy_priority_queue 10 63.172995s 0.158(1.62x slower)
jruby 9.3.7.0 (2.6.8) 2022-08-16 c79ef237e0 OpenJDK 64-Bit Server VM 17.0.2+8-86 on 17.0.2+8-86 +indy +jit [x86_64-darwin]
Library Iterations Seconds Iterations per second
pairing_heap 28 60.280368 0.465
Fibonacci 22 61.405561 0.465(1.30x slower)
lazy_priority_queue 20 60.397535 0.331(1.40x slower)
truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE JVM [x86_64-darwin]
Library Iterations Seconds Iterations per second
pairing_heap 70 60.663184 1.160
lazy_priority_queue 23 60.474587 0.382(3.04x slower)
Fibonacci 2 74.873854 0.027(43.44x slower)

Stress test with changing priority or push/pop(test ignored in summary) source code

Start with 500 pushes, then:

  • If queue supports changing priority 500 change_priority calls, then 500 pops
  • If does not support changing priority 500 push calls, then 1000 pops
    ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) [x86_64-darwin21]
    Library Iterations per second
    pairing_heap (PairingHeap) 436.4
    lazy_priority_queue 380.2(1.94x slower)
    pairing_heap (SimplePairingHeap) 339.9.02(2.17x slower)
    Fibonacci 313.9(2.35x slower)
    rb_heap 194.7(3.78 slower)
    ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) +YJIT [x86_64-darwin21]
    Library Iterations per second
    pairing_heap 854.6
    Fibonacci 651.3(1.31x slower)
    lazy_priority_queue 453.6(1.88x slower)
    pairing_heap(SimplePairingHeap) 390.9(2.19x slower)
    rb_heap 268.8(3.18x slower)
    jruby 9.3.7.0 (2.6.8) 2022-08-16 c79ef237e0 OpenJDK 64-Bit Server VM 17.0.2+8-86 on 17.0.2+8-86 +indy +jit [x86_64-darwin]
    Library Iterations per second
    pairing_heap(PairingHeap) 1591
    Fibonacci 1092(1.46x slower)
    lazy_priority_queue 986(1.61x slower)
    pairing_heap(SimplePairingHeap) 562(2.37x slower)
    rb_heap 623(2.55x slower)
    truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE JVM [x86_64-darwin]
    Library Iterations per second
    pairing_heap(PairingHeap) 7404
    pairing_heap(SimplePairingHeap) 5104(1.45x slower)
    rb_heap 1575(4.70x slower)
    Fibonacci 1258(5.88x slower)
    lazy_priority_queue 1004(7.38x slower)

Dijkstra's algorithm with RGL source code

ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) [x86_64-darwin21]
Library Iterations Seconds Iterations per second
pairing_heap 9 61.469343 0.116
lazy_priority_queue 8 64.312672 0.125(1.18x slower)
Fibonacci 7 60.555716 0.116(1.27x slower)
ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) +YJIT [x86_64-darwin21]
Library Iterations Seconds Iterations per second
pairing_heap 10 65.160945s 0.154
Fibonacci 9 61.950587 0.145(1.06x slower)
lazy_priority_queue 9 66.592123 0.135(1.14x slower)
jruby 9.3.7.0 (2.6.8) 2022-08-16 c79ef237e0 OpenJDK 64-Bit Server VM 17.0.2+8-86 on 17.0.2+8-86 +indy +jit [x86_64-darwin]
Library Iterations Seconds Iterations per second
lazy_priority_queue 20 61.149944 0.328
pairing_heap 20 61.210225s 0.328
Fibonacci 18 62.330882 0.292(1.12x slower)
truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE JVM [x86_64-darwin]
Library Iterations Seconds Iterations per second
pairing_heap 59 60.053843 0.991
lazy_priority_queue 34 60.586461 0.563(1.76x slower)
Fibonacci 31 60.633711 0.520(1.90x slower)

Simple Dijkstra's algorithm implementation source code

Heaps that support change_priority operation use it. Heaps that do not support it use dijkstra implementation that do not rely on change_priority instead and do additional pops and pushes instead(see Dijkstra-NoDec from Priority Queues and Dijkstra’s Algorithm).

ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) [x86_64-darwin21]
Library Iterations Seconds Iterations per second
pairing_heap (SimplePairingHeap) 28 62.100299 0.451
pairing_heap (PairingHeap) 23 60.633153 0.380(1.19x slower)
rb_heap 14 62.019763 0.226(2.00x slower)
lazy_priority_queue 11 63.105064s 0.174(2.58x slower)
Fibonacci 10 64.407187 0.155(2.90x slower)
ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) +YJIT [x86_64-darwin21]
Library Iterations Seconds Iterations per second
pairing_heap (SimplePairingHeap) 32 61.289321 0.522
pairing_heap (PairingHeap) 26 60.657625 0.429(1.22x slower)
rb_heap 19 60.710888s 0.313(1.67x slower)
Fibonacci 19 61.471203 0.310(1.69x slower)
lazy_priority_queue 12 60.125779 0.200(2.61x slower)
jruby 9.3.7.0 (2.6.8) 2022-08-16 c79ef237e0 OpenJDK 64-Bit Server VM 17.0.2+8-86 on 17.0.2+8-86 +indy +jit [x86_64-darwin]
Library Iterations Seconds Iterations per second
pairing_heap (SimplePairingHeap) 46 61.226924 0.753
rb_heap 38 60.563995 0.628(1.20x slower)
pairing_heap (PairingHeap) 37 60.928350 0.608(1.24x slower)
Fibonacci 28 61.136970 0.461(1.63x slower)
lazy_priority_queue 22 62.214796 0.354(2.13x slower)
truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE JVM [x86_64-darwin]
Library Iterations Seconds Iterations per second
pairing_heap (SimplePairingHeap) 176 60.029817 3.006
pairing_heap (PairingHeap) 124 60.366607 2.078(1.45x slower)
rb_heap 95 60.021043 1.585(1.90x slower)
Fibonacci 38 60.020976 0.636(4.72x slower)
lazy_priority_queue 27 61.349925 0.445(6.75x slower)

Summary

Change priority required

ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) [x86_64-darwin21]
Library Slower geometric mean
pairing_heap 1
lazy_priority_queue 1.688x slower
Fibonacci 1.987x slower
ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) +YJIT [x86_64-darwin21]
Library Slower geometric mean
pairing_heap 1
Fibonacci 1.256x slower
lazy_priority_queue 1.648x slower
jruby 9.3.7.0 (2.6.8) 2022-08-16 c79ef237e0 OpenJDK 64-Bit Server VM 17.0.2+8-86 on 17.0.2+8-86 +indy +jit [x86_64-darwin]
Library Slower geometric mean
pairing_heap 1
Fibonacci 1.327x slower
lazy_priority_queue 1.383x slower
truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE JVM [x86_64-darwin]
Library Slower geometric mean
pairing_heap 1
lazy_priority_queue 3.878x slower
Fibonacci 9.889x slower

Change priority not required

ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) [x86_64-darwin21]
Library Slower geometric mean
pairing_heap (SimplePairingHeap) 1
pairing_heap (PairingHeap) 1.318x slower
rb_heap 1.8x slower
lazy_priority_queue 2.519x slower
Fibonacci 2.989x slower
ruby 3.1.2p20 (2022-04-12 revision 4491bb740a) +YJIT [x86_64-darwin21]
Library Slower geometric mean
pairing_heap (SimplePairingHeap) 1
pairing_heap (PairingHeap) 1.348x slower
rb_heap 1.490x slower
Fibonacci 1.792x slower
lazy_priority_queue 2.492x slower
jruby 9.3.7.0 (2.6.8) 2022-08-16 c79ef237e0 OpenJDK 64-Bit Server VM 17.0.2+8-86 on 17.0.2+8-86 +indy +jit [x86_64-darwin]
Library Slower geometric mean
pairing_heap (SimplePairingHeap) 1
rb_heap 1.292x slower
pairing_heap (PairingHeap) 1.359x slower
lazy_priority_queue 2.115x slower
Fibonacci 1.824x slower
truffleruby 22.2.0, like ruby 3.0.3, GraalVM CE JVM [x86_64-darwin]
Library Slower geometric mean
pairing_heap (SimplePairingHeap) 1
pairing_heap (PairingHeap) 1.865x slower
rb_heap 1.915x slower
lazy_priority_queue 8.791x slower
Fibonacci 26.044x slower

Development

After checking out the repo, run bin/setup to install dependencies. Then, run rake test to run the tests. You can also run bin/console for an interactive prompt that will allow you to experiment.

To install this gem onto your local machine, run bundle exec rake install. To release a new version, update the version number in version.rb, and then run bundle exec rake release, which will create a git tag for the version, push git commits and the created tag, and push the .gem file to rubygems.org.

Contributing

Bug reports and pull requests are welcome on GitHub at https://github.com/mhib/pairing_heap.

License

The gem is available as open source under the terms of the MIT License.