heaporder

Heap order is the invariant that defines a heap data structure. In a heap, each node’s key is not greater than its children’s keys in a min-heap, or not less than its children’s keys in a max-heap. This heap property ensures that the root node holds the minimum (min-heap) or maximum (max-heap) element of the entire structure. The property is called the heap order, and it guarantees a quick access to the extremal element while allowing efficient updates elsewhere in the structure.

Heaps are typically implemented as nearly complete trees, commonly binary heaps, and are usually stored in arrays. The heap order concerns only the parent-child relationships; there is no requirement for a total order among siblings. As a result, the ordering is not global, and elements apart from the root may be arranged in various ways as long as the heap property holds.

Operationally, heaps support efficient priority-queue operations. Insertion adds a new element at the end and then “sifts up” to restore the heap order. Removing the root (the min or max) replaces it with the last element and then “sifts down.” Other operations include decrease-key or increase-key, which adjust a node’s key while maintaining the heap property. Time complexities are typically O(log n) for insert and extract operations, with building a heap from n elements achievable in O(n) time.

Heaps are widely used to implement priority queues and in sorting algorithms such as heapsort. The heap order guarantees quick access to the extreme element, while the rest of the elements are arranged to preserve the property.