heap

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

If $⪯$ is $\le$, then the root of the heap always gives the smallest element of the heap, and if $⪯$ 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⪯x$ 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}$.