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}$

$$ \xymatrix{ &&& 8 \ar@{-}[dll] \ar@{-}[drr] \\ & 4 \ar@{-}[dl] \ar@{-}[dr] &&&& 6 \ar@{-}[dl] \\ 1 && 4 && 2 } $$

Due to the heap property, heaps have a very elegant application to the sorting problem. The heapsort is an in-place sorting algorithm centered entirely around a heap. Heaps are also used to implement priority queues.