Pile (data structure)

Pile (data structure)

A pile is an abstract data structure for storing data in a loosely ordered way. There are two different usages of the term

Ordered deque

The first version combines the properties of the deque and a priority queue and may be described as an ordered dequeue.

An item may be added to the head of the list if the new item is valued less than or equal to the current head or to the tail of the list if the new item is greater than or equal to the current tail. Elements may be removed from both the head and the tail. [Art S. Kagel, " [http://www.nist.gov/dads/HTML/pile.html Pile] ", in "Dictionary of Algorithms and Data Structures" [online] , Paul E. Black, ed., National Institute of Standards and Technology, assessed September 27, 2007.]

Piles of this kind are used in the "UnShuffle sort" sorting algorithm.

Improved heap

The second version is a subject of patents [ [http://www.patentstorm.us/patents/6952696-fulltext.html "Data structure and method for sorting using heap-supernodes"] , U.S. patent 728147 (2000, issued 2005)] [ [http://www.patentstorm.us/patents/7007021-fulltext.html "Data structure and method for pipeline heap-sorting"] , U.S. patent 09727534 (2000, issued 2006)] and improves the heap data structure.

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Pile — may refer to:*Pile foundation, type of deep foundation *Pile (textile), fabric with raised surface made of upright loops or strands of yarn ** Carpet pile * Nuclear pile, early term for a nuclear reactor, typically one constructed of graphite *… …   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

  • Pile integrity test — A pile integrity test (also known as low strain dynamic test, sonic echo test, and low strain integrity test) is one of the methods for assessing the condition of piles or shafts. It is cost effective and not very time consuming.The test is based …   Wikipedia

  • structure — struc|ture1 W2S3 [ˈstrʌktʃə US ər] n [Date: 1400 1500; : Latin; Origin: structura act of building , from struere to make into a pile, build ] 1.) [U and C] the way in which the parts of something are connected with each other and form a whole, or …   Dictionary of contemporary English

  • Plesiochronous data hierarchy — Hiérarchie numérique plésiochrone Pile de protocoles 7 • Application 6 • Présentation 5 • Session 4 • …   Wikipédia en Français

  • UnShuffle sort — is a sort algorithm. IntroductionThe UnShuffle Sort is a distribution or merge sort which was developed by Art S. Kagel. UnShuffle is most efficient when sorting data which exhibits low entropy, in effect where the data is well ordered or… …   Wikipedia

  • LIFO — is an acronym which stands for last in, first out. In computer science and queueing theory this refers to the way items stored in some types of data structures are processed. By definition, in a LIFO structured linear list, elements can only be… …   Wikipedia

  • Stack — (st[a^]k), n. [Icel. stakkr; akin to Sw. stack, Dan. stak. Cf. {Stake}.] 1. A large and to some degree orderly pile of hay, grain, straw, or the like, usually of a nearly conical form, but sometimes rectangular or oblong, contracted at the top to …   The Collaborative International Dictionary of English

  • Stack of arms — Stack Stack (st[a^]k), n. [Icel. stakkr; akin to Sw. stack, Dan. stak. Cf. {Stake}.] 1. A large and to some degree orderly pile of hay, grain, straw, or the like, usually of a nearly conical form, but sometimes rectangular or oblong, contracted… …   The Collaborative International Dictionary of English

  • to blow one's stacks — Stack Stack (st[a^]k), n. [Icel. stakkr; akin to Sw. stack, Dan. stak. Cf. {Stake}.] 1. A large and to some degree orderly pile of hay, grain, straw, or the like, usually of a nearly conical form, but sometimes rectangular or oblong, contracted… …   The Collaborative International Dictionary of English

Share the article and excerpts

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