CWYAlpha

Just another WordPress.com site

Thought this was cool: Python使用heapq实现小顶堆(TopK大)、大顶堆(BtmK小)

leave a comment »


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

import heapq
import random

class TopkHeap(object):
    def __init__(self, k):
        self.k = k
        self.data = []

    def Push(self, elem):
        if len(self.data) < self.k:
            heapq.heappush(self.data, elem)
        else:
            topk_small = self.data[0]
            if elem > topk_small:
                heapq.heapreplace(self.data, elem)

    def TopK(self):
        return [x for x in reversed([heapq.heappop(self.data) for x in xrange(len(self.data))])]

if __name__ == "__main__":
    print "Hello"
    list_rand = random.sample(xrange(1000000), 100)
    th = TopkHeap(3)
    for i in list_rand:
        th.Push(i)
    print th.TopK()
    print sorted(list_rand, reverse=True)[0:3]

上面的用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完全相同,看代码:

class BtmkHeap(object):
    def __init__(self, k):
        self.k = k
        self.data = []

    def Push(self, elem):
        # Reverse elem to convert to max-heap
        elem = -elem
        # Using heap algorighem
        if len(self.data) < self.k:
            heapq.heappush(self.data, elem)
        else:
            topk_small = self.data[0]
            if elem > topk_small:
                heapq.heapreplace(self.data, elem)

    def BtmK(self):
        return sorted([-x for x in self.data])

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

 

 
from 四号程序员: http://www.coder4.com/archives/3844

Written by cwyalpha

四月 11, 2013 在 3:23 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: