Difference between revisions of "Heap"
From PEGWiki
(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...") |
|||
Line 6: | Line 6: | ||
[[Category:Heaps]] | [[Category:Heaps]] | ||
+ | [[Category:Data structures]] |
Latest revision as of 23:31, 11 December 2011
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.