当前位置:   article > 正文

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

top-k预测排序

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

Appetiser, first! 先来点开胃菜

Part I.方法选择

实例:假设手头上有100w份同学的简历,而现在只需要知道其中前100位同学的情况,那么应该怎么办?

方案一

使用常规排序算法对所有条目进行排序,接着再选取Top-100。
这种方法之前已经说过,在这种情景下效率偏低,不太合适。
在使用快排的情况下,时间复杂度为O() = O()

方案二

使用堆排序(Heap Sort)(或者更具体一点说应该是使用k-堆排序)[专业术语叫做:优先队列(Priority Queue)]
这便是这篇文章所要具体介绍的方法。(不过方案二给出的方法并不是最好的解决方案)

所谓k-堆排序就是创造并维护一个大小仅仅为K的堆
在此处便是维护一个大小为100(而不是100W)的大根堆,寻找最大的数嘛,正常人的第一反应肯定都是使用大根堆。
首先根据前100个元素建立起这个堆的雏形,之后对于每一个元素都进行一次资格审查,如果当前元素比100堆中的某个元素要大,则将它置换堆中;否则直接弃用(弱肉强食,适者生存)。这一趟扫描下来,最后留在堆中的100个元素就是Top100了。

大致步骤如下:

Step.1:创造并维护k-堆

foreach (Element element in SourceArray) // 依次读取原始的数据元素
{    
    if (heap_100.Count < 100) // 创建大根堆
    {
        heap_100.AppendAndSwim(element); // 在堆的最尾追加元素,并使之上浮到合适的位置
    }

    else // 如果堆的大小 >= 100,则开始对堆进行维护操作
    {
        Element min = heap_100.GetMin(); // 找到最小的元素

        if (element > min)
        {
            Swap(min, element);     // 用新的元素替换原先最小的元素
            heap_100.Swim(element); // 让新元素上浮到合适的位置
        }
    }

}

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

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

大致步骤如下:

Step.2:构建结果集

while (heap_100.Count > 0)
{
    Element = heap_100.Sink(); // 返回当前堆的根节点,并将它从堆中删除,再重新对堆进行一次整理
    resultList.Add(Element);   // 将结果添加入结果集合中
}

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

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

一点点小技巧:哨兵

在方案二的基础上再做一些些小小改动,让这个算法可以跑得更快
在之前的维护k-堆算法中,每一次都需要先调用FindMin()查找目前堆内元素的最小值,我们可以构建一个哨兵,使它等于当前堆中的最小值,这样每次就可以不用耗费logk的查找堆内最小值的操作了。

方案三(终极方案!)

在方案三的基础上,使用小根堆(使用小根堆寻找最大的k个值)
之前在没搞清楚这个问题的时候,上网查找相关的资料,看到很多帖子都很没头没脑的说,找k个最大值用小根堆。这当时简直是让我云里雾里,怎么也搞不明白是为什么。

现在我来说明一下,其实使用小根堆的原因有两个
(1)维护k-堆的插入新结点和删除多余结点的操作非常简便;(最最重要的原因)
(2)可以用小根堆的根节点(root)直接作为哨兵元素使用。
使用了这套终极方案之后,全过程的时间复杂度为O(),虽然和方案三的时间复杂度相同,但是运行起来肯定要比它们来得快,而且写起来也方便许多。

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

foreach (Element element in SourceArray) // 依次读取原始的数据元素
{    
    if (heap.Count < k) // 创建小根堆!
    {
        heap.AppendAndSwim(element); // 在堆的最尾追加元素,并使之上浮到合适的位置[时间复杂度:O(logk)]
    }

    else // 如果堆的大小 >= 100,则开始对堆进行维护操作
    {
        if (element < heap.Root) // 哨兵站岗,小于小根堆的根结点就没有必要再做操作了
            continue;


        if (element > min)
        {
            heap.Sink(element); // 删除根结点,并让新元素下沉到合适的位置[时间复杂度:O(logk)]
        }
    }
}

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

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

一、Heap 堆

这里的堆特指二叉堆(Binary Heap),二叉堆具有如下二个特质(以大根堆为例):
1. 父节点 >= 子节点
2. 堆的树状结构是完全二叉树
注意: 堆结构中并没有对左右节点的大小做要求! 并没有像查找二叉树一样规定说左节点就一定要比右节点小。

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


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

写在最后

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

(1)当k极小的时候,假设k <= C(一个非常小的数),甚至可以直接扫描原始数据n次从而得到k个极大/小的值。 此时时间开销为:kn;(这个C是可以大致估算出来的)
(2)当时,堆排序就是一个很棒的选择;
(3)当时,别犹豫了,直接上快排吧;

Address: http://marvin-space.info/blog/algo_priority-queue/

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/716853
推荐阅读
相关标签
  

闽ICP备14008679号