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.
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_priorityreturnsselfinstead of the first argumentenqueuereturnsselfinstead of the first argument- Queue classes are in the
PairingHeapnamespace, sorequire 'pairing_heapdoes not loadMinPriorityQueueto the global scope top_conditionconstructor 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, used for example in RGL
- 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.0p0 (2021-12-25 revision fb4df44d16) [x86_64-darwin21] Library Iterations Seconds Iterations per second pairing_heap (SimplePairingHeap) 18 60.232046 0.299 pairing_heap (PairingHeap) 15 63.978031 0.234(1.27x slower) lazy_priority_queue 9 60.031283 0.150(1.99x slower) rb_heap 9 60.497355 0.149(2.01x slower) Fibonacci 8 66.866055 0.120(2.50x slower) ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) +YJIT [x86_64-darwin21] Library Iterations Seconds Iterations per second pairing_heap (SimplePairingHeap) 22 62.866807 0.350 pairing_heap (PairingHeap) 16 61.358679 0.261(1.34x slower) Fibonacci 14 64.394112 0.217(1.61x slower) rb_heap 12 60.975479 0.197(1.78x slower) lazy_priority_queue 11 65.568648 0.168(2.09x slower) jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit Server VM 16.0.1+9-24 on 16.0.1+9-24 +jit [darwin-x86_64] Library Iterations Seconds Iterations per second pairing_heap (SimplePairingHeap) 21 60.357577s 0.348 pairing_heap (PairingHeap) 15 60.417252 0.248(1.40x slower) lazy_priority_queue 14 61.022450 0.229(1.52x slower) rb_heap 13 63.661862 0.204(1.70x slower) Fibonacci 8 62.643449 0.128(2.72x slower) jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit Server VM 16.0.1+9-24 on 16.0.1+9-24 +indy +jit [darwin-x86_64] Library Iterations Seconds Iterations per second pairing_heap (SimplePairingHeap) 43 60.472129 0.711 pairing_heap (PairingHeap) 30 60.359748 0.497(1.43x slower) Fibonacci 25 62.084250 0.403(1.77x slower) rb_heap 23 62.419893 0.369(1.93x slower) lazy_priority_queue 22 60.947299 0.361(1.97x 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.0p0 (2021-12-25 revision fb4df44d16) [x86_64-darwin21] | |||
|---|---|---|---|
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap | 14 | 63.536300 | 0.220 |
| lazy_priority_queue | 9 | 63.319474s | 0.142(1.55x slower) |
| Fibonacci | 8 | 67.385714 | 0.119(1.86x slower) |
| ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) +YJIT [x86_64-darwin21] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap | 15 | 62.243080 | 0.241 |
| Fibonacci | 13 | 63.030390 | 0.206(1.17x slower) |
| lazy_priority_queue | 10 | 64.865853 | 0.154(1.56x slower) |
| jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit Server VM 16.0.1+9-24 on 16.0.1+9-24 +jit [darwin-x86_64] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap | 15 | 61.540851 | 0.244 |
| lazy_priority_queue | 14 | 61.471507 | 0.228(1.07x slower) |
| Fibonacci | 9 | 67.393730 | 0.134(1.83x slower) |
| jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit Server VM 16.0.1+9-24 on 16.0.1+9-24 +indy +jit [darwin-x86_64] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap | 27 | 61.322001 | 0.440 |
| Fibonacci | 21 | 60.334636 | 0.349(1.26x slower) |
| lazy_priority_queue | 20 | 61.471507 | 0.327(1.35x slower) |
Stress test with changing priority(N = 10) source code
A stress test of 165 operations: starting with 10 pushes/10 change_priorities/0 pops, following 9 pushes/9 change_priorities/1 pop, and so on till 0 pushes/0 change_priorities/10 pops.
| ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) [x86_64-darwin21] | |||
|---|---|---|---|
| Library | Iterations per second | ||
| pairing_heap | 5914.3 | ||
| lazy_priority_queue | 4293.5(1.38x slower) | ||
| Fibonacci | 3755.2(1.57x slower) | ||
| ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) +YJIT [x86_64-darwin21] | |||
| Library | Iterations per second | ||
| pairing_heap | 7082.7 | ||
| Fibonacci | 6687.1(1.06x slower) | ||
| lazy_priority_queue | 5006.4(1.41x slower) | ||
| jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit Server VM 16.0.1+9-24 on 16.0.1+9-24 +jit [darwin-x86_64] | |||
| Library | Iterations per second | ||
| pairing_heap | 6861.6 | ||
| lazy_priority_queue | 6446.4(1.06x slower) | ||
| Fibonacci | 4365.4(1.57x slower) | ||
| jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit Server VM 16.0.1+9-24 on 16.0.1+9-24 +indy +jit [darwin-x86_64] | |||
| Library | Iterations per second | ||
| pairing_heap | 14032 | ||
| Fibonacci | 12841(1.09x slower) | ||
| lazy_priority_queue | 10404(1.35x slower) | ||
Dijkstra's algorithm with RGL source code
| ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) [x86_64-darwin21] | |||
|---|---|---|---|
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap | 9 | 64.505899 | 0.140 |
| lazy_priority_queue | 8 | 63.970577 | 0.125(1.12x slower) |
| Fibonacci | 7 | 62.573724 | 0.112(1.25x slower) |
| ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) +YJIT [x86_64-darwin21] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap | 9 | 63.567801 | 0.142 |
| Fibonacci | 9 | 64.575079 | 0.140(1.02x slower) |
| lazy_priority_queue | 8 | 60.123700 | 0.133(1.06x slower) |
| jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit Server VM 16.0.1+9-24 on 16.0.1+9-24 +jit [darwin-x86_64] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap | 14 | 64.124373 | 0.218 |
| lazy_priority_queue | 13 | 61.147807 | 0.213(1.03x slower) |
| Fibonacci | 10 | 64.250067 | 0.156(1.40x slower) |
| jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit Server VM 16.0.1+9-24 on 16.0.1+9-24 +indy +jit [darwin-x86_64] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap | 22 | 61.450341 | 0.361 |
| Fibonacci | 18 | 61.618204 | 0.296(1.22x slower) |
| lazy_priority_queue | 17 | 60.156184 | 0.283(1.27x 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.0p0 (2021-12-25 revision fb4df44d16) [x86_64-darwin21] | |||
|---|---|---|---|
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap (SimplePairingHeap) | 25 | 61.386477 | 0.407 |
| pairing_heap (PairingHeap) | 22 | 62.044470 | 0.355(1.15x slower) |
| rb_heap | 13 | 60.717112 | 0.214(1.90x slower) |
| lazy_priority_queue | 10 | 61.730614 | 0.162(2.51x slower) |
| Fibonacci | 10 | 65.899982 | 0.152(2.68x slower) |
| ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) +YJIT [x86_64-darwin21] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap (SimplePairingHeap) | 29 | 61.656995 | 0.471 |
| pairing_heap (PairingHeap) | 24 | 61.813482 | 0.389(1.21x slower) |
| rb_heap | 19 | 62.191040 | 0.306(1.54x slower) |
| Fibonacci | 18 | 60.062072 | 0.300(1.57x slower) |
| lazy_priority_queue | 12 | 60.860292 | 0.197(2.38x slower) |
| jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit Server VM 16.0.1+9-24 on 16.0.1+9-24 +jit [darwin-x86_64] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap (SimplePairingHeap) | 24 | 61.972936 | 0.387 |
| pairing_heap (PairingHeap) | 20 | 62.178839 | 0.322(1.20x slower) |
| lazy_priority_queue | 14 | 61.540058s | 0.228(1.70x slower) |
| rb_heap | 14 | 62.125831 | 0.225(1.72x slower) |
| Fibonacci | 10 | 62.319669 | 0.155(2.41x slower) |
| jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit Server VM 16.0.1+9-24 on 16.0.1+9-24 +indy +jit [darwin-x86_64] | |||
| Library | Iterations | Seconds | Iterations per second |
| pairing_heap (SimplePairingHeap) | 47 | 61.192519 | 0.770 |
| rb_heap | 39 | 61.028398 | 0.639(1.20x slower) |
| pairing_heap (PairingHeap) | 36 | 60.035760 | 0.601(1.28x slower) |
| Fibonacci | 28 | 61.599202 | 0.456(1.69x slower) |
| lazy_priority_queue | 22 | 60.540367 | 0.364(2.12x slower) |
Summary
Change priority required
| ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) [x86_64-darwin21] | |||
|---|---|---|---|
| Library | Slower geometric mean | ||
| pairing_heap | 1 | ||
| lazy_priority_queue | 1.523x slower | ||
| Fibonacci | 1.751x slower | ||
| ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) +YJIT [x86_64-darwin21] | |||
| Library | Slower geometric mean | ||
| pairing_heap | 1 | ||
| Fibonacci | 1.146x slower | ||
| lazy_priority_queue | 1.482x slower | ||
| jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit Server VM 16.0.1+9-24 on 16.0.1+9-24 +jit [darwin-x86_64] | |||
| Library | Slower geometric mean | ||
| pairing_heap | 1 | ||
| lazy_priority_queue | 1.153x slower | ||
| Fibonacci | 1.793x slower | ||
| jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit Server VM 16.0.1+9-24 on 16.0.1+9-24 +indy +jit [darwin-x86_64] | |||
| Library | Slower geometric mean | ||
| pairing_heap | 1 | ||
| Fibonacci | 1.222x slower | ||
| lazy_priority_queue | 1.394x slower | ||
Change priority not required
| ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) [x86_64-darwin21] | |||
|---|---|---|---|
| Library | Slower geometric mean | ||
| pairing_heap (SimplePairingHeap) | 1 | ||
| pairing_heap (PairingHeap) | 1.209x slower | ||
| rb_heap | 1.954x slower | ||
| lazy_priority_queue | 2.235x slower | ||
| Fibonacci | 2.588x slower | ||
| ruby 3.1.0p0 (2021-12-25 revision fb4df44d16) +YJIT [x86_64-darwin21] | |||
| Library | Slower geometric mean | ||
| pairing_heap (SimplePairingHeap) | 1 | ||
| pairing_heap (PairingHeap) | 1.273x slower | ||
| Fibonacci | 1.590x slower | ||
| rb_heap | 1.666x slower | ||
| lazy_priority_queue | 2.230x slower | ||
| jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit Server VM 16.0.1+9-24 on 16.0.1+9-24 +jit [darwin-x86_64] | |||
| Library | Slower geometric mean | ||
| pairing_heap (SimplePairingHeap) | 1 | ||
| pairing_heap (PairingHeap) | 1.296x slower | ||
| lazy_priority_queue | 1.607x slower | ||
| rb_heap | 1.710x slower | ||
| Fibonacci | 2.452x slower | ||
| jruby 9.3.3.0 (2.6.8) 2022-01-19 b26de1f5c5 OpenJDK 64-Bit Server VM 16.0.1+9-24 on 16.0.1+9-24 +indy +jit [darwin-x86_64] | |||
| Library | Slower geometric mean | ||
| pairing_heap (SimplePairingHeap) | 1 | ||
| pairing_heap (PairingHeap) | 1.353x slower | ||
| rb_heap | 1.522x slower | ||
| Fibonacci | 1.730x slower | ||
| lazy_priority_queue | 2.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.