kanwei/algorithms — pull request #11 by juanplopes (2012-07-24 15:39:41+00:00)
Title: Binary heap implementation proposal

In this pull request, I propose a binary heap implementation alternative. Altough its amortized complexities are greater than Fibonacci heap, this array-backed implementation is simpler, more memory-efficient, has better spatial locality (i.e. less indirections) and may be faster for reasonable heap sizes.

In this pull request you'll find a benchmark that shows this point.

```
FIBONACCI | BINARY |
------------------------------------
Push! 1.870 | 0.010 |
Pop! 0.027 | 0.012 |
Merge! 0.003 | 0.013 |

RUBY | COMB_SORT | HEAPSORT | BINARYHEAPSORT | INSERTION_SORT | SHELL_SORT | QUICKSORT | MERGESORT |
------------------------------------------------------------------------------------------------------------------------------
Already sorted 0.000 | 0.015 | 0.479 | 0.068 | 0.001 | 0.009 | 0.135 | 0.014 |
Random 0.001 | 0.024 | 0.544 | 0.069 | 0.190 | 0.016 | 0.008 | 0.024 |

```

Please note that I didn't implement the methods change_key and delete, since it doesn't make too much sense in a binary heap. It would required an additional hashmap to keep track of stored keys, and much of the memory efficiency would be lost.

It's just an implementation proposal. It may not comply with the library coding style. You may eventually realize that neither Ruby nor English are my main languages :)