Ruby heaps inspired by Python
Ruby arrays are impressive. They can be used as a stack or a queue because adding and removing from either end of the list is amortized to O(1). They are flexible, and the workhorses of Ruby.
So, why not make them even more flexible and allow them to be used as heaps? (priority queues) Ruby doesn't currently have heaps in it's standard library.
Inspired by Python's standard library, heapq, I wrote a gem called heapify that extends Ruby arrays with three methods that allow you to use them as heaps!
heapify
Transforms an array into a heap in-place. It has a time complexity of O(n) and a space complexity of O(1).
heap = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7] heap.heapify # => [1, 2, 3, 4, 7, 9, 10, 14, 8, 16]
heap_push(val)
Adds an element to the heap. It has a time complexity of O(log n) and a space complexity of O(1).
heap = [1, 2, 3, 4, 7, 9, 10, 14, 8, 16] heap.heap_push(5) # array => [1, 2, 3, 4, 5, 9, 10, 14, 8, 7, 16]
heap_pop
Removes the smallest element from the heap and returns it. It has a time complexity of O(log n) and a space complexity of O(1).
heap = [1, 2, 3, 4, 7, 9, 10, 14, 8, 16] heap.heap_pop # => 1
I love this little interface because it's simple and it allows us to view heaps as a regular Ruby arrays without surprises: heap.first is the smallest item, and heap.sort maintains the heap invariant!
The next step is adding a C implementation and checking if it provides any significant speedup, and then maybe adding other methods like heap_push_pop and heap_replace.
Why not a Heap class?
Using an Array allows random access to the heap's elements. If we use a Heap class, we cannot allow random access while guaranteeing the heap invariant. For the same reason, we cannot efficiently implement Enumerable for a Heap class, but with the Array, we don't have to worry about that. It's obvious that it's the user's responsibility to maintain the heap. This makes using an Array much more flexible.