- 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
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.
- https://en.wikipedia.org/wiki/Binary_heap
- https://en.wikipedia.org/wiki/Pairing_heap
- https://en.wikipedia.org/wiki/Leftist_tree
- https://en.wikipedia.org/wiki/Skew_heap
- https://en.wikipedia.org/wiki/Binomial_heap
- https://en.wikipedia.org/wiki/Finger_tree
- http://www.staff.city.ac.uk/~ross/papers/FingerTree.html
- http://www.mew.org/~kazu/proj/weight-balanced-tree/
- https://hackage.haskell.org/package/containers-0.5.10.2/docs/Data-Map-Lazy.html
- https://en.wikipedia.org/wiki/Weight-balanced_tree
- http://blog.higher-order.net/2009/09/08/understanding-clojures-persistenthashmap-deftwice
- https://infoscience.epfl.ch/record/64398/files/idealhashtrees.pdf
- https://en.wikipedia.org/wiki/Hash_array_mapped_trie