C++语言extract_min

假设我们已经用 C++ 实现了一个最小堆，其中 `heap` 是存储堆元素的数组，`heap_size` 是堆的大小。下面是一个简单的 `extract_min` 实现：

int extract_min(int heap[], int& heap_size) {
    if (heap_size < 1) {
        // 堆为空，抛出异常或返回一个特定值
        throw exception("Heap is empty");
    }
    int min_value = heap[0];  // 取出堆顶元素
    heap[0] = heap[heap_size - 1];  // 将堆尾元素放到堆顶
    heap_size--;  // 堆的大小减一
    // 对新的堆顶元素进行下沉操作
    int i = 0;
    while (2 * i + 1 < heap_size) {  // 当前节点有左子节点
        int j = 2 * i + 1;  // 左子节点的下标
        if (j + 1 < heap_size && heap[j + 1] < heap[j]) {  // 如果存在右子节点并且右子节点更小
            j++;
        }
        if (heap[j] < heap[i]) {  // 如果子节点更小，则交换位置
            swap(heap[i], heap[j]);
            i = j;
        } else {
            break;  // 否则堆的性质已经满足，退出循环
        }
    }
    return min_value;
}

这里使用了一个 `while` 循环来进行下沉操作，从当前节点开始一直下沉到叶子节点或者堆的性质已经满足。每次比较当前节点与其子节点，选择更小的子节点进行交换。需要注意的是，如果存在右子节点并且右子节点更小，那么需要选择右子节点进行交换。最后返回取出的最小值即可。