14.二叉堆

二叉堆

(Heap)是一类数据结构,它们拥有树状结构,且能够保证父节点比子节点大(或小)。当根节点保存堆中最大值时,称为大根堆;反之,则称为小根堆

二叉堆(Binary Heap)是最简单、常用的堆,是一棵符合堆的性质的完全二叉树。它可以实现 O(log⁡n) 地插入或删除某个值,并且 O(1) 地查询最大(或最小)值。

作为一棵完全二叉树,二叉堆完全可以用一个1-index的数组来存储,对于节点pp*2即为左儿子,p*2+1即为右节点。同时,用size记录当前二叉堆中节点的个数。

现在我们考虑如何保证二叉堆的性质不被破坏。实际上,对于一个破坏堆性质的节点,我们可以使其上浮下沉,因为最差也不过是上浮到顶或是下沉到底,所以只需要 O(log⁡n) 的时间就可以使其不再破坏性质。稍后我们会看到,插入和删除都只需要上浮/下沉一个节点。

上浮

很简单,不断与父节点比较,如果比父节点大(以大根堆为例,下同)就与之交换,直到不大于父节点或成为根节点为止。

1
2
3
4
5
void swim(int n)
{
for (int i = n; i > 1 && heap[i] > heap[i / 2]; i /= 2)
swap(heap[i], heap[i / 2]);
}

下沉

类似地,不断与较大的子节点比较,如果比它小就与之交换,直到不小于任何子节点或成为叶子节点为止。之所以要与较大的子节点比较,是为了保证交换上来的节点比两个子节点都大。

1
2
3
4
5
6
7
8
9
int son(int n) // 找到需要交换的那个子节点
{
return n * 2 + (n * 2 + 1 <= size && heap[n * 2 + 1] > heap[n * 2]);
}
void sink(int n)
{
for (int i = n, t = son(i); t <= size && heap[t] > heap[i]; i = t, t = son(i))
swap(heap[i], heap[t]);
}

插入

直接在尾部插入值,然后上浮即可。

1
2
3
4
5
void insert(int x)
{
heap[++size] = x;
swim(size);
}

删除

可以将根节点与最后一个节点交换,使size减1,然后再下沉。

1
2
3
4
5
void pop()
{
swap(heap[1], heap[size--]);
sink(1);
}

查询

直接返回根节点即可。

1
2
3
4
int top()
{
return heap[1];
}

建立

可以从一个数组 O(n)地建立堆,只需复制过来然后从底部到顶部依次下沉即可。实际上因为叶子节点不需要下沉,所以可以从 n/2 处开始遍历。

1
2
3
4
5
6
7
void build(int A[], int n) // 从一个(这里是0-index的)数组O(n)地建立二叉堆
{
memcpy(heap + 1, A, sizeof(int) * n);
size = n;
for (int i = n / 2; i > 0; --i)
sink(i);
}

使用手写的二叉堆,会比STL提供的priority_queue快一些。此外,了解其原理也有助于理解一些更高级的数据结构。接下来提供一个可以方便地在小根堆和大根堆间切换的模板(利用了宏定义):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
namespace heap
{
#define maxheap // 如果需要小根堆,把这行注释掉即可
#ifdef maxheap
#define op >
#else
#define op <
#endif
const int MAXN = 1000005;
int heap[MAXN], size;
void swim(int n)
{
for (int i = n; i > 1 && heap[i] op heap[i / 2]; i /= 2)
swap(heap[i], heap[i / 2]);
}
int son(int n)
{
return n * 2 + (n * 2 + 1 <= size && heap[n * 2 + 1] op heap[n * 2]);
}
void sink(int n)
{
for (int i = n, t = son(i); t <= size && heap[t] op heap[i]; i = t, t = son(i))
swap(heap[i], heap[t]);
}
void push(int x)
{
heap[++size] = x;
swim(size);
}
void pop()
{
swap(heap[1], heap[size--]);
sink(1);
}
int top()
{
return heap[1];
}
void build(int A[], int n)
{
memcpy(heap + 1, A, sizeof(int) * n);
size = n;
for (int i = n / 2; i > 0; --i)
sink(i);
}
} // namespace heap

0.AcWing 145. 超市

贪心策略:对于 t tt 天,我们需要在保证不卖出过期商品的前提下,卖出利润前 t tt 大的商品。

因此我们可以把商品按照过期时间排序,然后建立一个小根堆,对于每一个数而言,如果说它的过期时间大于当前小根堆的个数,那么我们可以直接将这个货物的价值加入进来,如果说当前过期时间等于这个小根堆堆内的个数,那么我们就需要对比一下,如果说这个货物的价值,是高于小根堆的堆顶的话,那么我们就将小根堆堆顶弹出,然后push我们这个新货物,因为新货物明显是更加优于堆顶的老货物的,因为每次都选择最优的选项,保证了算法的正确性。

------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧!
微信打赏