堆入门以及使用堆完成排序操作

什么是堆?

堆是一种特殊的树,需要满足以下两点要求:
第一点,堆必须是一个完全二叉树。完全二叉树要求,除了最后一层,其他层的节点个数都是满的,最后一层的节点都靠左排列。

第二点,堆中的每个节点的值必须大于等于(或者小于等于)其子树中每个节点的值。实际上,可以换一种说法,堆中每个节点的值都大于等于(或者小于等于)其左右子节点的值。这两种表述是等价的。

对于每个节点的值都大于等于子树中每个节点值的堆,叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆,叫作“小顶堆”。

如下图的例子所示:

img

其中,1和2是大顶堆,3是小顶堆,4不是堆。并且,对于同一组数据,可以构建出不同形态的堆。

如何实现一个堆?

完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点。因而,可以使用数组存储堆。

img

可以看出,数组中下标为$i$的节点的左子节点位于$i2$处,右子节点位于$i2+1$处,其父节点的下标为$\frac{i}{2}$。

往堆中插入一个元素

插入一个元素后,堆的两个特性仍旧需要得到满足。

如果将新插入的元素直接放在堆的最后,会发现不符合堆的特性。因而,需要进行调整,使其重新满足堆的特性,这一过程被成为堆化。

堆化的方式有两种,一种是从下往上,一种是从上往下,首先是从下往上的方法。

img

所谓堆化,即顺着节点所在的路径,向上或者向下,对比当前节点与其父节点的元素,然后交换。

如下图所示,将新插入的节点与父节点对比大小,如果不满足子节点和父节点之间的大小关系,则交换两个节点。重复上述过程,直到父子节点之间满足大小关系。

img

将上述过程表示为代码的形式:

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 heap {
private:
vector<int> heap_data;
int max_number;
int count;
public:
heap(int capacity): max_number{capacity}{
count = 0;
heap_data.push_back(0); // 在下标为0的位置填入无意义的元素,用于占位
};
~heap() = default;

void insert(int data){
if (count > max_number) return;
count ++;
heap_data.push_back(data); // 将新插入的元素放到堆数组的末尾
int index = count;
while (index/2 > 0 && heap_data[index] > heap_data[index/2]){
int temp = heap_data[index];
heap_data[index] = heap_data[index/2];
heap_data[index/2] = temp;
index = index / 2;
}
}
};

可以看出,利用完全二叉树使用数组进行存储时的特性,很容易实现父子节点之间的对比和交换操作。

删除堆顶元素

由堆的定义可知:堆顶所存储的元素就是堆中数据的最大值或者最小值。

如果构造的是大顶堆,那么堆顶元素就是最大的元素。删除堆顶元素之后,就要把第二大的元素放到堆顶,第二大元素必然出现在左右子节点中。接着,迭代删除第二大节点,直到叶子节点被删除。

其过程如下图所示,这一删除方法存在一个问题:最后堆化得到的堆不满足完全二叉树的特性。

img

为了解决这一问题,可以采用一种从上到下的堆化方法。删除堆顶的元素后,首先将最末尾的子节点放到堆顶,接着与其子节点进行比对,如果不满足大小关系,则交换两个节点,重复上述过程,直到父子节点满足大小关系。

因为移除的是数组的最后一个元素,且在堆化的过程中,使用的都是交换操作,因而不会出现空节点,因此该方法得到的堆肯定满足完全二叉树的特性。

img

代码实现如下:

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 remove_max(){
if (heap_data.empty())
return;
// 将末尾的元素填入堆顶
heap_data[1] = heap_data[count];
count--;
heapify_up_down(1, count);
}

// 从上到下进行堆化
void heapify_up_down(int index, int end_index){
while (index <= end_index){
int max_pos = index;
if (index*2 <= end_index && heap_data[index] < heap_data[index*2]) max_pos = index * 2;
if (index*2+1 <= end_index && heap_data[max_pos] < heap_data[index*2+1]) max_pos = index * 2 + 1;
if (max_pos == index)
break;

int temp = heap_data[index];
heap_data[index] = heap_data[max_pos];
heap_data[max_pos] = temp;
index = max_pos;
}
}

对于一个完全二叉树来说,其高度最多不会超过$log_2n$。堆化的过程顺着节点所在的路径进行,因而堆化的时间复杂度和树的高度成正比,即$O(logn)$。插入数据和删除数据的主要操作是堆化,因而往堆中插入和删除一个数据的时间复杂度都是$O(logn)$。

如何基于堆实现排序?

在排序章节,有时间复杂度为$O(n^2)$的冒泡排序、插入排序和选择排序,也有时间复杂度为$O(nlogn)$的归并排序、快速排序,以及线性排序。

