堆

堆

简介

可以称作完全二叉树，数组的[t]位置的左儿子和右儿子对应的位置分别为[2t]和[2t + 1]，父亲节点的位置为[t / 2]

大根堆

父节点中的值大于两个子节点中的值，根节点最大的堆称为大根堆

小根堆

父节点中的值小于两个子节点中的值，根节点最小的堆称为小根堆

插入操作

// 以小根堆为例
void insert(int x) {
    heap[++len] = x; //先将元素放到数组末尾
    up(len);
}
void up(int k) {
    while (k > 1 && heap[k] < heap[k / 2]) {
        swap(heap[k], heap[k / 2]);
        k = k / 2;
    }
}

删除操作

// 删除堆顶元素
void delete() {
    swap(heap[1], heap[len]); // 先将堆顶元素与数组末尾元素交换
    --len;
    down(1);
}
void down(int k) {
    while (k + k <= len) {
        int j = k + k;
        if (j + 1 <= len && heap[j + 1] < heap[j])
            ++j;
        if (heap[k] <= heap[j])
            break;
        swap(heap[k], heap[j]);
        k = j;
    }
}
// 删除堆中任意元素
void delete(int pos) {
    if (pos == len) {
        --len;
        return;
    }
    int x = heap[pos], y = heap[len];
    swap(heap[pos], heap[len]);
    --len;
    up(pos);
    down(pos);
}