Python使用heapq实现小顶堆(TopK大)、大顶堆(BtmK小)

需1求:给出N长的序列,求出TopK大的元素,使用小顶堆,heapq模块实现。

上面的用heapq就能轻松搞定。

变态的需求来了:给出N长的序列,求出BtmK小的元素,即使用大顶堆。

heapq在实现的时候,没有给出一个类似Java的Compartor函数接口或比较函数,开发者给出了原因见这里:http://code.activestate.com/lists/python-list/162387/

于是,人们想出了一些很NB的思路,见:http://stackoverflow.com/questions/14189540/python-topn-max-heap-use-heapq-or-self-implement

我来概括一种最简单的:

将push(e)改为push(-e)、pop(e)改为-pop(e)。

也就是说,在存入堆、从堆中取出的时候,都用相反数,而其他逻辑与TopK完全相同,看代码:

经过测试,是完全没有问题的,这思路太Trick了……

 

 

4 thoughts on “Python使用heapq实现小顶堆(TopK大)、大顶堆(BtmK小)

  1. digiter

    如果是其他语言中unsigned类型,还有个类似的方法是push(M-e),M-pop(e),M选一个足够大的数(大于等于所有元素的最大值)

    Reply
    1. Anonymous

      是不是还是加负号取反安全点?
      PS: wp头像用的是Gravatar,id是邮箱,应该是你之前在别的相关网站更新过头像,被同步到G上了。

      Reply
      1. digiter

        用负数方便些,但如果是unsigned类型没法用负数,那就可以用我说的方法了

        Reply

Leave a Reply

Your email address will not be published.