二叉堆

  |  

摘要: 经典的二叉堆的实现,附代码模板和应用

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


$1 二叉堆

原理

堆是一种支持插入key,删除堆顶key,查询key的最值的数据结构,二叉堆对是一种满足堆性质的完全二叉树。

小顶堆性质:树中任意一个节点的 key 都大于等于其父节点的权值
大顶堆性质:树中任意一个节点的 key 都小于等于其父节点的权值

  • 一般不支持按key操作,例如按 key 删除,按 key 修改。但是如果真有需求的话,可以通过在内部加索引的方式实现,使得给堆提供 key 之后,对内部可以找到该 key 对应的节点(数组下标),例如索引堆

代码

由于二叉堆具有完全二叉树的性质,因此采用数组实现二叉树的方式实现二叉堆。

  • 如果根节点为 1,则左子节点为 2i,右子节点为 2i + 1,父节点为 i/2
  • 如果根节点为 0,则左子节点为 2i + 1,右子节点为 2i + 2,父节点为 (i-1)/2

以根节点为 1 的大顶堆为例。

数据结构设计

data 持有数据,_size 表示元素个数。

1
2
vector<int> data; // keys
int _size;

(0) 调整节点 push_up(i), push_down(i)

当进行了插入,删除,修改等操作。数组中会有某个节点发生了改变。例如插入的时候,尾部节点发生改变;删除堆头的时候,头部节点发生改变。如果是按照索引进行删除或者修改,那么数组中间会有某个节点发生改变。

发生改变后,该节点可能就不满足堆的性质了。需要将节点进行调整。如果改变发生在数组的头部,只需要向下调整,如果改变发生在数组的尾部,只需要向上调整,如果改变发生在数组的中部,向上向下均需要调整。

向上调整 push_up

1
2
3
4
5
6
7
8
9
void push_up(int i)
{
if(i > _size) return;
while(i / 2 > 0 && data[i / 2] < data[i])
{
swap(data[i], data[i / 2]);
i /= 2;
}
}

向下调整 push_down

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void push_down(int i)
{
// ori 为下传的方向
int ori = i, left = i * 2, right = i * 2 + 1;
if(left <= _size && data[left] > data[ori])
ori = left;
if(right <= _size && data[right] > data[ori])
ori = right;
if(ori != i)
{
swap(data[i], data[ori]);
push_down(ori);
}
}

(1) 插入 push(val)

把 val 放在数组末尾,然后向上调整,直至满足堆性质

1
2
3
4
5
6
7
void push(int key)
{
if(_size + 1 >= (int)data.size())
dilatation();
data[++_size] = key;
push_up(_size);
}

扩容

1
2
3
4
5
6
7
8
void dilatation()
{
vector<int> tmp_data((_size + 1) * 2 + 1);
tmp_data[0] = 1;
for(int i = 1; i <= _size; ++i)
tmp_data[i] = data[i];
data.swap(tmp_data);
}

(2) 删除堆头 pop()

1
2
3
4
5
6
7
8
9
int pop()
{
if(empty())
return -1;
int ans = data[1];
data[1] = data[_size--];
push_down(1);
return ans;
}

(3) 查询最值 top()

1
2
3
4
5
6
int top()
{
if(empty())
return -1;
return data[1];
}

(4) 按下标删除 remove(i)

数组的下标是不对外暴露的,但是如果内部有一层索引满足外面直接删 key 的需求的话,内部通过 key 查到对应的节点位置(数组下标)之后会按照下标删除节点

删除过程是将该点与数组尾部节点交换,然后调整该点(此时该点持有的是原尾部节点的 key)。

1
2
3
4
5
6
7
8
void remove(int i)
{
if(i > _size)
return;
data[i] = data[_size--];
push_up(i);
push_down(i);
}

(5) 建堆 build(size)

给定一个数组建堆,最直观的方式是从空堆开始依次插入一个节点。时间复杂度为 $O(NlogN)$

更好的办法是将数组视为已经建好的完全二叉树,如果想用根节点为 1 的树,可以用 $O(N)$ 的时间将数组右移一位。然后自底向上建堆。

  • 自底向上枚举 i(i = size,…,2,1),向下调整 i 这个点使得 [i..size] 这若干棵树满足堆的性质。

这种枚举的方式,树的高度是逐渐变高的,假设高度为h的子树均已完成二叉堆化,那么对于高度为h+1的子树,把其根节点或底层节点做调整,最多需要h步完成二叉堆化。总时间复杂度为 $O(N)$

1
2
3
4
5
6
7
8
9
10
11
12
void build(const vector<int>& nums)
{
data.clear();
int n = nums.size();
data.assign(n + 1, 0);
data[0] = -1;
for(int i = 0; i < n; ++i)
data[i + 1] = nums[i];
_size = n;
for(int i = n; i >= 1; --i)
push_down(i);
}

建堆的时间复杂度推导

