# 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_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, 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) |

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

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

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

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

Library | Slower geometric mean | ||

pairing_heap | 1 | ||

lazy_priority_queue | 1.153x slower | ||

Fibonacci | 1.793x slower | ||

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

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

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.