Ruby Heaps Inspired by Python (opens in new tab)

(homo-sapiens-reviewed.bearblog.dev)

2 pointsgarrisonj1y ago2 comments

2 comments

Lio1y ago

Nice. This is interesting and definitely something worth implementing. I hope you don't mind but I have some discussion points.

If it were me, rather than monkey patching array I'd be tempted introduce a new dedicated Heap class that implements existing API (push, pop, <<, shift) so that it's closer to existing Array and Queue implementations instead of adding dedicated heap_push, heap_pop, etc..

As well as better duck typing this allows introspection via .is_a? and case statements.

Also I wonder if it would be useful to base the implementation on the Queue[1] rather than Array to maintain thread safety.

1. https://ruby-doc.org/core-2.5.0/Queue.html

garrisonjOP1y ago

Defining a new class is probably the most Ruby way to do it. There are two implementations that define a new class: rb_heap[1] and algorithms[2]. However, algorithms[2] use a Fibonacci heap, which should technically have better time complexity but is slower in practice, and the library pulls in a lot of unnecessary stuff. rb_heap is good, although I think using a symbol to specify if it's a max/min heap is a little strange.

There is something satisfying about using an array like Python. It's very straightforward and doesn't require you to convert back and forth between a queue and a array.

That's an interesting idea to use Queue. I do need random access to implement the binary queue, so I'm not sure if Queue would work.

1. https://github.com/florian/rb_heap 2. https://github.com/kanwei/algorithms

j / k navigate · click thread line to collapse