extractMax

Extractmax is an operation on a max-priority queue or max-heap that removes and returns the element with the highest key. The element to be returned is the maximum in the data structure, and the operation maintains the remaining structure in a valid max-heap or priority queue.

In a binary max-heap implementation, the maximum element is stored at the root. To extract it, the root is replaced with the last element in the heap, the heap size is reduced by one, and a sift-down (heapify-down) process is performed from the root to restore the heap property. This yields the new maximum at the root. The time complexity is O(log n) for a heap with n elements. If the heap is empty, the operation is undefined or raises an error.

Other heap variants and advanced structures handle extractmax differently. For example, in a Fibonacci heap, removing the maximum involves removing the root from the root list, promoting its children to the root level, and then consolidating trees to maintain the structure’s amortized bounds. The amortized time for extract-max in a Fibonacci heap is O(log n). Regardless of the underlying structure, extractmax changes the size of the priority queue and may require additional updates to associated references.

Related operations include insert (to add a new element) and peek or maximum (to view the current maximum without removal). In most implementations, extractmax is paired with key-decrease or key-increase operations as part of a broader priority-queue interface.