堆 ADT / 二叉堆笔记
1. 前提条件

堆是一种常用来实现：

优先队列 Priority Queue的数据结构。

普通队列：先进先出 FIFO

优先队列：优先级最高的先出来

例如：

普通队列：
先来先出

优先队列：
分数最高 / 数值最小 / 权重最大 的先出

二叉堆是实现优先队列的常见方式，它满足“完全二叉树结构”和“堆序性质”。

2. 核心概念

二叉堆首先是一棵：完全二叉树

完全二叉树要求：

除了最后一层，其余层都满；
最后一层从左到右依次填充。

例如合法：

        1
      /   \
     3     5
    / \   /
   7   9 8

不合法：

        1
      /   \
     3     5
      \     \
       9     8

因为最后一层没有从左到右填。

3. 堆的两种类型

1. 小根堆 Min Heap

规则：

父节点 <= 子节点

也就是：堆顶最小

例如：

        1
      /   \
     3     5
    / \   /
   7   9 8

每个父节点都比孩子小。

适合：每次取最小值

2. 大根堆 Max Heap

规则：父节点 >= 子节点

也就是：堆顶最大

例如：

        9
      /   \
     7     8
    / \   /
   3   1 5

适合：每次取最大值

4. 二叉堆不是 BST

BST：

左子树 < 根 < 右子树

堆：

只要求父节点和孩子满足大小关系

例如小根堆：

父节点 <= 左孩子
父节点 <= 右孩子

但不要求：左孩子 < 右孩子

也不要求中序有序。

所以堆不能像 BST 那样查找某个普通元素。

5. 为什么二叉堆常用数组存

因为二叉堆是完全二叉树。

完全二叉树可以按层序放进数组，不需要真的用 left、right 指针。

例如：

        1
      /   \
     3     5
    / \   /
   7   9 8

数组：

下标: 0 1 2 3 4 5
值:   1 3 5 7 9 8

也就是层序存储。

数组实现二叉堆时，如果根节点在下标 0，那么对于下标 i，左孩子是 2i+1，右孩子是 2i+2，父节点是 (i-1)/2。

6. 数组下标关系

0 下标写法
当前节点：i

左孩子：2*i + 1

右孩子：2*i + 2

父节点：(i - 1) / 2

例如数组：

下标: 0 1 2 3 4 5
值:   1 3 5 7 9 8

对于下标 1：

值 = 3

左孩子下标 = 2*1+1 = 3，值 7
右孩子下标 = 2*1+2 = 4，值 9
父节点下标 = (1-1)/2 = 0，值 1
1 下标写法

当前节点：i

左孩子：2*i

右孩子：2*i + 1

父节点：i / 2

LeetCode / C 数组一般更常用：

0 下标

7. 堆 ADT 常见操作

堆一般支持：

InitHeap       初始化堆
IsEmpty        判空
Push / Insert  插入元素
Pop / Delete   删除堆顶
Top / FindMin  查看堆顶
BuildHeap      建堆

8. 插入操作：上滤

以小根堆为例。

插入新元素时：

先放到数组最后
再和父节点比较
如果比父节点小，就往上交换
直到满足堆序性质

这个过程叫：上滤
sift up / percolate up

例子，小根堆：

        2
      /   \
     5     7
    /
   10

数组：

[2,5,7,10]

插入：

1

先放最后：

[2,5,7,10,1]

对应：

        2
      /   \
     5     7
    / \
   10  1

1 比父节点 5 小，交换：

[2,1,7,10,5]

1 比父节点 2 小，交换：

[1,2,7,10,5]

最终堆顶变成 1。

9. 删除堆顶：下滤

以小根堆为例。

删除堆顶时：

1. 堆顶元素删除
2. 把最后一个元素放到堆顶
3. 和较小的孩子交换
4. 一直往下，直到满足堆序性质

这个过程叫：下滤
sift down / percolate down

例子：

[1,2,7,10,5]

删除堆顶 1。

把最后一个 5 放到堆顶：

[5,2,7,10]

对应：

        5
      /   \
     2     7
    /
   10

5 和较小孩子 2 比，交换：

[2,5,7,10]

得到：

        2
      /   \
     5     7
    /
   10

恢复小根堆。

10. 堆的结构体模板

用动态数组版，先写结构：

