Let be a total order on some set . A heap is then a data structure for storing elements in . A heap is a balanced binary tree, with the property that if is a descendent of in the heap, then must hold. This property is often referred to as the heap property.
If is , then the root of the heap always gives the smallest element of the heap, and if is , then the root of the heap always gives the largest element of the heap. More generally, the root of the heap is some such that holds for all in the heap.
For example, the following heap represents the multiset for the total order on .