heap

Let $\preceq$ 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\preceq y$ must hold. This property is often referred to as the heap property.

If $\preceq$ is $\leq$, then the root of the heap always gives the smallest element of the heap, and if $\preceq$ is $\geq$, 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\preceq x$ holds for all $x$ in the heap.

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