以 leetcode 23题为例说明一下python中堆和优先队列的用法。

Python 2 用法

from Queue import PriorityQueue  # python2中的包，Queue大写首字母

class Solution:
    def mergeKLists(self, lists):
        head = point = ListNode(-1)
        q = PriorityQueue()
        for l in lists:
            if l:
                q.put((l.val, l))  # put进去tuple，第一个是用于比较的值，第二个是存的信息
        while not q.empty():  # empty判空
            val, node = q.get()  # get获取最小元素
            point.next = node
            point = point.next
            node = node.next
            if node:
                q.put((node.val, node))
        return head.next

Python 3的不同点：

 
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
from queue import PriorityQueue  # 注意，3中这里变成了小写

class Solution:
    def mergeKLists(self, lists):
        head = point = ListNode(-1)
        q = PriorityQueue()
        for l in lists:
            if l:
				# 要注意这里！py3中要求put进去的元素l必须是可比较大小的，当第一个元素val相同时将根据第二个元素l的大小来比较。所以或者给ListNode类重写 eq 和 lt 函数使之变成可比较的，或者人工加一个例如id作为第二个元素来规避此问题
                q.put((l.val, id(l), l))
        while not q.empty():
            val, _, node = q.get()
            point.next = node
            point = point.next
            node = node.next
            if node:
                q.put((node.val, id(node), node))
        return head.next

PriorityQueue 其实是 heapq 做了一点简单封装，因此可以自己用heapq来做：

import heapq

class MyPriorityQueue:

    def __init__(self):
        self._index = 0
        self.queue = []

    def push(self, priority, val):
        heapq.heappush(self.queue, (priority, self._index, val))
        self._index += 1

    def pop(self):
        return heapq.heappop(self.queue)[-1]
		
	def get_top(self):
		return heapq.nsmallest(1, self.queue)[0][-1]