A fast d-ary heap priority queue implementation for ruby, implemented as a C extension.
A regular queue has "FIFO" behavior: first in, first out. A stack is "LIFO": last in first out. A priority queue pushes each element with a score and pops out in order by score. Priority queues are often used in algorithms for e.g. scheduling of timers or bandwidth management, for Huffman coding, and for various graph search algorithms such as Dijkstra's algorithm, A* search, or Prim's algorithm.
From wikipedia:
A heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a min heap, for any given node C, if P is a parent node of C, then the key (the value) of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node.
The d-ary heap data structure is a generalization of a binary heap in which
each node has d children instead of 2. This speeds up "push" or "decrease
priority" operations (O(log n / log d)) with the tradeoff of slower "pop" or
"increase priority" (O(d log n / log d)). Additionally, d-ary heaps can
have better memory cache behavior than binary heaps, letting them run more
quickly in practice.
Although the default d value will usually perform best (see the time complexity analysis below), it's always advisable to benchmark your specific use-case. In particular, if you push items more than you pop, higher values for d can give a faster total runtime.
Add this line to your application's Gemfile:
gem 'd_heap'
And then execute:
$ bundle install
Or install it yourself as:
$ gem install d_heap
The basic API is #push(object, score) and #pop. Please read the full
documentation for more details. The score must be convertable to a Float via
Float(score) (i.e. it should properly implement #to_f).
Quick reference for the most common methods:
heap << object adds a value, using Float(object) as its intrinsic score.heap.push(object, score) adds a value with an extrinsic score.heap.peek to view the minimum value without popping it.heap.pop removes and returns the value with the minimum score.heap.pop_below(max_score) pops only if the next score is < the argument.heap.clear to remove all items from the heap.heap.empty? returns true if the heap is empty.heap.size returns the number of items in the heap.# create some example objects to place in our heap
Task = Struct.new(:id, :time) do
def to_f; time.to_f end
end
t1 = Task.new(1, Time.now + 5*60)
t2 = Task.new(2, Time.now + 50)
t3 = Task.new(3, Time.now + 60)
t4 = Task.new(4, Time.now + 5)
# create the heap
require "d_heap"
heap = DHeap.new
# push with an explicit score (which might be extrinsic to the value)
heap.push t1, t1.to_f
# the score will be implicitly cast with Float, so any object with #to_f
heap.push t2, t2
# if the object has an intrinsic score via #to_f, "<<" is the simplest API
heap << t3 << t4
# pop returns the lowest scored item, and removes it from the heap
heap.pop # => #<struct Task id=4, time=2021-01-17 17:02:22.5574 -0500>
heap.pop # => #<struct Task id=2, time=2021-01-17 17:03:07.5574 -0500>
# peek returns the lowest scored item, without removing it from the heap
heap.peek # => #<struct Task id=3, time=2021-01-17 17:03:17.5574 -0500>
heap.pop # => #<struct Task id=3, time=2021-01-17 17:03:17.5574 -0500>
# pop_lte handles the common "h.pop if h.peek_score < max" pattern
heap.pop_lte(Time.now + 65) # => nil
# the heap size can be inspected with size and empty?
heap.empty? # => false
heap.size # => 1
heap.pop # => #<struct Task id=1, time=2021-01-17 17:07:17.5574 -0500>
heap.empty? # => true
heap.size # => 0
# popping from an empty heap returns nil
heap.pop # => nil
Please see the full documentation for more methods and more examples.
DHeap::Map augments the heap with an internal Hash, mapping objects to their
index in the heap. For simple push/pop this a bit slower than a normal DHeap
heap, but it can enable huge speed-ups for algorithms that need to adjust scores
after they've been added, e.g. Dijkstra's algorithm. It adds the following:
#hash value#[obj] # => score or #score(obj) in O(1)#[obj] = new_score or #rescore(obj, score) in O(d log n / log d)#delete(obj) in O(d log n / log d) (TODO)If a score changes while the object is still in the heap, it will not be re-evaluated again.
Constraining scores to Float gives enormous performance benefits. n.b.
very large Integer values will lose precision when converted to Float. This
is compiler and architecture dependant but with gcc on an IA-64 system, Float
is 64 bits with a 53-bit mantissa, which gives a range of -9,007,199,254,740,991
to +9,007,199,254,740,991, which is not enough to store the precise POSIX
time since the epoch in nanoseconds. This can be worked around by adding a
bias, but probably it's good enough for most usage.
Comparing arbitary objects via a <=> b was the original design and may be
added back in a future version, if (and only if) it can be done without
impacting the speed of numeric comparisons.
DHeap is not thread-safe, so concurrent access from multiple threads need to
take precautions such as locking access behind a mutex.
See full benchmark output in subdirs of benchmarks. See also or updated
results. These benchmarks were measured with an Intel Core i7-1065G7 8x3.9GHz
with d_heap v0.5.0 and ruby 2.7.2 without MJIT enabled.
findmin -
A very fast O(1) push using Array#push onto an unsorted Array, but a
very slow O(n) pop using Array#min, Array#rindex(min) and
Array#delete_at(min_index). Push + pop is still fast for n < 100, but
unusably slow for n > 1000.
bsearch -
A simple implementation with a slow O(n) push using Array#bsearch +
Array#insert to maintain a sorted Array, but a very fast O(1) pop with
Array#pop. It is still relatively fast for n < 10000, but its linear
time complexity really destroys it after that.
rb_heap -
A pure ruby binary min-heap that has been tuned for performance by making
few method calls and allocating and assigning as few variables as possible.
It runs in O(log n) for both push and pop, although pop is slower than
push by a constant factor. Its much higher constant factors makes it lose
to bsearch push + pop for n < 10000 but it holds steady with very little
slowdown even with n > 10000000.
c++ stl -
A thin wrapper around the priority_queue_cxx gem which uses the C++ STL
priority_queue. The wrapper is simply to provide compatibility with the
other benchmarked implementations, but it should be possible to speed this
up a little bit by benchmarking the priority_queue_cxx API directly. It
has the same time complexity as rb_heap but its much lower constant
factors allow it to easily outperform bsearch.
c_dheap -
A {DHeap} instance with the default d value of 4. It has the same time
complexity as rb_heap and c++ stl, but is faster than both in every
benchmarked scenario.
Each benchmark increases N exponentially, either by √1̅0̅ or approximating (alternating between x3 and x3.333) in order to simplify keeping loop counts evenly divisible by N.
This measures the average time per insert to create a queue of size N (clearing the queue once it reaches that size). Use cases which push (or decrease) more values than they pop, e.g. Dijkstra's algorithm or Prim's algorithm when the graph has more edges than verticies, may want to pay more attention to this benchmark.
== push N (N=100) ==========================================================
push N (c_dheap): 10522662.6 i/s
push N (findmin): 9980622.3 i/s - 1.05x slower
push N (c++ stl): 7991608.3 i/s - 1.32x slower
push N (rb_heap): 4607849.4 i/s - 2.28x slower
push N (bsearch): 2769106.2 i/s - 3.80x slower
== push N (N=10,000) =======================================================
push N (c_dheap): 10444588.3 i/s
push N (findmin): 10191797.4 i/s - 1.02x slower
push N (c++ stl): 8210895.4 i/s - 1.27x slower
push N (rb_heap): 4369252.9 i/s - 2.39x slower
push N (bsearch): 1213580.4 i/s - 8.61x slower
== push N (N=1,000,000) ====================================================
push N (c_dheap): 10342183.7 i/s
push N (findmin): 9963898.8 i/s - 1.04x slower
push N (c++ stl): 7891924.8 i/s - 1.31x slower
push N (rb_heap): 4350116.0 i/s - 2.38x slower
All three heap implementations have little to no perceptible slowdown for N > 100. But DHeap runs faster than Array#push to an unsorted array (findmin)!
This measures the average for a push or a pop, filling up a queue with N items and then draining that queue until empty. It represents the amortized cost of balanced pushes and pops to fill a heap and drain it.
== push N then pop N (N=100) ===============================================
push N + pop N (c_dheap): 10954469.2 i/s
push N + pop N (c++ stl): 9317140.2 i/s - 1.18x slower
push N + pop N (bsearch): 4808770.2 i/s - 2.28x slower
push N + pop N (findmin): 4321411.9 i/s - 2.53x slower
push N + pop N (rb_heap): 2467417.0 i/s - 4.44x slower
== push N then pop N (N=10,000) ============================================
push N + pop N (c_dheap): 8083962.7 i/s
push N + pop N (c++ stl): 7365661.8 i/s - 1.10x slower
push N + pop N (bsearch): 2257047.9 i/s - 3.58x slower
push N + pop N (rb_heap): 1439204.3 i/s - 5.62x slower
== push N then pop N (N=1,000,000) =========================================
push N + pop N (c++ stl): 5274657.5 i/s
push N + pop N (c_dheap): 4731117.9 i/s - 1.11x slower
push N + pop N (rb_heap): 976688.6 i/s - 5.40x slower
At N=100 findmin still beats a pure-ruby heap. But above that it slows down too
much to be useful. At N=10k, bsearch still beats a pure ruby heap, but above
30k it slows down too much to be useful. DHeap consistently runs 4.5-5.5x
faster than the pure ruby heap.
This measures the combined time to push once and pop once, which is done repeatedly while keeping a stable heap size of N. Its an approximation for scenarios which reach a stable size and then plateau with balanced pushes and pops. E.g. timers and timeouts will often reschedule themselves or replace themselves with new timers or timeouts, maintaining a roughly stable total count of timers.
push + pop (findmin)
N 10: 5480288.0 i/s
N 100: 2595178.8 i/s - 2.11x slower
N 1000: 224813.9 i/s - 24.38x slower
N 10000: 12630.7 i/s - 433.89x slower
N 100000: 1097.3 i/s - 4994.31x slower
N 1000000: 135.9 i/s - 40313.05x slower
N 10000000: 12.9 i/s - 425838.01x slower
push + pop (bsearch)
N 10: 3931408.4 i/s
N 100: 2904181.8 i/s - 1.35x slower
N 1000: 2203157.1 i/s - 1.78x slower
N 10000: 1209584.9 i/s - 3.25x slower
N 100000: 81121.4 i/s - 48.46x slower
N 1000000: 5356.0 i/s - 734.02x slower
N 10000000: 281.9 i/s - 13946.33x slower
push + pop (rb_heap)
N 10: 2325816.5 i/s
N 100: 1603540.3 i/s - 1.45x slower
N 1000: 1262515.2 i/s - 1.84x slower
N 10000: 950389.3 i/s - 2.45x slower
N 100000: 732548.8 i/s - 3.17x slower
N 1000000: 673577.8 i/s - 3.45x slower
N 10000000: 467512.3 i/s - 4.97x slower
push + pop (c++ stl)
N 10: 7706818.6 i/s - 1.01x slower
N 100: 7393127.3 i/s - 1.05x slower
N 1000: 6898781.3 i/s - 1.13x slower
N 10000: 5731130.5 i/s - 1.36x slower
N 100000: 4842393.2 i/s - 1.60x slower
N 1000000: 4170936.4 i/s - 1.86x slower
N 10000000: 2737146.6 i/s - 2.84x slower
push + pop (c_dheap)
N 10: 10196454.1 i/s
N 100: 9668679.8 i/s - 1.05x slower
N 1000: 9339557.0 i/s - 1.09x slower
N 10000: 8045103.0 i/s - 1.27x slower
N 100000: 7150276.7 i/s - 1.43x slower
N 1000000: 6490261.6 i/s - 1.57x slower
N 10000000: 3734856.5 i/s - 2.73x slower
There are two fundamental heap operations: sift-up (used by push or decrease score) and sift-down (used by pop or delete or increase score). Each sift bubbles an item to its correct location in the tree.
log n / log d layers, so either sift performs as many as
log n / log d writes, when a member sifts the entire length of the tree.O(log n / log d).O(d log n / log d).So, in the case of a balanced push then pop, as many as (1 + d) log n / log d
comparisons are made. Looking only at this worst case combo, d=4 requires the
fewest comparisons for a combined push and pop:
(1 + 2) log n / log d ≈ 4.328085 log n(1 + 3) log n / log d ≈ 3.640957 log n(1 + 4) log n / log d ≈ 3.606738 log n(1 + 5) log n / log d ≈ 3.728010 log n(1 + 6) log n / log d ≈ 3.906774 log n(1 + 7) log n / log d ≈ 4.111187 log n(1 + 8) log n / log d ≈ 4.328085 log n(1 + 9) log n / log d ≈ 4.551196 log n(1 + 10) log n / log d ≈ 4.777239 log nSee https://en.wikipedia.org/wiki/D-ary_heap#Analysis for deeper analysis.
However, what this simple count of comparisons misses is the extent to which modern compilers can optimize code (e.g. by unrolling the comparison loop to execute on registers) and more importantly how well modern processors are at pipelined speculative execution using branch prediction, etc. Benchmarks should be run on the exact same hardware platform that production code will use, as the sift-down operation is especially sensitive to good pipelining.
It is often useful to use external scores for otherwise uncomparable values.
And casting an item or score (via to_f) can also be time consuming. So
DHeap evaluates and stores scores at the time of insertion, and they will be
compared directly without needing any further lookup.
Numeric values can be compared much faster than other ruby objects, even if
those objects simply delegate comparison to internal Numeric values.
Additionally, native C integers or floats can be compared much faster than
ruby Numeric objects. So scores are converted to Float and stored as
double, which is 64 bits on an LP64 64-bit system.
As always, you should run benchmarks with your expected scenarios to determine which is best for your application.
Depending on your use-case, using a sorted Array using #bsearch_index
and #insert might be just fine! It only takes a couple of lines of code and
is probably "Fast Enough".
More complex heap variant, e.g. Fibonacci heap, allow heaps to be split and merged which gives some graph algorithms a lower amortized time complexity. But in practice, d-ary heaps have much lower overhead and often run faster.
If it is important to be able to quickly enumerate the set or find the ranking of values in it, then you may want to use a self-balancing binary search tree (e.g. a red-black tree) or a skip-list.
Hashed and Heirarchical Timing Wheels (or some variant in the
timing wheel family of data structures) can have effectively O(1) running time
in most cases. Although the implementation for that data structure is more
complex than a heap, it may be necessary for enormous values of N.
See the CI workflow for all supported platforms.
d_heap may contain bugs on 32-bit systems. Currently, d_heap is only tested
on 64-bit x86 CRuby 2.4-3.0 under Linux and Mac OS.
A DHeap's internal array grows but never shrinks. At the very least, there
should be a #compact or #shrink method and during #freeze. It might make
sense to automatically shrink (to no more than 2x the current size) during GC's
compact phase.
Benchmark sift-down min-child comparisons using SSE, AVX2, and AVX512F. This
might lead to a different default d value (maybe 16 or 24?).
Shrink scores to 64-bits: either store a type flag with each entry (this could
be used to support non-numeric scores) or require users to choose between
Integer or Float at construction time. Reducing memory usage should also
improve speed for very large heaps.
Patches to support JRuby, rubinius, 32-bit systems, or any other platforms are welcome! JRuby and Truffle Ruby ought to be able to use Java's PriorityQueue? Other platforms could fallback on the (slower) pure ruby implementation used by the benchmarks.
Allow a max-heap (or other configurations of the compare function). This can be very easily implemented by just reversing the scores.
Maybe allow non-numeric scores to be compared with <=>, only if the basic
numeric use case simplicity and speed can be preserved.
Consider DHeap::Monotonic, which could rely on #pop_below for "current time"
and move all values below that time onto an Array.
Consider adding DHeap::Lazy or DHeap.new(lazy: true) which could contain
some features that are loosely inspired by go's timers. Go lazily sifts its
heap after deletion or adjustments, to achieve faster amortized runtime.
There's no need to actually remove a deleted item from the heap, if you re-add
it back before it's next evaluated. A similar trick can be to store "far away"
values in an internal Hash, assuming many will be deleted before they rise to
the top. This could naturally evolve into a timing wheel variant.
After checking out the repo, run bin/setup to install dependencies. Then, run
rake spec 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 tags, and push the .gem file to
rubygems.org.
Bug reports and pull requests are welcome on GitHub at https://github.com/nevans/d_heap. This project is intended to be a safe, welcoming space for collaboration, and contributors are expected to adhere to the code of conduct.
The gem is available as open source under the terms of the MIT License.
Everyone interacting in the DHeap project's codebases, issue trackers, chat rooms and mailing lists is expected to follow the code of conduct.
FAQs
Unknown package
We found that d_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
Research
A malicious npm package disguised as a WhatsApp client is exploiting authentication flows with a remote kill switch to exfiltrate data and destroy files.
Security News
PyPI now supports digital attestations, enhancing security and trust by allowing package maintainers to verify the authenticity of Python packages.
Security News
GitHub removed 27 malicious pull requests attempting to inject harmful code across multiple open source repositories, in another round of low-effort attacks.