堆的顺序存储与向上调整——C语言实现

如果你对树和二叉树还不熟，最好先回忆一下。堆本质上是一颗完全二叉树，但多了一个约束：每颗子树的根必须是当前子树的最大值或最小值。根最大叫大根堆，根最小叫小根堆。

因为是完全二叉树，用数组存就很方便——从上到下、从左到右依次放入。怎么维持那个约束，我们在入堆和出堆时要额外处理。顺序表的结构已经很熟悉了，直接写出来：

typedef int HPDataType;
typedef struct Heap {
    HPDataType* arr;
    int size;
    int capacity;
} HP;

初始化和销毁

跟普通顺序表一模一样，没什么好说的。

// 堆的初始化
void HPInit(HP* php) {
    assert(php);
    php->arr = NULL;
    php->size = php->capacity = 0;
}

// 堆的销毁
void HPDestroy(HP* php) {
    assert(php);
    if (php->arr) free(php->arr);
    php->arr = NULL;
    php->size = php->capacity = 0;
}

入堆与向上调整

往堆里插数据通常往数组尾部放，但这一放可能就破坏了堆的性质。比如原来是小根堆，尾部加入一个 5，它可能比父节点还小，整棵树就不再满足要求了。

这时候就需要向上调整：把新插入的节点当成孩子，跟父节点比，如果它更小就交换。父节点下标是 (child - 1) / 2。