maxheap

A max-heap (also written maxheap) is a specialized binary heap used to implement a priority queue where the highest-priority element is always accessible in constant time. It is a complete binary tree in which every node's key is greater than or equal to the keys of its children, ensuring the maximum element sits at the root. In practice, max-heaps are usually stored in an array, which implies a fixed mapping: for a 1-based index i, the children are at 2i and 2i+1; for 0-based indexing, at 2i+1 and 2i+2. The completeness property guarantees a balanced height of O(log n).

Core operations rely on the heap property. Insertion adds a new element at the end of the array and performs a sift-up (bubble-up) until the parent is larger; this takes O(log n) time. Extracting the maximum removes the root, moves the last element to the root, and performs a sift-down (heapify) to restore order, also O(log n). Increase-key increases the value of a node and may require a sift-up. Building a heap from an arbitrary array can be done in O(n) time by applying heapify to the non-leaf nodes from right to left. Peek returns the root in O(1) time. The structure uses O(n) space.

Max-heaps are foundational for priority queues and heapsort. They are contrasted with min-heaps, in which the smallest element is at the root; by negating values or customizing comparisons, a max-heap can be adapted to various scenarios. Variants include d-ary heaps or pairing heaps, which adjust the branching factor or structure to optimize specific workloads. While efficient for prioritization tasks, a max-heap does not guarantee stability, and its performance depends on balanced behavior of the underlying array representation.