Skip to content

Latest commit

 

History

History
38 lines (30 loc) · 2.66 KB

README.md

File metadata and controls

38 lines (30 loc) · 2.66 KB
Raw

TypeScript implementation of several heap data structures

Implemented data structures

  • Binary heap[1] - mutable, array backed
  • Pairing heap[2] - persistent, has very good real-world performance
  • Leftist heap[3] - persistent, left biased tree
  • Skew heap[4] - persistent, reminiscent of Leftist Tree, but doesn't use ranks and has better merge performance
  • Binomial heap[5] - persistent, uses array as subtree storage
  • Finger Heap - persistent, uses Finger Tree as storage
  • Finger Vector - persistent, uses Finger Tree as storage
  • Finger Tree [6][7] - persistent, amortised O(1) dequeue operations, efficient split/concatenation
    Note: This implementation uses a strict spine. This means that the cost of the amortised operations is payed upfront and when that happens, the triggering operation pays the full O(log n) cost. However, the amortised complexities still hold, unless a bad data structure is purposefully reused multiple times.
  • Weight-Balanced Tree[8][9][10] - persistent, ordered, Map interface
  • Hash Array Mapped Trie (HAMT)[11][12][13] - persistent, hash based, Map interface

A note on implementation

All implementations assume a min heap. This is not a problem, however, because all heap constructors require a comparator to be provided. To derive a max heap, simply invert the comparator.

References

  1. https://en.wikipedia.org/wiki/Binary_heap
  2. https://en.wikipedia.org/wiki/Pairing_heap
  3. https://en.wikipedia.org/wiki/Leftist_tree
  4. https://en.wikipedia.org/wiki/Skew_heap
  5. https://en.wikipedia.org/wiki/Binomial_heap
  6. https://en.wikipedia.org/wiki/Finger_tree
  7. http://www.staff.city.ac.uk/~ross/papers/FingerTree.html
  8. http://www.mew.org/~kazu/proj/weight-balanced-tree/
  9. https://hackage.haskell.org/package/containers-0.5.10.2/docs/Data-Map-Lazy.html
  10. https://en.wikipedia.org/wiki/Weight-balanced_tree
  11. http://blog.higher-order.net/2009/09/08/understanding-clojures-persistenthashmap-deftwice
  12. https://infoscience.epfl.ch/record/64398/files/idealhashtrees.pdf
  13. https://en.wikipedia.org/wiki/Hash_array_mapped_trie