deletemin

deletemin is an operation used on priority queues and heap-based data structures to remove and typically return the smallest element, the minimum, currently stored. It is a key primitive in algorithms that repeatedly extract the next cheapest item, such as Dijkstra’s and Prim’s algorithms.

In a binary min-heap, deletemin is implemented by removing the root of the heap, replacing it with the last element in the heap, and then restoring the heap property by sifting the replacement down (down-heapifying) until the correct order is reestablished. This preserves the complete-tree structure while ensuring every parent node remains less than or equal to its children. The operation has a time complexity of O(log n), where n is the number of elements in the heap, and it uses O(1) extra space beyond the storage of the heap itself. If the heap is empty, the operation is typically defined to raise an exception or to return a sentinel value, depending on the implementation.

Deletemin is often referred to as extract-min or delete-min in various libraries and texts; the exact naming can vary, but the essential behavior is the removal of the minimum element. In more advanced heap variants, such as Fibonacci heaps or pairing heaps, delete-min remains a core operation, with amortized time complexities that are typically O(log n) for Fibonacci heaps.

Overall, deletemin is a fundamental tool for implementing efficient priority queues, enabling greedy and shortest-path algorithms to advance by always selecting the current minimal element.