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.
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
https://rubydoc.info/gems/pairing_heap
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.
This API is a drop-in replacement of lazy_priority_queue with the following differences:
change_priority returns self instead of the first argumentenqueue returns self instead of the first argumentPairingHeap namespace, so require 'pairing_heap does not load MinPriorityQueue to the global scopetop_condition constructor argument is removed| 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) |
| ^ merge | O(1) | O(1) |
* Not available in SimplePairingHeap
^ Only available in SimplePairingHeap
I picked the three fastest pure Ruby priority queue implementations I was aware of for the comparison:
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.
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.3.0 (2023-12-25 revision 5124f9ac75) [x86_64-darwin23] | |||
|---|---|---|---|
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap (SimplePairingHeap) | 26 | 62.249427 | 0.419 |
| pairing_heap (PairingHeap) | 17 | 61.624806 | 0.276(1.52x slower) |
| rb_heap | 16 | 63.656502 | 0.251(1.67x slower) |
| lazy_priority_queue | 7 | 63.339192 | 0.111(3.79x slower) |
| Fibonacci | 5 | 69.010737 | 0.073(5.77x slower) |
| ruby 3.3.0 (2023-12-25 revision 5124f9ac75) +YJIT [x86_64-darwin23] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap (SimplePairingHeap) | 39 | 60.725689 | 0.642 |
| rb_heap | 31 | 60.370348 | 0.514(1.25x slower) |
| pairing_heap (PairingHeap) | 25 | 62.269577 | 0.402(1.6x slower) |
| lazy_priority_queue | 9 | 62.144710 | 0.145(4.43x slower) |
| Fibonacci | 8 | 65.064385 | 0.123(5.22x slower) |
| jruby 9.4.5.0 (3.1.4) 2023-11-02 1abae2700f OpenJDK 64-Bit Server VM 21+35-2513 on 21+35-2513 +indy +jit [x86_64-darwin] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap (SimplePairingHeap) | 43 | 60.734661 | 0.709 |
| rb_heap | 34 | 61.677228 | 0.552(1.28x slower) |
| pairing_heap (PairingHeap) | 28 | 61.284382 | 0.458(1.55x slower) |
| Fibonacci | 22 | 61.396897 | 0.359(1.97x slower) |
| lazy_priority_queue | 20 | 61.841463 | 0.324(2.19x slower) |
| truffleruby 23.1.2, like ruby 3.2.2, Oracle GraalVM JVM [x86_64-darwin] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap (SimplePairingHeap) | 202 | 60.225639 | 3.388 |
| rb_heap | 140 | 60.190881 | 2.357(1.44x slower) |
| pairing_heap (PairingHeap) | 100 | 60.373610 | 1.692(2x slower) |
| lazy_priority_queue | 31 | 61.179244 | 0.510(6.65x slower) |
| Fibonacci | 11 | 64.413419 | 0.171(19.81x slower) |
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.3.0 (2023-12-25 revision 5124f9ac75) [x86_64-darwin23] | |||
|---|---|---|---|
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap | 15 | 60.817878 | 0.247 |
| lazy_priority_queue | 7 | 63.990376s | 0.109(2.26x slower) |
| Fibonacci | 5 | 70.148980s | 0.071(3.47x slower) |
| ruby 3.3.0 (2023-12-25 revision 5124f9ac75) +YJIT [x86_64-darwin23] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap | 22 | 62.429264 | 0.353 |
| lazy_priority_queue | 9 | 63.464818 | 0.142(2.49x slower) |
| Fibonacci | 8 | 67.908812 | 0.118(2.99x slower) |
| jruby 9.4.5.0 (3.1.4) 2023-11-02 1abae2700f OpenJDK 64-Bit Server VM 21+35-2513 on 21+35-2513 +indy +jit [x86_64-darwin] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap | 27 | 61.709517 | 0.438 |
| Fibonacci | 20 | 61.495636 | 0.326(1.34x slower) |
| lazy_priority_queue | 19 | 63.401601 | 0.309(1.46x slower) |
| truffleruby 23.1.2, like ruby 3.2.2, Oracle GraalVM JVM [x86_64-darwin] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap | 93 | 60.125750 | 1.577 |
| lazy_priority_queue | 26 | 62.372660s | 0.419(3.77x slower) |
| Fibonacci | 11 | 62.620172s | 0.177(8.92x slower) |
Start with 500 pushes, then:
| ruby 3.3.0 (2023-12-25 revision 5124f9ac75) [x86_64-darwin23] | |
|---|---|
| Library | Iterations per second |
| pairing_heap (PairingHeap) | 748.9 |
| lazy_priority_queue | 388.6(1.93x slower) |
| pairing_heap (SimplePairingHeap) | 336.2(2.23x slower) |
| Fibonacci | 225.9(3.31x slower) |
| rb_heap | 215.2(3.48x slower) |
| ruby 3.3.0 (2023-12-25 revision 5124f9ac75) +YJIT [x86_64-darwin23] | |
| Library | Iterations per second |
| pairing_heap | 1276 |
| pairing_heap(SimplePairingHeap) | 625.6(2.04x slower) |
| lazy_priority_queue | 533.36(2.39x slower) |
| Fibonacci | 495.519(2.57x slower) |
| rb_heap | 453.323(2.81x slower) |
| jruby 9.4.5.0 (3.1.4) 2023-11-02 1abae2700f OpenJDK 64-Bit Server VM 21+35-2513 on 21+35-2513 +indy +jit [x86_64-darwin] | |
| Library | Iterations per second |
| pairing_heap(PairingHeap) | 1377 |
| Fibonacci | 1088(1.27x slower) |
| lazy_priority_queue | 953.935(1.44x slower) |
| pairing_heap(SimplePairingHeap) | 621.35(2.22x slower) |
| rb_heap | 595.11(2.31x slower) |
| truffleruby 23.1.2, like ruby 3.2.2, Oracle GraalVM JVM [x86_64-darwin] | |
| Library | Iterations per second |
| pairing_heap(PairingHeap) | 12712 |
| pairing_heap(SimplePairingHeap) | 9447(1.35x slower) |
| rb_heap | 4009(3.17x slower) |
| Fibonacci | 2793(4.55x slower) |
| lazy_priority_queue | 1188(10.7x slower) |
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.3.0 (2023-12-25 revision 5124f9ac75) [x86_64-darwin23] | |||
|---|---|---|---|
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap (SimplePairingHeap) | 41 | 60.100316 | 0.682 |
| pairing_heap (PairingHeap) | 38 | 61.003607 | 0.623(1.09x slower) |
| rb_heap | 30 | 61.486216 | 0.488(1.40x slower) |
| lazy_priority_queue | 23 | 60.251764 | 0.382(1.79x slower) |
| Fibonacci | 13 | 61.158622 | 0.213(3.21x slower) |
| ruby 3.3.0 (2023-12-25 revision 5124f9ac75) +YJIT [x86_64-darwin23] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap (SimplePairingHeap) | 65 | 60.805882 | 1.070 |
| pairing_heap (PairingHeap) | 60 | 60.790842 | 0.987(1.08x slower) |
| rb_heap | 54 | 60.917679 | 0.887(1.21x slower) |
| lazy_priority_queue | 30 | 60.712786 | 0.495(2.16x slower) |
| Fibonacci | 24 | 61.900715 | 0.388(2.76x slower) |
| jruby 9.4.5.0 (3.1.4) 2023-11-02 1abae2700f OpenJDK 64-Bit Server VM 21+35-2513 on 21+35-2513 +indy +jit [x86_64-darwin] | |||
| Library | Iterations | Seconds | Iterations per second |
| rb_heap | 70 | 60.077928 | 1.168 |
| pairing_heap (SimplePairingHeap) | 66 | 60.420935 | 1.094(1.07x slower) |
| pairing_heap (PairingHeap) | 64 | 60.114467 | 1.066(1.1x slower) |
| Fibonacci | 54 | 60.426971 | 0.898(1.30x slower) |
| lazy_priority_queue | 49 | 60.636963 | 0.809(1.44x slower) |
| truffleruby 23.1.2, like ruby 3.2.2, Oracle GraalVM JVM [x86_64-darwin] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap (SimplePairingHeap) | 288 | 60.102278 | 4.936 |
| pairing_heap (PairingHeap) | 232 | 60.159057 | 3.936(1.25x slower) |
| rb_heap | 227 | 60.082482 | 3.881(1.27x slower) |
| Fibonacci | 101 | 60.076691 | 1.721(2.87x slower) |
| lazy_priority_queue | 66 | 60.771569 | 1.1(4.49x slower) |
| ruby 3.3.0 (2023-12-25 revision 5124f9ac75) [x86_64-darwin23] | |
|---|---|
| Library | Slower geometric mean |
| pairing_heap | 1 |
| lazy_priority_queue | 2.1x slower |
| Fibonacci | 3.38x slower |
| ruby 3.3.0 (2023-12-25 revision 5124f9ac75) +YJIT [x86_64-darwin23] | |
| Library | Slower geometric mean |
| pairing_heap | 1 |
| lazy_priority_queue | 2.55x slower |
| Fibonacci | 2.74x slower |
| jruby 9.4.5.0 (3.1.4) 2023-11-02 1abae2700f OpenJDK 64-Bit Server VM 21+35-2513 on 21+35-2513 +indy +jit [x86_64-darwin] | |
| Library | Slower geometric mean |
| pairing_heap | 1 |
| Fibonacci | 1.267x slower |
| lazy_priority_queue | 1.396x slower |
| truffleruby 23.1.2, like ruby 3.2.2, Oracle GraalVM JVM [x86_64-darwin] | |
| Library | Slower geometric mean |
| pairing_heap | 1 |
| lazy_priority_queue | 3.54x slower |
| Fibonacci | 5.86x slower |
| ruby 3.3.0 (2023-12-25 revision 5124f9ac75) [x86_64-darwin23] | |
|---|---|
| Library | Slower geometric mean |
| pairing_heap (SimplePairingHeap) | 1 |
| pairing_heap (PairingHeap) | 1.29x slower |
| rb_heap | 1.53x slower |
| lazy_priority_queue | 2.6x slower |
| Fibonacci | 4.29x slower |
| ruby 3.3.0 (2023-12-25 revision 5124f9ac75) +YJIT [x86_64-darwin23] | |
| Library | Slower geometric mean |
| pairing_heap (SimplePairingHeap) | 1 |
| rb_heap | 1.227x slower |
| pairing_heap (PairingHeap) | 1.316x slower |
| lazy_priority_queue | 3.094x slower |
| Fibonacci | 3.79x slower |
| jruby 9.4.5.0 (3.1.4) 2023-11-02 1abae2700f OpenJDK 64-Bit Server VM 21+35-2513 on 21+35-2513 +indy +jit [x86_64-darwin] | |
| Library | Slower geometric mean |
| pairing_heap (SimplePairingHeap) | 1.033x slower |
| rb_heap | 1.133x slower |
| pairing_heap (PairingHeap) | 1.302x slower |
| Fibonacci | 1.602x slower |
| lazy_priority_queue | 1.777x slower |
| truffleruby 23.1.2, like ruby 3.2.2, Oracle GraalVM JVM [x86_64-darwin] | |
| Library | Slower geometric mean |
| pairing_heap (SimplePairingHeap) | 1 |
| rb_heap | 1.35x slower |
| pairing_heap (PairingHeap) | 1.58x slower |
| lazy_priority_queue | 5.46x slower |
| Fibonacci | 7.54x slower |
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.
Bug reports and pull requests are welcome on GitHub at https://github.com/mhib/pairing_heap.
The gem is available as open source under the terms of the MIT License.
FAQs
Unknown package
We found that pairing_heap demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
TypeScript is porting its compiler to Go, delivering 10x faster builds, lower memory usage, and improved editor performance for a smoother developer experience.
Research
Security News
The Socket Research Team has discovered six new malicious npm packages linked to North Korea’s Lazarus Group, designed to steal credentials and deploy backdoors.
Security News
Socket CEO Feross Aboukhadijeh discusses the open web, open source security, and how Socket tackles software supply chain attacks on The Pair Program podcast.