堆
堆是一棵完全二叉树，使用数组实现堆，堆分为两种：
- 最大堆：父节点大于任意子节点（因此堆顶为最大值）
- 最小堆：父节点小于任意子节点（因此堆顶为最小值）
对于第i个节点（i从0开始计数）：
- 父节点：
(i-1)/2 - 左子节点：
2i+1 - 右子节点：
2i+2
若包含sz个节点，则第一个非叶子节点的序号为(sz - 2) / 2
插入节点
插入节点时，进行下列操作：
- 将元素添加到数组末尾；（相当于叶节点接入堆中）
- 和父节点进行比较，如果大于父节点(以最大堆为例)，则与父节点交换，一直比较交换到根节点
1/********************************************
2 * 向堆中插入元素
3 * hole：新元素所在的位置
4 ********************************************/
5template <class value>
6void _push_heap(vector<value> &arr,int hole){
7 value v = arr[hole]; //取出新元素，从而产生一个空洞
8 int parent = (hole - 1) / 2;
9 //建最大堆，如果建最小堆换成 arr[parent] > value
10 while(hole > 0 && arr[parent] < v){
11 arr[hole] = arr[parent];
12 hole = parent;
13 parent = (hole - 1) / 2;
14 }
15 arr[hole] = v;
16}
删除堆顶
删除实际上是将堆顶元素移入数组末尾，并不是真的删除。删除节点时，进行下列操作：
- 保存数组末尾元素(存如临时变量
v)，将堆顶元素存入数组末尾 - 将原来堆顶元素的两个子节点中较大的一个移入堆顶(以最大堆为例)，填补空缺，此时产生新的空缺，继续此步骤，直到空缺为一个叶子节点
- 将
v中存储的值移到空缺叶子节点的位置 - 对上一步中的新叶子节点完成向上比较交换操作
1/********************************************
2 * 删除堆顶元素
3 ********************************************/
4template <class value>
5void _pop_heap(vector<value> &arr,int sz)
6{
7 value v = arr[sz - 1];
8 arr[sz - 1] = arr[0];
9 --sz;
10 int hole = 0;
11 int child = 2 * (hole + 1); //右孩子
12 while(child < sz){
13 if(arr[child] < arr[child - 1])
14 --child;
15 arr[hole] = arr[child];
16 hole = child;
17 child = 2 * (hole + 1);
18 }
19 if(child == sz){
20 arr[hole] = arr[child - 1];
21 hole = child - 1;
22 }
23 arr[hole] = v;
24 _push_heap(arr,hole);
25}
建堆
- 堆的大小固定(且所有元素已知)：按“序号从大到小”的顺序遍历所有非叶子节点，将这些节点与左右子节点较大者(以最大堆为例)交换，执行siftdown一直到叶子节点，因此，每遍历到一个节点时，其左子树和右子树都已经是最大堆，只需对当前节点执行siftdown操作
- 堆的大小未知(如数据流)：可以通过插入操作来构建堆
1/********************************************
2 * 建堆
3 * sz：删除堆顶元素后的大小
4 * v： 被堆顶元素占据的位置原来的元素的值
5 ********************************************/
6template <class value>
7void _make_heap(vector<value> &arr)
8{
9 int sz = arr.size();
10 int parent = (sz - 2) / 2;
11 while(parent >= 0){
12 int hole = parent;
13 int child = 2 * (hole + 1); //右孩子
14 value v = arr[hole];
15 while(child < sz){
16 if(arr[child] < arr[child - 1])
17 --child;
18 arr[hole] = arr[child];
19 hole = child;
20 child = 2 * (hole + 1);
21 }
22 if(child == sz){
23 arr[hole] = arr[child - 1];
24 hole = child - 1;
25 }
26 arr[hole] = v;
27 _push_heap(arr,hole);
28 --parent;
29 }
30}
复杂度
- 插入节点：时间复杂度为O(logn)
- 删除堆顶：时间复杂度为O(logn)
- 建堆：
- 堆的大小固定(且所有元素已知)：每个siftdown操作的最大代价是节点被向下移动到树底的层数。在任意一棵完全二叉树中，大约有一半的节点是叶节点，因此不需要向下移动。四分之一的节点在叶节点的上一层，这样的节点最多只需要移动一层。每向上一层，节点的数目就为前一层的一般，而子树高度加1，因此移动层数加一。时间复杂度为O(n)
- 堆的大小未知(如数据流)：由于插入节点的时间代价为O(logn)，对于n个元素，每个执行一次插入操作，所以时间复杂度为O(nlogn)