数据结构——堆(优先级队列)
基本性质
优先级队列,也叫二叉堆、堆(不要和内存中的堆区搞混了,不是一个东西,一个是进程的内存区域,一个是数据结构)。
堆的本质上是一种完全二叉树,分为:
-
最小堆(小根堆):树中每个非叶子结点都不大于其左右孩子结点的值,也就是根节点最小的堆,图(a)。
-
最大堆(大根堆):树中每个非叶子结点都不小于其左右孩子结点的值,也就是根节点最大的堆,图(b)。
以下操作均以大根堆为例
存储方式
堆本质上是一颗完全二叉树,使用数组进行存储,从 a [ 0 ] a[0] a[0] 还是 a [ 1 ] a[1] a[1] 开始存储,对于索引为 k k k 的结点,其左孩子、右孩子和父节点索引情况如下:
第一个存储位置 | 左孩子 | 右孩子 | 父节点 |
---|---|---|---|
a [ 1 ] a[1] a[1] | 2 ∗ k 2*k 2∗k | 2 ∗ k + 1 2*k+1 2∗k+1 | $\left \lfloor k/2 \right \rfloor $ |
a [ 0 ] a[0] a[0] | 2 ∗ k + 1 2*k+1 2∗k+1 | 2 ∗ ( k + 1 ) 2*(k+1) 2∗(k+1) | $\left \lfloor (k-1)/2 \right \rfloor $ |
向上调整
假如我们向一个堆中插入一个元素,要使其仍然保持堆的结构。在数组的最后添加一个元素,作为堆的一个叶子结点,然后对这个元素进行向上调整;
向上调整总是把欲调整结点与父亲结点比较,如果权值比父亲结点大,那么就交换其与父亲结点,反复比较,直到到达堆顶或父亲结点的值较大为止。向上调整示意图如下:
代码如下,时间复杂度为 O ( l o g n ) O(logn) O(logn):
void heapinsert(int* arr, int n) {
int k = n;
//如果 K 结点有父节点,且比父节点的权值大
while (k > 1 && arr[k] > arr[k / 2]) {
//交换 K 与父节点的值
swap(arr[k / 2], arr[k]);
k >>= 1;
}
}
这样添加元素就很简单了
void insert(int* arr, int n, int x) {
arr[++n] = x;//将x置于数组末尾
heapinsert(arr, n);//向上调整x
}
向下调整
假如我们要删除一个堆中的堆顶元素,要使其仍然保持堆的结构。删除数组的第一个元素,把将最后一个元素移动到堆顶,然后对这个元素进行向下调整
向下调整总是把欲调整结点 K K K 与其左右孩子结点比较,如果孩子中存在权值比当前结点 K K K 大的,那么就将其中权值最大的那个孩子结点与结点 K K K,反复比较,直到到结点 K K K 为叶子结点或结点 K K K 的值比孩子结点都大为止。向下调整示意图如下:
代码如下,时间复杂度也是 O ( l o g n ) O(logn) O(logn):
void heapify(int* arr, int k, int n) {
//如果结点 K 存在左孩子
while (k * 2 <= n) {
int left = k * 2;
//如果存在右孩子,并且右孩子的权值大于左孩子
if (left + 1 <= n && arr[left] < arr[left + 1])
left++; //就选中右孩子
//如果节点 K 的权值已经大于左右孩子中较大的节点
if (arr[k] > arr[left])
break;
swap(arr[left], arr[k]);
k = left;
}
}
这样删除堆顶元素也就变得很简单了
void deleteTop(int* arr, int n) {
arr[1] = arr[n--];//用最后一个元素覆盖第一个元素,并让n-1
heapify(arr, 1, n);
}
建堆时间复杂度分析
自顶向下建堆
自顶向下建堆的思想是,从第 i = 1 i=1 i=1 个元素开始,对其进行向上调整,始终使前 i i i 个元素保持堆的结构。时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
void ArrayToHeap(int *a,int n) {
for (int i = 1; i <= n; i++) {
heapinsert(a, i);
}
}
自底向上建堆
自底向上建堆的思想是,从底 $i=\left \lfloor n/2 \right \rfloor $ 个元素开始,对其进行向下调整,始终让后 n − i n-i n−i 个元素保持堆的结构。
void ArrayToBheap(int *a, int n) {
int i = n / 2;
for (; i >= 1; i--) {
heapify(a, i, n);
}
}
如果仅从代码上直观观察,会得出构造二叉堆的时间复杂度为
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)的结果。当然这个上界是正确的,但却不是渐近界,可以观察到,不同结点在运行 heapify
的时间与该结点的树高(树高是指该结点到最底层叶子结点的值,不要和深度搞混了)相关,而且大部分结点的高度都很小。利用以下性质可以得到一个更准确的渐近界:
- 一个高度为 h h h 含有 n n n 个元素的堆,有 h = ⌊ l o g n ⌋ h=\lfloor logn\rfloor h=⌊logn⌋ ,最多包含 ⌈ n 2 k + 1 ⌉ \lceil \frac{n}{2^{k+1}} \rceil ⌈2k+1n⌉ 高度为 k k k 的结点
【可以画颗树试一下,具体证明算法导论上有】
在一个高度为
h
h
h 的结点上运行 heapify
的代价为
O
(
h
)
O(h)
O(h),我们可以将自顶向下建堆的总复杂度表示为
∑
k
=
0
h
⌈
n
2
k
+
1
⌉
O
(
h
)
=
O
(
n
∑
k
=
0
h
k
2
k
)
\sum ^{h}_{k=0} \lceil \frac {n}{2^{k+1}} \rceil O(h)= O(n\sum ^{h} _{k=0}\frac {k}{2^{k}})
k=0∑h⌈2k+1n⌉O(h)=O(nk=0∑h2kk)
这个式子
∑
k
=
0
h
k
2
k
\sum ^{h} _{k=0}\frac {k}{2^{k}}
k=0∑h2kk
求前
n
n
n 项和
T
(
k
)
=
1
2
+
2
2
2
+
3
2
3
+
⋯
+
k
2
k
1
2
T
(
k
)
=
1
2
2
+
2
2
3
+
3
2
4
+
⋯
+
k
−
1
2
k
+
k
2
k
+
1
T
(
k
)
−
1
2
T
(
k
)
=
1
2
+
1
2
2
+
1
2
3
+
⋯
+
1
2
k
−
k
2
k
+
1
1
2
T
(
k
)
=
1
2
(
1
−
(
1
2
)
k
)
1
−
1
2
−
k
2
k
+
1
T
(
k
)
=
2
−
1
2
k
−
1
−
k
2
k
T(k)=\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots+\frac{k}{2^k}\\ \frac{1}{2}T(k)=\frac{1}{2^2}+\frac{2}{2^3}+\frac{3}{2^4}+\cdots+\frac{k-1}{2^k}+\frac{k}{2^k+1}\\ T(k)-\frac{1}{2}T(k)=\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\cdots+\frac{1}{2^k}-\frac{k}{2^{k+1}}\\ \frac{1}{2}T(k)=\frac{\frac{1}{2}(1-(\frac{1}{2})^k)}{1-\frac{1}{2}}-\frac{k}{2^{k+1}}\\ T(k)=2-\frac{1}{2^{k-1}}-\frac{k}{2^{k}}
T(k)=21+222+233+⋯+2kk21T(k)=221+232+243+⋯+2kk−1+2k+1kT(k)−21T(k)=21+221+231+⋯+2k1−2k+1k21T(k)=1−2121(1−(21)k)−2k+1kT(k)=2−2k−11−2kk
到这儿就需要求极限,高等数学的知识
1
2
k
−
1
\frac{1}{2^{k-1}}
2k−11 当
k
k
k 趋于无穷大时极限是
0
0
0,对
k
2
k
\frac{k}{2^{k}}
2kk 用洛必达法则极限也是
0
0
0
也就是说当 h h h 趋向于无穷大时, O ( n ∑ k = 0 h k 2 k ) = O ( n ⋅ 2 ) O(n\sum ^{h} _{k=0}\frac {k}{2^{k}})=O(n\cdot 2) O(n∑k=0h2kk)=O(n⋅2) ,去掉常数项,所以自底向上建堆复杂度为 O ( n ) O(n) O(n)
应用举例
堆排序
堆排序的思想:假设一个大根堆有 n n n 个元素,每次把第 1 1 1 个元素,与第 n n n 个元素交换,对第一个元素进行向下调整(heapify),并使得 n = n − 1 n=n-1 n=n−1 ,直到 n = 1 n=1 n=1
void heapSort(int* arr, int n) {
//先自底向上建堆
int i = n / 2;
for (; i >= 1; i--) {
heapify(arr, i, n);
}
for (int i = 50; i > 1; i--) {
swap(arr[1], arr[i]);
heapify(arr, 1, i - 1);
}
}
寻找第K大元素
首先用数组的前k个元素构建一个小根堆,然后遍历剩余数组和堆顶比较,如果当前元素大于堆顶,则把当前元素放在堆顶位置,并调整堆(heapify)。遍历结束后,堆顶就是数组的最大k个元素中的最小值,也就是第k大元素。
void heapify(int* a, int index, int length) {
int left = index * 2 + 1;
while (left <= length) {
if (left + 1 <= length - 1 && a[left + 1] > a[left])left++;
if (a[index] > a[left])break;
swap(a[index], a[left]);
index = left;
}
}
void ArrayToBheap(int* a, int length) {
int i = length / 2 - 1;
for (; i >= 0; i--) {
heapify(a, i, length);
}
}
void FindKMax(int* a, int k, int length) {
ArrayToBheap(a, k);
for (int i = k; i < length; i++) {
if (a[i] > a[0]) a[0] = a[i];
heapify(a, 0, k);
}
}
时间复杂度 O ( n ) O(n) O(n),只是举个例子。
事实上对于这个问题是有更快的做法的,快速排序的思想,时间复杂度 O ( l o g n ) O(logn) O(logn)
int Search_K(int left, int right, int k) {
int i = left, j = right;
int p = rand() % (right - left + 1) + left;
int sign = a[p];
swap(a[p], a[i]);
while (i < j) {
while (i < j && a[j] >= sign)j--;
while (i < j && a[i] <= sign)i++;
swap(a[i], a[j]);
}
swap(a[i], a[left]);
if (i - left + 1 == k)return a[i];
if (i - left + 1 < k)return Search_K(i + 1, right, k - (i - left + 1));
else return Search_K(left, i - 1, k);
}
因为建堆 O ( n ) O(n) O(n),调整 O ( l o g n ) O(logn) O(logn),堆相对于排序最大的优势在于,当数据规模是动态增加的情况,可能需要重新排序,而堆只需要调整一下
STL priority_queue
下面为priority_queue
的模板参数,第一个为数据类型,第二个为容器类型默认vector,第三个为仿函数默认为less。
template <class _Ty, class _Container = vector<_Ty>, class _Pr = less<typename _Container::value_type>>
priority_queue默认是大根堆,基本数据类型的比较函数可以直接使用less<int>
或者greater<int>
可以满足建立大根堆或者小根堆。
#include <iostream>
#include <ctime>
#include <vector>
#include <queue>
using namespace std;
priority_queue<int>q1;//大根堆
priority_queue<int, vector<int>, greater<int>> q2;//小跟堆
int main() {
srand(time(0));
for (int i = 0; i < 10; i++) {
q1.push(rand() % 100);
q2.push(rand() % 100);
}
while (!q1.empty()) {
printf("%d ", q1.top());
q1.pop();
}
printf("\n");
while (!q2.empty()) {
printf("%d ", q2.top());
q2.pop();
}
return 0;
}
对于自定义类型,可以重载operator<或者重写仿函数
重载operator<的例子:返回true时,说明左边形参的优先级低于右边形参
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int x;
Node(int a) :x(a) {}
//返回true时,说明this的优先级低于b
bool operator<( Node b)const {
return x > b.x;//this.x大,反而优先级低,所以这是个小跟堆
}
};
返回true时,说明a的优先级低于b
//bool operator<(Node a, Node b) {
// return a.x > b.x;//a.x大,反而优先级低,所以这是个小跟堆
//}
int main() {
priority_queue<Node> q;
for (int i = 0; i < 10; ++i)
q.push(Node(rand()));
while (!q.empty()) {
printf("%d ", q.top().x);
q.pop();
}
return 0;
}
重写仿函数
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int x;
Node(int a) :x(a) {}
};
struct cmp {
bool operator() (Node a, Node b) {//默认是less函数,返回true时,左边的优先级低于右边的优先级
return a.x > b.x; //同样这是个小跟堆
}
};
int main() {
priority_queue<Node, vector<Node>, cmp> q;
for (int i = 0; i < 10; ++i)
q.push(Node(rand()));
while (!q.empty()) {
printf("%d ", q.top().x);
q.pop();
}
return 0;
}
为什么priority_queue默认是大根堆?
下面为priority_queue
的模板参数,第一个为数据类型,第二个为容器类型默认vector,第三个为仿函数默认为less。
template <class _Ty, class _Container = vector<_Ty>, class _Pr = less<typename _Container::value_type>>
这里有一点疑惑,传入的仿函数默认为less
,为什么priority_queue
默认形成大根堆?
源码剖析
less源码如下,若__Left < __Right
,则返回true:
template <class _Ty = void>
struct less {
_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty _FIRST_ARGUMENT_TYPE_NAME;
_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty _SECOND_ARGUMENT_TYPE_NAME;
_CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef bool _RESULT_TYPE_NAME;
constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const {
return _Left < _Right;
}
};
push源码如下,先在尾部插入一个元素,在向上调整堆,继续看 push_heap
函数:
void push(const value_type& _Val) {
c.push_back(_Val);
_STD push_heap(c.begin(), c.end(), comp);
}
直接继续 _Push_heap_by_index
,一堆乱七八糟看不懂的
template <class _RanIt, class _Pr>
_CONSTEXPR20 void push_heap(_RanIt _First, _RanIt _Last, _Pr _Pred) {
// push *(_Last - 1) onto heap at [_First, _Last - 1), using _Pred
_Adl_verify_range(_First, _Last);
const auto _UFirst = _Get_unwrapped(_First);
auto _ULast = _Get_unwrapped(_Last);
using _Diff = _Iter_diff_t<_RanIt>;
_Diff _Count = _ULast - _UFirst;
if (2 <= _Count) {
_Iter_value_t<_RanIt> _Val = _STD move(*--_ULast);
_Push_heap_by_index(_UFirst, --_Count, _Diff(0), _STD move(_Val), _Pass_fn(_Pred));
}
}
最后找到了我们要的东西,代码很抽象,但依稀能辨认出是向上调整的代码
template <class _RanIt, class _Ty, class _Pr>
_CONSTEXPR20 void _Push_heap_by_index(
_RanIt _First, _Iter_diff_t<_RanIt> _Hole, _Iter_diff_t<_RanIt> _Top, _Ty&& _Val, _Pr _Pred) {
// percolate _Hole to _Top or where _Val belongs, using _Pred
using _Diff = _Iter_diff_t<_RanIt>;
for (_Diff _Idx = (_Hole - 1) >> 1; // shift for codegen
_Top < _Hole && _DEBUG_LT_PRED(_Pred, *(_First + _Idx), _Val); //
_Idx = (_Hole - 1) >> 1) { // shift for codegen
// move _Hole up to parent
*(_First + _Hole) = _STD move(*(_First + _Idx));
_Hole = _Idx;
}
*(_First + _Hole) = _STD move(_Val); // drop _Val into final hole
}
关键是这一句, _DEBUG_LT_PRED(_Pred, *(_First + _Idx), _Val)
,传入的仿函数用在了这里,当 *(_First + _Idx) < _Val
时返回 true
,即当父节点的值小于新插入的值时继续调整,less函数返回true,父节点被插入结点换了下去,所以我们才可以得出上面用的结论 less函数,返回true时,左边的优先级低于右边的优先级,也就清楚了为什么默认传入less
反而形成的是大根堆。
上一篇: 数据可视化 Echarts