2-3 heap
|
|
A 2-3 heap is a data structure, a variation on the heap, designed by Tadao Takaoka in 1999. The structure is similar to the Fibonacci heap, and borrows from the 2-3 tree.
Time costs for some common heap operations:
- delete-min takes <math>O(log(n))<math> amortized time
- decrease-key takes constant amortized time
- insertion takes constant amortized time.
References
Original papers:
- Tadao Takaoka Theory of 2-3 Heaps, Cocoon 1999 (link) (http://www.cosc.canterbury.ac.nz/~tad/2-3heaps.pdf)