Article · Wikipedia archive · Last revised Jun 28, 2026

Pagoda (data structure)

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 or rightmost 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.

Last revised
Jun 28, 2026
Read time
≈ 1 min
Length
170 w
Citations
—
Source
Wikipedia ↗

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.

References

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?
  •  This article incorporates public domain material from Paul E. Black. "pagoda". Dictionary of Algorithms and Data Structures. NIST.