Heap
From PEGWiki
Revision as of 23:30, 11 December 2011 by Brian (Talk | contribs) (Created page with "Various implementations of the priority queue abstract data type are known as '''heaps'''. A ''max-heap-ordered tree'' is a rooted tree in which every node's label i...")
Various implementations of the priority queue abstract data type are known as heaps.
A max-heap-ordered tree is a rooted tree in which every node's label is greater than or equal to the labels of all its children; so the maximum label may be found at the root. A max-heap is a collection of max-heap-ordered trees. The terms min-heap-ordered-tree and min-heap are defined analogously. A heap is either a max-heap or a min-heap.
The word heap, when unqualified, usually refers to the binary heap data structure. However, this is not the only data structure that is a heap; the binomial heap and Fibonacci heap are well-known varieties of heaps.