而在本节,借助堆实现的排序算法就叫做堆排序。其时间复杂度为$O(nlogn)$,同时,该排序算法是原地排序算法。

可以将堆排序的过程大致分解为两个步骤:建堆、排序。

建堆

对于一个数组,要将其转换为堆,存在两种方法:

  • 借助在堆中插入一个元素的思路。可以先假设起始堆中只有一个数据,即下标为1的数据;接着,调用插入操作,将下标从2到n的数据依次插入到堆中。最后,便可以得到包含n个数据的堆。
  • 在第一种思路中,从前往后对数据进行处理,并且在将每个数据插入堆中时,都是从下往上堆化。而第二种思路,是从后往前对数据进行处理,并且每个数据都是从上往下堆化。

在第二种思路中,因为叶子节点无法进行向下堆化,因而可以直接从第一个非叶子节点开始,依次向下进行堆化。第一个非叶子节点的位置为$\frac{n}{2}$(最后一个叶子节点的父节点)。

示意图如下所示:

img

img

代码如下:

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
void build_heap_from_array(vector<int> origin_array, int item_count, int item_max_number){
heap_data = std::move(origin_array);
// 在下标为0的位置插入无意义的数字
heap_data.insert(heap_data.begin(), 0);
count = item_count;
max_number = item_max_number;

for (int i=count/2; i>0; i--){
heapify_up_down(i, count);
}
}

// 从上到下进行堆化
void heapify_up_down(int index, int end_index){
while (index <= end_index){
int max_pos = index;
if (index*2 <= end_index && heap_data[index] < heap_data[index*2]) max_pos = index * 2;
if (index*2+1 <= end_index && heap_data[max_pos] < heap_data[index*2+1]) max_pos = index * 2 + 1;
if (max_pos == index)
break;

int temp = heap_data[index];
heap_data[index] = heap_data[max_pos];
heap_data[max_pos] = temp;
index = max_pos;
}
}

建堆的时间复杂度

对于节点中的每一个节点来说,要对其进行堆化,时间复杂度与其高度成正比,即$O(logn)$。

当对一个数组进行堆化时,只需要对非叶子节点进行堆化即可,即只需要堆化范围在$[\frac{n}{2}, 1]$的节点。将每一层的节点的个数和对应的高度画出图,如下所示:

img

对上述的所有节点的高度进行求和,如下式所示:

img

上述公式的求解流程如下:

img

最终求得:

img

代入$h=log_2n$,求得$S=O(n)$。

排序

在对数组进行堆化后,如何使用堆对其中的元素进行从小到大的排序?

对于大顶堆而言,其堆顶的元素是最大值。因而,可以首先将堆顶的元素和最后一个位置的元素交换,然后对剩余的$n-1$个元素执行自顶向下的堆化操作;接着,再将堆顶的元素和第$n-1$个元素进行交换,再对剩余的元素进行堆化操作;重复执行上述步骤,直到只剩余下标为1的位置的元素,即完成排序操作。其过程如下图所示:

img

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
* @brief 大顶堆上的堆排序操作
* @param origin_array: 原始未排序数组
* @param item_count: 数组中包含的元素的数目
* @param item_max_number: 数组中最多可以包含的元素的数目
*/
void sort(vector<int> origin_array, int item_count, int item_max_number){
// 从数组中构建大顶堆
build_heap_from_array(origin_array, item_count, item_max_number);
int last_index = count;
while (last_index > 1){
// 将堆顶的元素和最后一个元素交换
int temp = heap_data[1];
heap_data[1] = heap_data[last_index];
heap_data[last_index] = temp;
last_index -= 1;
heapify_up_down(1, last_index);
}
}

在堆排序的过程中,只在交换元素这一步需要额外的少量的内存空间,因而堆排序算法是原地排序算法。堆排序总共可分为两步:在建堆阶段,其时间复杂度是$O(n)$;而在排序阶段,其主要操作为自上向下的堆化操作,因而其时间复杂度为$O(nlogn)$。因此,堆排序的整体时间复杂度为$O(nlogn)$。

堆排序是不稳定的排序算法,因为在排序操作中存在将最后一个元素和堆顶元素交换的操作,因而有可能改变值相同的数据的原始相对位置。

