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)
^ merge O(1) O(1)

* Not available in SimplePairingHeap

^ Only 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.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)

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

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

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

Summary

Change priority required

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

Change priority not required

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

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.