Heap

From PEGWiki
Revision as of 23:31, 11 December 2011 by Brian (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.