为何快速排序比堆排序的性能好?

  • 堆排序的数据访问的方式没有快速排序友好

    对于快速排序来说,其数据是局部顺序访问的。而对于堆排序而言,其数据是跳着访问的。相比于局部顺序访问,跳着访问的方式对CPU的缓存是不友好的。

    img

  • 对于同样的数据,在排序过程中,堆排序算法的数据交换次数多于快速排序

    对于快速排序而言,其数据交换的次数不会超过数据的逆序度。

    但是堆排序的第一步是建堆,建堆的过程会打乱数据原有的相对先后顺序,导致原数据的有序度降低。对于一组有序的数据,经过建堆后,数据会变得无序。

    img

堆的应用

优先级队列

所谓优先级队列,首先是一个队列。与普通的队列相比,其最大的特点是数据的出队序列不是先进先出,而是按照元素的优先级出队,优先级最高的最先出队。

在实现优先级队列的方法中,最直接、高效的是使用堆来实现。堆和优先级队列有着非常相似的地方,优先级最高的元素相当于堆顶的元素。从优先级队列中取出优先级最高的元素,就相当于取出堆顶元素。

以下以优先级队列的一些应用场景为例:

  • 合并有序小文件: 假设我们有 100 个小文件,每个文件的大小是 100MB,每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。这里就会用到优先级队列。

    解决这一问题的思路与归并排序中的合并函数类似,首先取各个文件中的第一个字符串,放入数组中,然后比较大小,从数组中取最小的字符串放入合并后的大文件中,将其从数组中删除;接着,从该最小的字符串所对应的文件中取下一个字符串,将其放入数组中,继续取数组中的最小字符串放入大文件中,并删除;重复执行上述步骤,直到所有小文件中的字符串都被取完。

    在将小文件中的字符串放入数组中后,每次都要对整个数组进行遍历,得到其中最小的字符串,这一操作无疑是非常低效的。为了对其进行改进,就可以使用优先级队列(堆),将从小文件中取出的字符串放入到小顶堆中,那么堆顶的元素即为最小的字符串。将该字符串放入大文件中,并从堆中删除。接着再从小文件中取出下一个字符串,重复上述步骤。

  • 高性能计时器:假设我们有一个定时器,定时器中维护了很多定时任务,每个任务都设定了一个要触发执行的时间点。定时器每过一个很小的单位时间(比如 1 秒),就扫描一遍任务,看是否有任务到达设定的执行时间。如果到达了,就拿出来执行。

    但如果每隔固定时间就对任务列表进行一次扫描的操作是非常低效的,首先,其中有很多任务可能需要过很久才会被执行;其次,如果任务列表非常大,每一次扫描将非常低效。

    为了解决这一问题,可以采用优先队列的方式。按照任务设定的执行时间将任务存放在优先级队列中,队列的首位存放的是最先执行的队列。

    这样,定时器就不需要按照固定的间隔对任务列表进行扫描。转而,首先使用队首的任务的执行时间点与当前时间点作差,求出一个时间间隔$T$。在$T$时间后,定时器才会取优先级队列中的队首任务进行执行。接着,再计算新的队首任务的时间间隔$T$,再在$T$时间后再次执行上述步骤。

    这样,定时器既不需要每隔固定的时间来查询任务列表,也不需要对整个列表进行遍历,自然提高了性能。

求Top-K元素

将求Top K的问题抽象为两类:一类是针对静态数据集合,即数据集合事先确定,不会改变;另一类针对动态数据集合,即数据集合事先不确定,有数据动态地加入到集合中。

对于静态数据集合,假设数组中包含$n$个数据,要从其中查找前$K$大数据。可以采取如下的方法:维护一个大小为$K$的小顶堆(从数组中任意选取$K$个元素),对数组中的元素进行遍历,当所取出的数据比堆顶元素大时,说明数组中比堆顶元素大的元素的数目超过了$K$个,因此可以将此时的堆顶元素删除,将从数组中取出的数据插入堆中;接着继续从数组中取出数据,并执行以上过程,直到数组中的元素被遍历完。此时堆中的元素就是数组中的top-k元素。

遍历数组的时间复杂度为$O(n)$,插入数据时所执行的堆化的时间复杂度为$O(logk)$,因而,在最坏情况下,该算法的时间复杂度为$O(nlogk)$。

而对于动态数据来说,求$top-k$元素可以被分解为两步:向数组中添加数据,计算当前的top-k元素。

如果,每一次插入数据时都重新计算前top-k个元素,那么时间复杂度就是$O(nlogk)$。但是,可以进行如下的简化:如果插入的数据位于top-k的范围内,那么该数据必定比小顶堆的堆顶元素大,因而,可以一直维持一个大小为$k$的小顶堆。当插入新的数据时,就将该数据与堆顶的元素进行比较,如果比堆顶的元素大,则删除堆顶元素,将当前元素插入堆内,否则不做处理。

利用堆求中位数

