# heap

Let $\u2aaf$ be a total order^{} on some set $A$. A *heap* is then a data structure for storing elements in $A$. A heap is a balanced binary tree, with the property that if $y$ is a descendent of $x$ in the heap, then $x\u2aafy$ must hold. This property is often referred to as the *heap property*.

If $\u2aaf$ is $\le $, then the root of the heap always gives the smallest element of the heap, and if $\u2aaf$ is $\ge $, then the root of the heap always gives the largest element of the heap. More generally, the root of the heap is some $a\in A$ such that $a\u2aafx$ holds for all $x$ in the heap.

For example, the following heap represents the multiset $\{1,2,4,4,6,8\}$ for the total order $\ge $ on $\mathbb{Z}$.