堆与优先队列

堆(heaps)是一种特殊的数据组织方式,STL 中的 priority_queue 容器适配器底层就是采用堆来组织数据存储的。为了弄明白堆是什么,首先要搞清楚什么是树存储结构。

本节就来学习C++中点的堆于优先队列。

基本概念

堆(heap)是一种非常重要的数据结构(这里我们讨论的是二叉堆),它是一棵满足特定条件的完全二叉树,堆的定义如下:

堆是一棵树完全二叉树,对于该完全二叉树中的每一个结点x,其关键字大于等于(或小于等于)其左右孩子结点,而其左右子树均为一个二叉堆。

在上述的定义中,若堆中父亲结点关键字的值大于等于孩子结点,则称该堆为大顶堆;若堆中父亲结点关键子的值小于等于孩子结点,则称该堆为小顶堆。

由于堆是一棵完全二叉树,所以我们可以很轻易地用一个数组存储堆中的每一个元素,并且由子结点访问到其父亲结点和由父亲结点访问到其子结点

堆是一种用于查找最大值/最小值的二叉树
支持添加/减少数据,添加/删除的复杂度是O(logn),查找的复杂度是O(1)
堆的结构:

大根堆:顾名思义,根结点的值比两个子结点都大.
小根堆:顾名思义,根节点的值比两个子结点都小.
堆中结点序号:若根节点序号为1,则根节点的左结点为2(12),右结点为3(12+1)。堆的全部结点均满足该性质.

STL基本操作

1
2
3
4
5
a.size(); //返回堆内元素个数。
a.empty();//如果堆为空,返回真,否则返回假。
a.top();//返回堆顶元素。
a.pop();//删除堆顶元素,自动整理。
a.push(x);//插入一个元素x,自动整理。

优先队列

基本概念

先来回顾一下队列,队列是一种先进先出(FIFO)的数据结构,它的本质是一个线性表,只能在表的一端插入值,在表的另一端删除值。

  • 队尾(rear):允许插入的一端;
  • 队头(front):允许删除的一端。
image-20200426101423861

优先队列也是一种队列,与队列不同的是,优先队列不再遵循先入先出的原则,而是分成了两种情况:

  • 最大优先队列,无论入队顺序,当前最大的元素优先出队。
  • 最小优先队列,无论入队顺序,当前最小的元素优先出队。

对于最小优先队列,队列中的每个元素都有一个权值,权值小的优先出队。假如我们将自身的数值作为权值,那么最小优先队列中较小的数会排在队列的前面,当加入一个新值 3 时,3 会在队列中处于合适的位置。

当进行出队操作时,每次会从队首弹出队列中最小的元素:
image-20200426101437274

最大优先队列则与之相反,最先弹出队列中最大的元素。

事实上,优先队列的本质上是一个堆,它是一棵完全二叉树,分为小顶堆和大顶堆:

  • 小顶堆是每一个根节点小于左右子节点的完全二叉树,堆顶元素最小,对应最小优先队列;
  • 大顶堆是每一个根节点大于左右子节点的完全二叉树,堆顶元素最大,对应最大优先队列;

由于删除堆顶元素时的时间复杂度为 $O(\log N)$,因此在优先队列中入队和出队操作的时间复杂度也是 $O(\log N)$。

基本操作

应用示例

面试题41. 数据流中的中位数

题目描述

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

例如,

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构:

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。
示例 1:
1
2
3
4
输入:
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出:[null,null,null,1.50000,null,2.00000]
示例 2:
1
2
3
4
输入:
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出:[null,null,2.00000,null,2.50000]
解法
思路:使用堆和优先队列

我们将中位数左边的数保存在大顶堆中,右边的数保存在小顶堆中。这样我们可以在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
class MedianFinder {
priority_queue<int> lo; // 大顶堆
priority_queue<int, vector<int>, greater<int>> hi; // 小顶堆

public:
// Adds a number into the data structure.
void addNum(int num)
{
lo.push(num); // 加到大顶堆

hi.push(lo.top()); // 平衡
lo.pop();

if (lo.size() < hi.size()) { // 维护两个堆元素个数
lo.push(hi.top());
hi.pop();
}
}

// Returns the median of current data stream
double findMedian()
{
return lo.size() > hi.size() ? (double) lo.top() : (lo.top() + hi.top()) * 0.5;
}
};
复杂度分析

时间复杂度:O(logn)。堆插入和删除需要O(logn),查找中位数需要 O(1)。
空间复杂度:O(n)。

  • © 2019-2022 guoben
  • PV: UV:

微信