Pagoda (data structure)

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 (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

* 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?
*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Pagoda (disambiguation) — Pagoda can mean: * Pagoda, tower with a tiered structure * Pagoda (band), the New York grunge band * Pagoda (album) * Pagoda (coin), the Indian coin * Pagoda (data structure) * Columbariidae, the pagoda shell * Pagoda Mast, the distinctive… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • arts, East Asian — Introduction       music and visual and performing arts of China, Korea, and Japan. The literatures of these countries are covered in the articles Chinese literature, Korean literature, and Japanese literature.       Some studies of East Asia… …   Universalium

  • Religion in China — Three laughs at Tiger Brook , Confucianism, Taoism, and Buddhism are one, a litang style painting portraying three men laughing by a river stream, 12th century, Song Dynasty …   Wikipedia

  • National Treasures of Japan — For the informal term of Preservers of Important Intangible Cultural Properties, see Living National Treasures of Japan …   Wikipedia

  • Bibliography —    CONTENTS    Introduction 488    I. General 493    1. Bibliographies and Research Guides 493    2. Directories, Handbooks, Statistical Abstracts, and Yearbooks 494    3. Guides 494    4. Travel and Description 494    II. History 496    1.… …   Historical Dictionary of Burma (Myanmar)

  • education — /ej oo kay sheuhn/, n. 1. the act or process of imparting or acquiring general knowledge, developing the powers of reasoning and judgment, and generally of preparing oneself or others intellectually for mature life. 2. the act or process of… …   Universalium

  • Gyeongju — 경주 …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”