maxheaps

A max-heap is a specialized binary heap in which the key of every node is greater than or equal to the keys of its children. This property ensures that the maximum element is always located at the root. A max-heap is a complete binary tree, and it is commonly stored in an array for efficiency. For a node at index i (0-based), the left child is at index 2i + 1, the right child at 2i + 2, and the parent at floor((i - 1) / 2). The heap maintains two properties: the shape property (the tree is complete) and the heap property (parent keys are at least as large as child keys).

The main operations are insert, extract-max, and peek. Insertion adds the new element at the end of the array and then performs a sift-up (heapify-up) to restore the heap property. Extract-max removes the root, moves the last element to the root, and performs a sift-down (heapify-down) to restore order. Peek returns the maximum element without removing it. Building a max-heap from an arbitrary array can be done in O(n) time by applying sift-down from the last non-leaf node up to the root.

Complexity considerations include O(log n) time for insert and extract-max, and O(n) time to build a max-heap from n elements. The space usage is O(n). Max-heaps are widely used to implement priority queues and are the basis of heapsort, a comparison-based sorting algorithm. They are contrasted with min-heaps, which maintain the smallest element at the root. Heaps are not stable data structures.