[排序算法]关于Top-k排序(优先队列Priority Queue)

在实际应用中,常有这样一种情况,对于一大堆杂乱无章的数据(大小为n),我们需要的往往只是其中最小或者最大的前k位,而之后的数据对我们没有任何意义,普通的排序算法在这个时候就显得有点不合时宜了,特别是当k << n时,简直是杀鸡用牛刀,还浪费了大量磨刀的时间。

1. Appetiser, first! 先来点开胃菜

实例:假设手头上有100万个数字,而现在只需要知道其中数值最大的100个数,那么应该怎么办?

Part I.方法选择

方案一

使用常规排序算法对所有条目进行排序,接着再选取Top-100。

这种方法之前已经说过,在这种情景下效率偏低,不太合适。

在使用快排的情况下,时间复杂度为O(nlogn)) = O(100wlog100w)

方案二

使用堆排序(Heap Sort)(或者更具体一点说应该是使用k-堆排序)[专业术语叫做:优先队列(Priority Queue)]

这便是这篇文章所要具体介绍的方法。(不过方案二给出的方法并不是最好的解决方案)

所谓k-堆排序就是创造并维护一个大小仅仅为K的堆

在此处便是维护一个大小为100(而不是100W)的大根堆,寻找最大的数嘛,正常人的第一反应肯定都是使用大根堆。

首先根据前100个元素建立起这个堆的雏形,之后对于每一个元素都进行一次资格审查,如果当前元素比100堆中的某个元素要大,则将它置换堆中;否则直接弃用(弱肉强食,适者生存)。

这一趟扫描下来,最后留在堆中的100个元素就是Top100了。

大致步骤如下(具体的细节比如swim()方法可以暂时不用管,后文会有专门的介绍,这里先看懂流程就好了):

Step.1:创造并维护k-堆
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
foreach (Element element in SourceArray) // 依次读取原始的数据元素
{
if (heap_100.Count <= 100) // 创建大根堆
{
heap_100.AppendAndSwim(element); // 在堆的最尾追加元素,并使之上浮到合适的位置
}
else // 如果堆的大小 > 100,则开始对堆进行维护操作
{
Element heap_min = heap_100.GetMin(); // 找到当前大根堆中最小的元素
if (element > heap_min) // 新元素比堆中最小的元素还要大,因此将其置换入堆
{
heap_100.delete(heap_min); // 用新的元素替换原先最小的元素
heap_100.AppendAndSwim(element); // 让新元素上浮到合适的位置
}
}
}

寻找堆内最小元素的时间复杂度为O(logk) ,每次执行上浮的时间复杂度为O(logk),因此,这样一次扫描下来建堆并维护堆的时间复杂度为O(nlogk) = O(100wlog100)

不过到这里还只是建堆并维护堆的过程,而最终需要输出这100个元素的时候还是需要做一些额外的操作的。现在暂时将该操作命名为sink(),这每一次操作都将返回堆的根节点,接着重新调整堆的序列。

构建最终结果集的大致步骤如下:

Step.2:构建结果集
1
2
3
4
5
6
7
8
9
10
11
12
while (heap_100.Count > 0)
{
Element e = heap_100.Sink(); // 返回当前堆的根节点,并将它从堆中删除,再重新对堆进行一次整理
resultList.Add(e); // 将结果添加入结果集合中
}
return resultList; // 返回最终结果集

每次Sink()的时间复杂度为O(logk),因此该步骤的时间复杂度为O(klogk) = O(100log100)

至此,整个获取Top-K的过程便结束了,总共需要的时间复杂度为O(nlogk) = O(100wlog100)

一点点小技巧:哨兵

在方案二的基础上再做一些些小小改动,让这个算法可以跑得更快

在之前的维护k-堆算法中,每一次都需要先调用FindMin()查找目前堆内元素的最小值,我们可以构建一个哨兵,使它等于当前堆中的最小值,这样每次就可以不用耗费logk的查找堆内最小值的操作了。

方案三(终极方案!)

在方案三的基础上,使用小根堆(使用小根堆寻找最大的k个值)

之前在没搞清楚这个问题的时候,上网查找相关的资料,看到很多帖子都很没头没脑的说,找k个最大值用小根堆。当时让我很费解,不太明白是怎么回事。

现在我来说明一下,其实使用小根堆的原因有两个

  • (1)维护k-堆的插入新结点和删除多余结点的操作非常简便;(最最重要的原因)

  • (2)可以用小根堆的根节点(root)直接作为哨兵元素使用。

使用了这套终极方案之后,全过程的时间复杂度为O(nlogk),虽然和方案二的时间复杂度相同,但是实际运行的效率要比它快得多,写起来也方便许多。

构建堆并进行维护的大致步骤如下:

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
foreach (Element element in SourceArray) // 依次读取原始的数据元素
{
if (heap.Count <= k) // 创建小根堆!
{
heap.AppendAndSwim(element); // 在堆的最尾追加元素,并使之上浮到合适的位置[时间复杂度:O(logk)]
}
else // 如果堆的大小>k,则开始对堆进行维护操作
{
if (element <= heap.Root) // 哨兵站岗,小于小根堆的根结点就没有必要再做操作了
continue;
if (element > heap.Root)
{
heap.Sink(element); // 用新元素置换出根结点(根节点就是最小的元素),接着调整小根堆,使新元素下沉到合适的位置[时间复杂度:O(logk)]
}
}
}
实例:使用小根堆查找最大的k个数

示意图

Part II. 堆以及堆排序的细节

一、Heap 堆

这里的堆特指二叉堆(Binary Heap),二叉堆具有如下二个特质(以大根堆为例):

  1. 父节点 >= 子节点

  2. 堆的树状结构是完全二叉树

!注意: 堆结构中并没有对左右节点的大小做要求! 并没有像查找二叉树一样规定说左节点就一定要比右节点小。

二、关于堆排序的基本操作

示意图

示意图

三、实例:使用小根堆查找最大的k个数

(上文中已经发过)

示意图

写在最后

实际情况中,碰到top-k问题时,堆排序并不是通解,还得具体情况具体分析。

  • (1)当k极小的时候,假设k<=C,这个时候之直接顺序扫描一次加上一个简单的列表存储,即可找到;
  • (2)当C<k<n/2时,堆排序就是一个很棒的选择;
  • (3)当k>n/2时,别犹豫了,直接上快排吧;