堆 (Heap)

堆是一种树状数据结构(但不必使用链实现),其性质是父节点与子节点始终有序,一般实现都会满足维护 O(logn)、查询树根 O(1) 的复杂度。

二叉堆

即使用二叉树实现的堆。二叉树的性质这里不再赘述。由于它经常使用一维数组实现,针对根节点位于 0 还是 1 下标位置,对应计算相对节点下标如下:

根节点下标为 1
#define ROOT 1
#define LEFT(i)   (2 * (i)    )
#define RIGHT(i)  (2 * (i) + 1)
#define PARENT(i) (    (i) / 2)
根节点下标为 0
#define ROOT 0
#define LEFT(i)   (2 * (i) + 1)
#define RIGHT(i)  (2 * (i) + 2)
#define PARENT(i) ((i - 1) / 2)

在堆上可以进行插入节点、删除根节点、查询根节点等操作,下面一一实现。

插入节点

先将待插入元素放到树的末尾,然后从它开始向上调整(与父节点交换)以满足堆的性质。显然该调整不会超过 O(logn) 次。

对于数组实现,可以直接取数组长度来索引到末尾位置;而简单链式实现中,要取到末尾位置还需要 O(logn) 的搜索时间,因此推荐使用数组实现,如果要尽量使用少的内存,可以使用倍增数组,调整倍增系数来优化用时和空间。

int heap[4096];
size_t n = ROOT; // 当前元素个数
#define ORDER(p, c) ((p) <= (c))
void heap_up(size_t i) {
    size_t p = PARENT(i);
    if (!ORDER(heap[p], heap[i])) {
        swap(p, i);
        heap_up(p);
    }
}

void insert(int value) {
    heap[n++] = value;
    heap_up(n - 1);
}

删除根节点

先将末尾节点塞到根节点,然后从它开始向下调整以满足堆的性质。显然复杂度仍为 O(logn)。

void heap_down(size_t i) {
    size_t l = LEFT(i), r = RIGHT(i), p = i;
    if (l < n && !ORDER(heap[p], heap[l])) p = l;
    if (r < n && !ORDER(heap[p], heap[r])) p = r;
    if (p != i) {
        swap(p, i);
        heap_down(p);
    }
}

int pop(void) {
    int value = heap[ROOT];
    heap[ROOT] = heap[--n];
    heap_down(ROOT);
    return value;
}

构造二叉堆

假设已经有一列无序元素,将其构造成符合堆的性质。如果使用 n 次插入算法,其时间复杂度为 O(nlogn)。而更优的算法是自底向上地对每个子树做上文提到的 heap_down 操作,其时间复杂度为 O(n)。

void build(void) {
    for (size_t i = PARENT(n); i > ROOT; --i)
        heap_down(i);
    heap_down(ROOT);
}

由此可以立刻得到一个 O(nlogn) 的堆排序算法,而且还是原地的(空间复杂度 O(1)),不再赘述。

合并

简单串联两个堆,然后执行一遍构造即可,复杂度为 O(lognlogk)。

其他实现

二叉堆足够简单,但是缺陷也很明显:合并复杂度高、数据量过大时父子节点不在同一个内存页,会耗费很多换页时间,查看 wiki 来对比其他实现。

配对堆(可并堆,合并两堆 O(1))

#define ORDER(p, c) ((p) <= (c))
typedef struct Node Node;
struct Node {               //   p
    int value;              //  /
    Node *child, *sibling;  // c---s
};

Node *merge(Node *a, Node *b) {
    if (!a) return b; if (!b) return a;
    if (!ORDER(a->value, b->value)) swap(a, b);
    b->sibling = a->child; a->child = b;
    return a;
}

Node *insert(Node *root, int value) {
    Node *p = malloc(sizeof(Node));
    *p = (Node) { value, NULL, NULL };
    return merge(root, p);
}

Node *merges(Node *x) {
    if (!x || !x->sibling) return x;
    Node *a = x->sibling, *b = a->sibling;
    x->sibling = a->sibling = NULL;
    return merge(merge(x, a), merges(b));
}

Node *pop(Node *root) {
    Node *p = merges(root->child);
    free(root);
    return p;
}

应用

堆排

只需原地构造堆,然后不断 pop() 出来放到数组末尾即可。

选择第 k 大/居中的元素

除了最值外,可以通过同时维护两个相反 ORDER 的堆来实现。

优先队列

直接上就行了。