0.02
The project is in a healthy, maintained state
Performant priority queue in pure ruby with support for changing priority using pairing heap data structure
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
 Dependencies

Development

~> 5.0
~> 13.0
~> 1.20
~> 0.22.0
 Project Readme

PairingHeap

Ruby Style Guide

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 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.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.