(data structure)

Definition: 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.

Generalization (I am a kind of ...)
priority queue.

Aggregate child (... is a part of or used in me.)
binary tree, heap property, meld.

Author: PEB


delete (C and Pascal), insert (C and Pascal), and merge (C and Pascal)

More information

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?

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 16 November 2009.
HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:
Paul E. Black, "pagoda", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 16 November 2009. (accessed TODAY) Available from:

to NIST home page