Pagoda (data structure)
From Wikipedia, the free encyclopedia
In computer science, a pagoda is a priority queue implemented with a variant of a binary tree. The root points to its children, as in a binary tree. Every other node points back to its parent and down to its leftmost (if it is a right child) or rightmost (if it is a left child) descendant leaf. The basic operation is merge or meld, which maintains the heap property. An element is inserted by merging it as a singleton. The root is removed by merging its right and left children. Merging is bottom-up, merging the leftmost edge of one with the rightmost edge of the other.
[edit] References
- J. Francon, G. Viennot, and J. Vuillemin, Description and analysis of an efficient priority queue representation, Proc. 19th Annual Symp. on Foundations of Computer Science. IEEE, 1978, pages 1-7.
- R. Nix, An Evaluation of Pagodas, Res. Rep. 164, Dept. of Computer Science, Yale Univ. 1988?
- Paul E. Black, pagoda at the NIST Dictionary of Algorithms and Data Structures.