struct Heap {
    int* data;
    int size;
    int capacity;
};

含义：

data：数组
size：当前元素个数
capacity：最大容量

11. 小根堆核心代码
创建堆
#include <stdlib.h>

struct Heap {
    int* data;
    int size;
    int capacity;
};

struct Heap* createHeap(int capacity)
{
    struct Heap* heap =
        malloc(sizeof(struct Heap));

    heap->data =
        malloc(capacity * sizeof(int));

    heap->size = 0;
    heap->capacity = capacity;

    return heap;
}
交换
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
判空
int isEmpty(struct Heap* heap)
{
    return heap->size == 0;
}
插入：上滤
int push(struct Heap* heap, int x)
{
    if(heap->size == heap->capacity)
    {
        return 0;
    }

    int i = heap->size;
    heap->data[i] = x;
    heap->size++;

    while(i > 0)
    {
        int parent = (i - 1) / 2;

        if(heap->data[parent] <= heap->data[i])
        {
            break;
        }

        swap(&heap->data[parent], &heap->data[i]);

        i = parent;
    }

    return 1;
}

取堆顶
int top(struct Heap* heap, int* x)
{
    if(isEmpty(heap))
    {
        return 0;
    }

    *x = heap->data[0];

    return 1;
}

删除堆顶：下滤
int pop(struct Heap* heap, int* x)
{
    if(isEmpty(heap))
    {
        return 0;
    }

    *x = heap->data[0];

    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;

    int i = 0;

    while(1)
    {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = i;

        if(left < heap->size
            && heap->data[left] < heap->data[smallest])
        {
            smallest = left;
        }

        if(right < heap->size
            && heap->data[right] < heap->data[smallest])
        {
            smallest = right;
        }

        if(smallest == i)
        {
            break;
        }

        swap(&heap->data[i], &heap->data[smallest]);

        i = smallest;
    }

    return 1;
}

释放堆
void destroyHeap(struct Heap* heap)
{
    free(heap->data);
    free(heap);
}

12. 堆的遍历问题

堆一般不讨论前序、中序、后序遍历

因为堆不是为了遍历而设计的。

堆最重要的是：

快速拿到最大值或最小值

所以常用操作是：

push
pop
top

而不是遍历。

13. 堆和 BST 对比
BST：

左小右大
适合查找某个值
中序遍历有序

--------------------------------

堆：

父子满足大小关系
只保证堆顶最大/最小
适合快速取最大值/最小值
不能快速查找任意值
14. 复杂度

二叉堆插入和删除堆顶都需要沿着树高上滤或下滤，最坏复杂度是 O(log n)；查看堆顶是 O(1)。

top：
O(1)

push：
O(log n)

pop：
O(log n)

空间：
O(n)
15. 易错点
1. 堆不是有序数组

小根堆只保证：

父节点 <= 子节点

不保证：

整个数组升序

例如：

[1,3,2,8,5]

是可能合法的小根堆。

2. 堆不是 BST

BST：

左 < 根 < 右

堆：

根 < 左
根 < 右

左右孩子之间没有固定大小关系。

3. 插入是上滤

新元素先放最后。

然后：

和父节点比较
一路往上

4. 删除堆顶是下滤

堆顶删除后，把最后一个元素放到堆顶。

然后：

和更小的孩子交换
一路往下

16. 总结
堆 ADT / 二叉堆

--------------------------------

用途：实现优先队列

--------------------------------

结构：

完全二叉树

最后一层从左到右填充

--------------------------------

堆序性质：

小根堆：
    父节点 <= 子节点
    堆顶最小

大根堆：
    父节点 >= 子节点
    堆顶最大

--------------------------------

数组存储：

0下标：

左孩子：
    2*i + 1

右孩子：
    2*i + 2

父节点：
    (i - 1) / 2

--------------------------------

核心操作：

top：
    查看堆顶

push：
    插入元素
    先放最后
    再上滤

pop：
    删除堆顶
    最后一个元素放堆顶
    再下滤

--------------------------------

复杂度：

top O(1)

push O(log n)

pop O(log n)

--------------------------------

堆不是BST：

BST适合查找任意值

堆适合快速取最大/最小值

二叉堆 = 完全二叉树 + 父子堆序关系 + 数组存储。