[Python] heapq简介

[Python] heapq简介
judezhan 发布于 2012 年 8 月 8 日
暂无评论发表评论
假设你需要维护一个列表，这个列表不断有新的元素加入，你需要在任何时候很方便的得到列表中的最大(小)值，因此要求列表始终处于排序完毕状态，。你会怎么做？
一个最简单的方法就是每次插入新的数据时，调用一次sort方法，这样可以保证列表的顺序。在数据量很小的情况下，这种方法可行，但如果数据量很大呢？要知道，Python中列表的sort方法实现并不高明，采用了一种不太有名的自然归并排序，虽然排序开销已经被尽量的压缩了，但仍然不是很理想，复杂度大概是O(nlogn)。
有没有更好的实现方法呢？答案是肯定的！在数据结构的世界里，只有想不到，没有做不到。
另一种解决方案就是heapq，它是Python的一个标准库。heapq实现了一种叫做堆的数据结构，是一种简洁的二叉树。他能确保父节点总是比子节点小，即满足
1
2
#Python code
list[i] <= list[2*i + 1] and list[i] <= list[2*i + 2]
因此，list[0]就是最小的元素。在Python中维护一个堆最好的方式就是使用列表，并用库模块heapq来管理此列表。这个列表无需完成排序，但你却能够确保每次调用heappop从列表中获取元素时，总是当前最小的元素，然后所有节点会自动调整，以确保堆特性仍然有效。每次通过heappush添加元素或通过heappop删除元素时，开销大概是O(logn)，在数据量很大时，明显要好于排序的方法。
下面，我将通过一个例子来说明适合堆使用的场景。
假设有一个很长的列表，并且周期性的有新的数据到达，你总是希望能够从队列中获取最重要的元素，而无需不断的重新排序或在整个队列中搜索。这个概念叫做优先级队列，而堆正是最适合实现他的数据结构。注意，heapq模块在每次调用heappop时向你提供最小的元素，因此需要安排你的元素的优先级值，以反应出元素的这个特点。举个例子，假设你每次收到一个数据都付一份钱，而任何时候最重要的元素都是队列中价格最高的那个；另外对于价格相同的元素，先到达的重要一些。下面的代码就是遵循这个要求，使用heapq实现的“优先级队列”类。
1
2
3
4
5
6
7
8
9
10
11
class prioq(object):
    def __init__(self):
        self.q = []
        self.i = 0;

    def push(self, item, cost):
        heapq.heappush(self.q, (-cost, self.i, item))
        self.i += 1

    def pop(self):
        return heapq.heappop(self.q)
代码中，将价格置为负数，作为原组的第一个元素，并将整个原组压入堆中，这样更高的出价便会产生更小的原组(基于Python的自然比较方式)，在价钱之后，我们放置了一个递增索引，这样，当元素拥有相同的价钱时，先到达的元素将会处于更小的原组中。
需要说明的一点是，堆本身并不是一种有序的结构，但可以通过遍历二叉树的方式得到有序的列表。堆排序就是这么做的。
另外，Python在2.3中引入heapq模块，在2.4版本中又被重新实现和进一步优化了。更详细的使用说明，请参考Python标准库文档。