Binary heap: Difference between revisions

Revision as of 02:50, 5 November 2004

Revision as of 19:40, 2 February 2005

Line 1:

[[Category:Trees (structure)]]

'''Binary heaps''' are a particularly simple kind of [[heap]] [[data structure]] created using a [[binary tree]]. It can be seen as a binary tree with thetwo additional constraint that each node is larger than all its children (for a max-heap) or smaller than all its children (for a min-heap). Conventionally, max-heaps are used, since they are readily applicable for use in [[priority queue]]s.constraints:

*The ''shape property'': that the <math>{n}</math>th node of the heap is a child of the <math>\left \lfloor \frac{n}{2} \right \rfloor</math>th node.

*The ''heap property'': that each node is greater than or equal to each of its children.

"Greater than" means according to whatever comparison function is chosen to sort the heap, not necessarily "greater than" in the mathematical sense (since the quantities are not even always numerical). Heaps where the comparison function is mathematical "greater than" are called max-heaps; those where the comparison function is mathematical "less than" are called "min-heaps". Conventionally, max-heaps are used, since they are readily applicable for use in [[priority queue]]s.

1 11

Line 10 ⟶ 16:

8 9 10 11 1 2 3 4

Note that the ordering of siblings in a heap is not specified by the [[heap|heap property]], so the two children of a parent can be freely interchanged.

== Heap operations ==