A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:
- The shape property: the tree is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
- The heap property: each node is greater than or equal to each of its children according to a comparison predicate defined for the data structure.
Heaps with a mathematical "greater than or equal to" comparison function are called max-heaps; those with a mathematical "less than or equal to" comparison function are called min-heaps. Min-heaps are often used to implement priority queues.
Since the ordering of siblings in a heap is not specified by the heap property, a single node's two children can be freely interchanged unless doing so violates the shape property (compare with treap).
The binary heap is a special case of the d-ary heap in which d = 2.
Read more about Binary Heap: Heap Operations, Building A Heap, Heap Implementation, Derivation of Children's Index in An Array Implementation
Famous quotes containing the word heap:
“—First a shiver, and then a thrill,
Then something decidedly like a spill,—
And the parson was sitting up on a rock,
At half-past nine by the meet’n’-house clock,—
Just the hour of the Earthquake shock!
MWhat do you think the parson found,
When he got up and stared around?
The poor old chaise in a heap or mound,
As if it had been to the mill and ground!”
—Oliver Wendell Holmes, Sr. (1809–1894)