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 # => 1
simple_heap.pop_with_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
returnsself
instead of the first argument -
enqueue
returnsself
instead of the first argument - Queue classes are in the
PairingHeap
namespace, sorequire 'pairing_heap
does not loadMinPriorityQueue
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.2.2 (2023-03-30 revision e51014f9c0) [x86_64-darwin22] | |||
---|---|---|---|
Library | Iterations | Seconds | Iterations per second |
pairing_heap (SimplePairingHeap) | 26 | 62.000755 | 0.420 |
pairing_heap (PairingHeap) | 17 | 61.767914 | 0.276(1.52x slower) |
rb_heap | 17 | 62.531495s | 0.272(1.54x slower) |
lazy_priority_queue | 10 | 66.576596 | 0.150(2.79x slower) |
Fibonacci | 6 | 61.606882 | 0.091(4.31x slower) |
ruby 3.2.2 (2023-03-30 revision e51014f9c0) +YJIT [x86_64-darwin22] | |||
Library | Iterations | Seconds | Iterations per second |
pairing_heap (SimplePairingHeap) | 42 | 61.170369 | 0.687 |
rb_heap | 30 | 61.266231 | 0.490(1.07x slower) |
pairing_heap (PairingHeap) | 25 | 61.409506 | 0.407(1.69x slower) |
lazy_priority_queue | 12 | 61.560478 | 0.195(3.53x slower) |
Fibonacci | 11 | 64.966138 | 0.169(4.06x slower) |
jruby 9.4.2.0 (3.1.0) 2023-03-08 90d2913fda 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) | 42 | 60.349060 | 0.696 |
rb_heap | 32 | 60.281040 | 0.515(1.35x slower) |
pairing_heap (PairingHeap) | 29 | 61.276515 | 0.474(1.47x slower) |
lazy_priority_queue | 21 | 61.679564 | 0.341(2.04x slower) |
Fibonacci | 21 | 62.166960 | 0.338(2.06x slower) |
truffleruby 22.3.1, like ruby 3.0.3, GraalVM CE JVM [x86_64-darwin] | |||
Library | Iterations | Seconds | Iterations per second |
pairing_heap (SimplePairingHeap) | 190 | 60.150795 | 3.181 |
rb_heap | 103 | 60.395842 | 1.707(1.86x slower) |
pairing_heap (PairingHeap) | 100 | 60.121239 | 1.681(1.89x slower) |
lazy_priority_queue | 20 | 62.125953 | 0.322(9.87x slower) |
Fibonacci | 8 | 60.682738 | 0.132(24.05x 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.2.2 (2023-03-30 revision e51014f9c0) [x86_64-darwin22] | |||
---|---|---|---|
Library | Iterations | Seconds | Iterations per second |
pairing_heap | 15 | 61.049572 | 0.246 |
lazy_priority_queue | 9 | 63.753290 | 0.141(1.74x slower) |
Fibonacci | 6 | 63.178331 | 0.095(2.59x slower) |
ruby 3.2.2 (2023-03-30 revision e51014f9c0) +YJIT [x86_64-darwin22] | |||
Library | Iterations | Seconds | Iterations per second |
pairing_heap | 23 | 62.450014 | 0.369 |
lazy_priority_queue | 11 | 61.411572 | 0.179(2.06x slower) |
Fibonacci | 9 | 65.088674 | 0.138(2.67x slower) |
jruby 9.4.2.0 (3.1.0) 2023-03-08 90d2913fda 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 | 61.567608 | 0.456 |
Fibonacci | 20 | 62.937410 | 0.318(1.43x slower) |
lazy_priority_queue | 19 | 61.462856 | 0.309(1.47x slower) |
truffleruby 22.3.1, like ruby 3.0.3, GraalVM CE JVM [x86_64-darwin] | |||
Library | Iterations | Seconds | Iterations per second |
pairing_heap | 90 | 60.338872 | 1.505 |
lazy_priority_queue | 24 | 60.910311 | 0.395(3.81x slower) |
Fibonacci | 9 | 65.172894 | 0.138(10.88x 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.2.2 (2023-03-30 revision e51014f9c0) [x86_64-darwin22] | |||
---|---|---|---|
Library | Iterations per second | ||
pairing_heap (PairingHeap) | 734.65 | ||
lazy_priority_queue | 386.161(1.90x slower) | ||
pairing_heap (SimplePairingHeap) | 331.9(2.21x slower) | ||
Fibonacci | 245.3(2.99x slower) | ||
rb_heap | 224.8(3.27x slower) | ||
ruby 3.2.2 (2023-03-30 revision e51014f9c0) +YJIT [x86_64-darwin22] | |||
Library | Iterations per second | ||
pairing_heap | 1295.8 | ||
pairing_heap(SimplePairingHeap) | 639.3(2.03x slower) | ||
lazy_priority_queue | 543.2(2.39x slower) | ||
rb_heap | 432(3x slower) | ||
Fibonacci | 407.4(3.18x slower) | ||
jruby 9.4.2.0 (3.1.0) 2023-03-08 90d2913fda 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) | 1469 | ||
Fibonacci | 966(1.52x slower) | ||
lazy_priority_queue | 907(1.62x slower) | ||
pairing_heap(SimplePairingHeap) | 639(2.30x slower) | ||
rb_heap | 504(2.91x slower) | ||
truffleruby 22.3.1, like ruby 3.0.3, GraalVM CE JVM [x86_64-darwin] | |||
Library | Iterations per second | ||
pairing_heap(PairingHeap) | 13943 | ||
pairing_heap(SimplePairingHeap) | 8213(1.70x slower) | ||
rb_heap | 2341(5.95x slower) | ||
Fibonacci | 1572(8.87x slower) | ||
lazy_priority_queue | 1012(13.78x slower) |
Dijkstra's algorithm with RGL source code
ruby 3.2.2 (2023-03-30 revision e51014f9c0) [x86_64-darwin22] | |||
---|---|---|---|
Library | Iterations | Seconds | Iterations per second |
pairing_heap | 10 | 60.694556 | 0.165 |
lazy_priority_queue | 9 | 63.397416 | 0.142(1.16x slower) |
Fibonacci | 7 | 67.456340 | 0.104(1.59x slower) |
ruby 3.2.2 (2023-03-30 revision e51014f9c0) +YJIT [x86_64-darwin22] | |||
Library | Iterations | Seconds | Iterations per second |
pairing_heap | 12 | 61.717338 | 0.195 |
lazy_priority_queue | 11 | 65.780856 | 0.167(1.16x slower) |
Fibonacci | 9 | 64.968622 | 0.139(1.40x slower) |
jruby 9.4.2.0 (3.1.0) 2023-03-08 90d2913fda 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 | 20 | 62.414285 | 0.321 |
lazy_priority_queue | 19 | 60.904401 | 0.313(1.03x slower) |
Fibonacci | 18 | 62.869887 | 0.287(1.12x slower) |
truffleruby 22.3.1, like ruby 3.0.3, GraalVM CE JVM [x86_64-darwin] | |||
Library | Iterations | Seconds | Iterations per second |
pairing_heap | 36 | 60.620255 | 0.599 |
lazy_priority_queue | 26 | 62.000357 | 0.422(1.42x slower) |
Fibonacci | 24 | 62.438081 | 0.520(1.52x 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.2.2 (2023-03-30 revision e51014f9c0) [x86_64-darwin22] | |||
---|---|---|---|
Library | Iterations | Seconds | Iterations per second |
pairing_heap (SimplePairingHeap) | 38 | 60.115729 | 0.633 |
pairing_heap (PairingHeap) | 32 | 60.990854 | 0.525(1.20x slower) |
rb_heap | 30 | 60.288193 | 0.498(1.27x slower) |
lazy_priority_queue | 22 | 60.345144 | 0.365(1.74x slower) |
Fibonacci | 13 | 64.820842 | 0.201(3.16x slower) |
ruby 3.2.2 (2023-03-30 revision e51014f9c0) +YJIT [x86_64-darwin22] | |||
Library | Iterations | Seconds | Iterations per second |
rb_heap | 52 | 60.764238 | 0.856 |
pairing_heap (SimplePairingHeap) | 49 | 60.242233 | 0.818(1.05x slower) |
pairing_heap (PairingHeap) | 47 | 60.176639 | 0.784(1.09x slower) |
lazy_priority_queue | 30 | 61.919103 | 0.485(1.76x slower) |
Fibonacci | 18 | 61.946877 | 0.291(2.95x slower) |
jruby 9.4.2.0 (3.1.0) 2023-03-08 90d2913fda 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 |
rb_heap | 68 | 60.677947 | 1.123 |
pairing_heap (SimplePairingHeap) | 64 | 60.885495 | 1.066(1.05x slower) |
pairing_heap (PairingHeap) | 64 | 60.928350 | 1.053(1.07x slower) |
Fibonacci | 51 | 60.930898 | 0.840(1.34x slower) |
lazy_priority_queue | 48 | 60.625907 | 0.793(1.42x slower) |
truffleruby 22.3.1, like ruby 3.0.3, GraalVM CE JVM [x86_64-darwin] | |||
Library | Iterations | Seconds | Iterations per second |
pairing_heap (SimplePairingHeap) | 282 | 60.154056 | 4.748 |
pairing_heap (PairingHeap) | 230 | 60.070466 | 3.855(1.23x slower) |
rb_heap | 214 | 60.073212 | 3.594(1.32x slower) |
Fibonacci | 68 | 60.586191 | 1.131(4.20x slower) |
lazy_priority_queue | 48 | 60.991714 | 0.788(6.03x slower) |
Summary
Change priority required
ruby 3.2.2 (2023-03-30 revision e51014f9c0) [x86_64-darwin22] | |||
---|---|---|---|
Library | Slower geometric mean | ||
pairing_heap | 1 | ||
lazy_priority_queue | 1.52x slower | ||
Fibonacci | 2.38x slower | ||
ruby 3.2.2 (2023-03-30 revision e51014f9c0) +YJIT [x86_64-darwin22] | |||
Library | Slower geometric mean | ||
pairing_heap | 1 | ||
lazy_priority_queue | 1.682x slower | ||
Fibonacci | 2.216x slower | ||
jruby 9.4.2.0 (3.1.0) 2023-03-08 90d2913fda 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 | ||
lazy_priority_queue | 1.291x slower | ||
Fibonacci | 1.295x slower | ||
truffleruby 22.3.1, like ruby 3.0.3, GraalVM CE JVM [x86_64-darwin] | |||
Library | Slower geometric mean | ||
pairing_heap | 1 | ||
lazy_priority_queue | 3.428x slower | ||
Fibonacci | 5.175x slower |
Change priority not required
ruby 3.2.2 (2023-03-30 revision e51014f9c0) [x86_64-darwin22] | |||
---|---|---|---|
Library | Slower geometric mean | ||
pairing_heap (SimplePairingHeap) | 1 | ||
pairing_heap (PairingHeap) | 1.35x slower | ||
rb_heap | 1.4x slower | ||
lazy_priority_queue | 2.2x slower | ||
Fibonacci | 3.69x slower | ||
ruby 3.2.2 (2023-03-30 revision e51014f9c0) +YJIT [x86_64-darwin22] | |||
Library | Slower geometric mean | ||
pairing_heap (SimplePairingHeap) | 1.025x slower | ||
rb_heap | 1.034x slower | ||
pairing_heap (PairingHeap) | 1.357x slower | ||
lazy_priority_queue | 2.492x slower | ||
Fibonacci | 3.46x slower | ||
jruby 9.4.2.0 (3.1.0) 2023-03-08 90d2913fda 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.024x slower | ||
rb_heap | 1.162x slower | ||
pairing_heap (PairingHeap) | 1.254x slower | ||
Fibonacci | 1.661x slower | ||
lazy_priority_queue | 1.702x slower | ||
truffleruby 22.3.1, like ruby 3.0.3, GraalVM CE JVM [x86_64-darwin] | |||
Library | Slower geometric mean | ||
pairing_heap (SimplePairingHeap) | 1 | ||
pairing_heap (PairingHeap) | 1.525x slower | ||
rb_heap | 1.567x slower | ||
lazy_priority_queue | 7.715x slower | ||
Fibonacci | 10.05x 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.