如何使用堆求动态数据集合中的中位数?

中位数,顾名思义,就是处在中间位置的那个数。如果数据的个数是奇数,把数据从小到大排列,那第$ 2n+1$ 个数据就是中位数(注意:假设数据是从 0 开始编号的);如果数据的个数是偶数的话,那处于中间位置的数据有两个,第 $\frac{n}{2}$个和第 $\frac{n}{2}+1$ 个数据,这个时候,我们可以随意取一个作为中位数,比如取两个数中靠前的那个,就是第 $\frac{n}{2}$个数据。

img

对于静态数据,可以先排序,再求中位数。而对于动态数据,如果每次都重新排序,效率就比较低。

实际上,借助堆就可以很高效地实现求中位数操作。

需要维护两个堆,一个大顶堆,一个小顶堆。大顶堆存储前半部分数据、小顶堆存储后半部分数据,且小顶堆中的数据都大于大顶堆中的数据。

如果有$n$个数据,$n$是偶数时,从小到大进行排序,那么前$\frac{n}{2}$个数据存储再大顶堆中,剩余的数据存储在小顶堆中。此时,大顶堆的堆顶元素就是我们要找的中位数。如果$n$是奇数,那么大顶堆中存储$\frac{n}{2}+1$个数据,小顶堆存储$\frac{n}{2}$个数据。

img

那么,当新添加一个数据的时候,如何调整两个堆,使得大顶堆中的堆顶元素继续是中位数?

如果新加入的数据小于等于大顶堆的堆顶元素,就将这个新数据插入到大顶堆;否则,就将这个新数据插入到小顶堆。此时有可能出现两个堆的元素的数目不符合上述要求的情况。解决方法是,将一个堆中的元素移动到另一个堆中,直到满足个数要求。

img

于是,我们就可以利用两个堆,一个大顶堆、一个小顶堆,实现在动态数据集合中求中位数的操作。插入数据因为需要涉及堆化,所以时间复杂度变成了 $O(logn)$,但是求中位数我们只需要返回大顶堆的堆顶元素就可以了,所以时间复杂度就是$O(1)$。

如何求出10亿个用户搜索中的Top-10个关键词?

假设现在我们有一个包含 10 亿个搜索关键词的日志文件,如何快速获取到 Top 10 最热门的搜索关键词呢?限定条件是:将处理的场景限定为单机,可以使用的内存为 1GB。

在忽略限制条件的情况下,我们可以首先使用散列表、平衡二叉树等支持快速查找、删除的数据结构来统计每一个关键词出现的次数。以散列表为例,对10亿条数据进行遍历,对于某个关键词,到散列表中查询,如果存在该关键词,则将对应的次数加1,否则将其插入到散列表中。遍历完成后,散列表中就存储了不重复的搜索关键词及其对应的出现次数。

接着,使用前面所述的求Top-K个元素的方法,建立一个大小为10的小顶堆,对散列表进行遍历,一次取出每个搜索关键词及其对应出现的次数,与堆顶的搜索关键词对比。如果出现次数比堆顶搜索关键词的次数多,那就删除堆顶的关键词,将这个出现次数更多的关键词加入到堆中。

以此类推,当遍历完整个散列表中的搜索关键词之后,堆中的搜索关键词就是出现次数最多的 Top 10 搜索关键词了。

但是,假设10亿个关键词中不重复的关键词的个数有一亿条,如果每个搜索关键词的平均长度是 50 个字节,那存储 1 亿个关键词起码需要 5GB 的内存空间,而散列表因为要避免频繁冲突,不会选择太大的装载因子,所以会消耗更多的内存空间,不满足题目要求。

此时,可以利用相同数据经过哈希算法得到的哈希值是一样的这一特性。将10亿条关键字使用哈希算法分片到10个文件中。

具体,创建 10 个空文件 00,01,02,……,09。遍历这 10 亿个关键词,并且通过某个哈希算法对其求哈希值,然后哈希值同 10 取模,得到的结果就是这个搜索关键词应该被分到的文件编号(保证每个文件中存在大量重复的关键词)。

对这 10 亿个关键词分片之后,每个文件都只有 1 亿的关键词,去除掉重复的,可能就只有 1000 万个,每个关键词平均 50 个字节,所以总的大小就是 500MB。1GB 的内存完全可以放得下。

针对每个包含 1 亿条搜索关键词的文件,利用散列表和堆,分别求出 Top 10,然后把这个 10 个 Top 10 放在一块,然后取这 100 个关键词中,出现次数最多的 10 个关键词,这就是这 10 亿数据中的 Top 10 最频繁的搜索关键词了。

参考