Binary (min) heap | |||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | binary tree/heap | ||||||||||||||||||||||||||
Invented | 1964 | ||||||||||||||||||||||||||
Invented by | J. W. J. Williams | ||||||||||||||||||||||||||
|
A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues.[1]: 162–163 The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort.[2]
A binary heap is defined as a binary tree with two additional constraints:[3]
Heaps where the parent key is greater than or equal to (≥) the child keys are called max-heaps; those where it is less than or equal to (≤) are called min-heaps. Efficient (logarithmic time) algorithms are known for the two operations needed to implement a priority queue on a binary heap: inserting an element, and removing the smallest or largest element from a min-heap or max-heap, respectively. Binary heaps are also commonly employed in the heapsort sorting algorithm, which is an in-place algorithm because binary heaps can be implemented as an implicit data structure, storing keys in an array and using their relative positions within that array to represent child–parent relationships.
clrs
was invoked but never defined (see the help page).