python优先级队列

四月 24th, 2009 发表评论 阅读评论

先写个python优先级队列，作为写爬虫的基础类调用。PriorityQueue直接继承list结构，主要重写了list.count()函数，直接使用二分搜索查找元素，提高效率。而元素插入的排序问题就使用标准bisect模块中的insort函数，代码比较简短，呵呵。

 

# -*- coding: utf-8 -*-

#PriorityQueue.py

import bisect

 

class PriorityQueue(list):

    "优先级队列。作者：Keengle"

    def push(self, item):

        # 按顺序插入，防止重复元素;若要按升序排列，可使用bisect.insort_left

        if self.count(item) == 0:

            bisect.insort(self, item)

        

    def pop(self):

        return list.pop(self)

        

    def empty(self):

        return len(self) == 0

        

    def remove(self,item):

        list.remove(self, item)

    

    def count(self,item):

        if len(self) == 0 :

            return 0

        #二分查找

        left = 0

        right = len(self)-1

        mid = -1

        while left <= right:

            mid = (left+right)/2

            if self[mid] < item :

                left = mid + 1

            elif self[mid] > item :

                right = mid -1

            else :

                break

        return self[mid] == item and 1 or 0

# try it

def main():

    pq = PriorityQueue()

    # add items out of order

    pq.push(2)

    pq.push(1)

    pq.push(1)

    pq.push(3)

    

    print pq.count(1)

    print pq.count(2)

    print pq.count(3)

    print pq.count(4)

    print pq.count(0)

    # print queue contents

    while not pq.empty():

        print pq.pop()

        

    print pq.count(2)

        

if __name__ == '__main__':

    main() 

 

有些论坛贴代码格式很好看,有语法高亮，不知是怎么贴的，会的朋友可以赐教一下。^-^

注：转载请注明出处http://www.kgblog.net 。

分类: python学习 标签: python  优先级队列  priority queue  (1817次阅读)