高度为 h (根的高度为 0)的满二叉树节点个数 $S(h) = 2^{h+1}-1$

第 h 层有 $2^{h}$ 个节点。

对于节点 i (1,2,…,N),其高度为 h $0,1,…,\lfloor logN\rfloor$

在高度为 h 的节点向上调整的时间复杂度为 $O(h)$,向下调整的时间复杂度为 $O(\lfloor logN\rfloor -h)$

总的时间复杂度为 $\sum\limits_{h=0}\limits^{\lfloor logN\rfloor}2^{h} \times (\lfloor logN\rfloor - h)$

记 $m = \lfloor logN\rfloor$,$ O = \sum\limits_{h=0}\limits^{m}2^{h} \times (m - h) = m \times \sum\limits_{h=0}\limits^{m}2^{h} - \sum\limits_{h=0}\limits^{m}2^{h} \times h$

记 $S = \sum\limits_{h=0}\limits^{m}2^{h} \times h$

错位相减

等比数列求和 $\sum\limits_{i=1}\limits^{m}2^{i} = \frac{2^{1}(1 - 2^{m})}{1 - 2} = 2^{m+1} - 2$

因此

总时间复杂度为 $O(N)$

完整代码和测试 (模板)

将前面分散的代码片段整合到一起,形成以下最大堆的代码模板。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class MaxHeap
{
public:
MaxHeap()
{
data.assign(0, -1);
_size = 0;
}

void build(const vector<int>& nums)
{
data.clear();
int n = nums.size();
data.assign(n + 1, 0);
data[0] = -1;
for(int i = 0; i < n; ++i)
data[i + 1] = nums[i];
_size = n;
for(int i = n; i >= 1; --i)
push_down(i);
}

int top()
{
if(empty())
return -1;
return data[1];
}

int pop()
{
if(empty())
return -1;
int ans = data[1];
data[1] = data[_size--];
push_down(1);
return ans;
}

void push(int key)
{
if(_size + 1 >= (int)data.size())
dilatation();
data[++_size] = key;
push_up(_size);
}

int size()
{
return _size;
}

bool empty()
{
return _size == 0;
}

private:
vector<int> data; // keys
int _size;

void dilatation()
{
vector<int> tmp_data((_size + 1) * 2 + 1);
tmp_data[0] = 1;
for(int i = 1; i <= _size; ++i)
tmp_data[i] = data[i];
data.swap(tmp_data);
}

void push_up(int i)
{
if(i > _size) return;
while(i / 2 > 0 && data[i / 2] < data[i])
{
swap(data[i], data[i / 2]);
i /= 2;
}
}

void push_down(int i)
{
int ori = i, left = i * 2, right = i * 2 + 1;
if(left <= _size && data[left] > data[ori])
ori = left;
if(right <= _size && data[right] > data[ori])
ori = right;
if(ori != i)
{
swap(data[i], data[ori]);
push_down(ori);
}
}
};

使用前面的代码模板,用堆排序算法解决 912. 排序数组 问题,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
MaxHeap heap;
heap.build(nums);
vector<int> result;
cout << heap.size() << endl;
while(!heap.empty())
{
cout << heap.top() << endl;
result.push_back(heap.pop());
}
reverse(result.begin(), result.end());
return result;
}
};

$2 数组的堆排序

数组上有各种排序算法:数组排序

对于堆排序,建堆和维护堆的操作都可以再输入数组上原地做。因此堆排序是数组排序中,平均时间复杂度 $O(NlogN)$ 的基础上,空间复杂度可以达到 $O(1)$ 的算法。

数组的堆排序代码

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
void heapsort(vector<int>& nums)
{
if(nums.empty())
return;
int n = nums.size();
_heapsort(nums, n);
}

void _heapsort(vector<int>& data, int size)
{
data.push_back(0);
int n = size;
for(int i = n - 1; i >= 0; --i)
data[i + 1] = data[i]; // 堆中元素在内部数组中的下标从 1 开始
for(int i = n; i >= 1; --i)
push_down(data, size, i); // 时间复杂度 O(N) 不是 O(NlogN)
for(int i = n; i >= 1; --i)
{
swap(data[1], data[size--]);
push_down(data, size, 1);
}
for(int i = 0; i < n; ++i)
data[i] = data[i + 1];
data.pop_back();
}

数组的堆排序和快排的对比

快排和堆排同样是不稳定排序,并且时间复杂度 $O(NlogN)$ 的排序。这两个的对比就比较有意思了。

  • 堆排序的时间性能略差,虽然最坏情况下堆排序可以有 $O(NlogN)$ 而快排是 $O(N${2})$,但是当数据量不很小的时候最坏情况的概率极低,而堆排序虽然是 $O(NlogG)$ 但是常数大,所以快排在实战中往往比堆排块。
  • 堆排序的空间性能略好,因为快排需要基于递归来做。

更深入的参考:


Share