extractmin

Extractmin is an operation used with priority queues and heap-based data structures to remove and return the element with the smallest key. It is essential in algorithms that repeatedly select the next best element, such as Dijkstra's shortest path, Prim's minimum spanning tree, and event-driven simulations. The operation typically returns the minimum element and adjusts the queue to preserve its ordering properties.

Implementation and complexity: In a binary min-heap, extractmin removes the root, moves the last element to the root, reduces the size, and performs a heapify-down (sift-down) procedure to restore the heap property. The time complexity is O(log n). In other heap variants, such as binomial heaps, Fibonacci heaps, or pairing heaps, the amortized or worst-case complexity may differ, but extract-min generally requires reorganization of the heap structure to consolidate or link elements so that the minimum element can be efficiently tracked.

Variants and semantics: Some libraries expose extractmin as delete-min or extract, returning the minimum key and possibly the associated payload. If the heap is empty, the operation returns an error or a sentinel value. Duplicates are typically handled by the underlying ordering and may be returned in arbitrary order relative to equal keys.

Notes: The operation is distinct from peek (or minimum), which observes the minimum without removal. Example: in a binary min-heap containing elements with keys [1, 3, 5, 7, 9], extractmin would return 1 and reorganize the remaining elements to maintain the heap property.