Difference between revisions of "Heap"

From PEGWiki
Jump to: navigation, search
(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.