How it works
Remove the minimum from a binary min-heap and restore the heap property by sifting the new root down.
Implementation
function heapExtractMinOp(state) { const values = state.values; const n = values.length; if (n === 0) { reportNotFound(); return; } const min = values[0]; removeNode(0, min); const last = values[n - 1]; values.length = n - 1; if (values.length === 0) { finish(min); return; } values[0] = last; updateNode(0, last); const size = values.length; let i = 0; while (true) { let smallest = i; const l = 2 * i + 1; const r = 2 * i + 2; if (l < size && values[l] < values[smallest]) { smallest = l; } if (r < size && values[r] < values[smallest]) { smallest = r; } compareKeys(i, smallest); if (smallest === i) { finish(min); return; } const tmp = values[i]; values[i] = values[smallest]; values[smallest] = tmp; swapNodes(i, smallest); i = smallest; } }
def heapExtractMinOp(state): values = state.values n = values.length if (n == 0): reportNotFound() return min = values[0] removeNode(0, min) last = values[(n - 1)] values.length = (n - 1) if (values.length == 0): finish(min) return values[0] = last updateNode(0, last) size = values.length i = 0 while True: smallest = i l = ((2 * i) + 1) r = ((2 * i) + 2) if ((l < size) and (values[l] < values[smallest])): smallest = l if ((r < size) and (values[r] < values[smallest])): smallest = r compareKeys(i, smallest) if (smallest == i): finish(min) return values[i], values[smallest] = values[smallest], values[i] swapNodes(i, smallest) i = smallest
#include <vector> #include <algorithm> void heapExtractMinOp(int state) { auto values = state.values; auto n = values.length; if((n == 0)) { reportNotFound(); return; } auto min = values[0]; removeNode(0, min); auto last = values[(n - 1)]; values.length = (n - 1); if((values.length == 0)) { finish(min); return; } values[0] = last; updateNode(0, last); auto size = values.length; auto i = 0; while(true) { auto smallest = i; auto l = ((2 * i) + 1); auto r = ((2 * i) + 2); if(((l < size) && (values[l] < values[smallest]))) { smallest = l; } if(((r < size) && (values[r] < values[smallest]))) { smallest = r; } compareKeys(i, smallest); if((smallest == i)) { finish(min); return; } std::swap(values[i], values[smallest]); swapNodes(i, smallest); i = smallest; } }
public void heapExtractMinOp(int state) { var values = state.values; var n = values.length; if((n == 0)) { reportNotFound(); return; } var min = values[0]; removeNode(0, min); var last = values[(n - 1)]; values.length = (n - 1); if((values.length == 0)) { finish(min); return; } values[0] = last; updateNode(0, last); var size = values.length; var i = 0; while(true) { var smallest = i; var l = ((2 * i) + 1); var r = ((2 * i) + 2); if(((l < size) && (values[l] < values[smallest]))) { smallest = l; } if(((r < size) && (values[r] < values[smallest]))) { smallest = r; } compareKeys(i, smallest); if((smallest == i)) { finish(min); return; } { int _t = values[i]; values[i] = values[smallest]; values[smallest] = _t; } swapNodes(i, smallest); i = smallest; } }
#include <stdio.h> void heapExtractMinOp(int state) { var values = state.values; var n = values.length; if((n == 0)) { reportNotFound(); return; } var min = values[0]; removeNode(0, min); var last = values[(n - 1)]; values.length = (n - 1); if((values.length == 0)) { finish(min); return; } values[0] = last; updateNode(0, last); var size = values.length; var i = 0; while(true) { var smallest = i; var l = ((2 * i) + 1); var r = ((2 * i) + 2); if(((l < size) && (values[l] < values[smallest]))) { smallest = l; } if(((r < size) && (values[r] < values[smallest]))) { smallest = r; } compareKeys(i, smallest); if((smallest == i)) { finish(min); return; } { int _t = values[i]; values[i] = values[smallest]; values[smallest] = _t; } swapNodes(i, smallest); i = smallest; } }