堆和二叉堆基础

堆 ADT / 二叉堆笔记

1. 前提条件

堆是一种常用来实现：

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

普通队列：先进先出 FIFO

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

例如：

普通队列：
先来先出

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

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

2. 核心概念

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

完全二叉树要求：

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

例如合法：

    1
  /   \
 3     5
/ \   /

7 9 8

不合法：

    1
  /   \
 3     5
  \     \
   9     8

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

3. 堆的两种类型

4. 小根堆 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

左孩子下标 = 21+1 = 3，值 7
右孩子下标 = 21+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适合查找任意值

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

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