Python 堆的实现 heapq PriorityQueue

1、系统实现

堆（heap），一种数据结构，它是一种优先队列。优先队列让你能够以任意顺序添加对象，并随时（可能是在两次添加对象之间）找出（并删除）最小的元素。相比于列表方法min，这样做的效率要高得多。

1.1 heapq

实际上，Python没有独立的堆类型，而只有一个包含一些堆操作函数的模块。这个模块名为heapq（其中的q表示队列），它包含6个函数，其中前4个与堆操作直接相关。必须使用列表来表示堆对象本身。

模块heapq中一些重要的函数

• heappush(heap, x)         将x压入堆中
• heappop(heap)              从堆中弹出最小的元素
• heapify(heap)                让列表具备堆特征
• heapreplace(heap, x)      弹出最小的元素，并将x压入堆中
• nlargest(n, iter)              返回iter中n个最大的元素
• nsmallest(n, iter)            返回iter中n个最小的元素

栗子：

 1 from heapq import *
 2 
 3 arr = [10, 20, 30, 40, 2, 8, 6, 4, 3, 3, 3, 1, 7, 5, 60]
 4 heap = []
 5 for i in range(len(arr)):
 6     heappush(heap, arr[i])
 7 print("heap=", heap)
 8 
 9 print("顺序为：", end="")
10 while heap:
11     print(heappop(heap), end=" ")
12 
13 print("\n###########################################")
14 
15 heapify(arr)
16 print(arr)
17 print("顺序为：", end="")
18 while arr:
19     print(heappop(arr), end=" ")

结果如下：

heap= [1, 3, 2, 4, 3, 6, 5, 40, 10, 20, 3, 30, 7, 8, 60]
顺序为：1 2 3 3 3 4 5 6 7 8 10 20 30 40 60
###########################################
[1, 2, 5, 3, 3, 7, 6, 4, 40, 3, 20, 8, 30, 10, 60]
顺序为：1 2 3 3 3 4 5 6 7 8 10 20 30 40 60

可以看到，使用heapify和heappush方法，heap的结果是不一样的，注意区分

注意：

　　heapq的实现是小根堆。如果要实现大根堆，将入栈的元素变为相反数即可

 1 from heapq import *
 2 
 3 arr = [10, 20, 30, 40, 2, 8, 6, 4, 3, 3, 3, 1, 7, 5, 60]
 4 heap = []
 5 for i in range(len(arr)):
 6     heappush(heap, -arr[i])
 7 print("heap=", heap)
 8 
 9 print("顺序为：", end="")
10 while heap:
11     print(heappop(heap)*(-1), end=" ")

heap= [-60, -30, -40, -10, -3, -8, -20, -4, -3, -2, -3, -1, -7, -5, -6]
顺序为：60 40 30 20 10 8 7 6 5 4 3 3 3 2 1

1.2 priority_queue

queue.PriorityQueue这个优先级队列的实现在内部使用了heapq，时间和空间复杂度与heapq相同。

区别在于PriorityQueue是同步的，提供了锁语义来支持多个并发的生产者和消费者。在不同情况下，锁语义可能会带来帮助，也可能会导致不必要的开销。

调用方法：

from queue import PriorityQueue

最常用的成员函数

put(). get()取队首元素的值并将其弹出. 当优先队列为空时，调用get()不会报错，而是会一直等待取出元素，可能和 PriorityQueue 支持并发的特性有关. 

full() 判断是否为满. empty() 判断是否为空.

 1 from queue import PriorityQueue
 2 
 3 q = PriorityQueue()
 4 
 5 q.put((2, 'code'))
 6 q.put((1, 'eat'))
 7 q.put((3, 'sleep'))
 8 
 9 while not q.empty():
10     next_item = q.get()
11     print(next_item)
12 
13 # 结果：
14 #   (1, 'eat')
15 #   (2, 'code')
16 #   (3, 'sleep')

同样的，python中的priority_queue如何从大到小排?

其实解法很简单，优先队列在插入元素的时候已经对元素做了排序，把最小的元素放在队尾，那么只要在插入的时候，让最大值被判断为最小就好了。

1 items = [3,1,2]
2 pq = PriorityQueue()
3 for element in items:
4         pq.put((-element,element))
5 print (pq.get()[1])

Python在对tuple类型作比较时，采用的是按照元素顺序，找到第一个可比较的元素进行比较。

源码如下：

 1 class PriorityQueue(Queue):
 2     '''Variant of Queue that retrieves open entries in priority order (lowest first).
 3 
 4     Entries are typically tuples of the form:  (priority number, data).
 5     '''
 6 
 7     def _init(self, maxsize):
 8         self.queue = []
 9 
10     def _qsize(self):
11         return len(self.queue)
12 
13     def _put(self, item):
14         heappush(self.queue, item)
15 
16     def _get(self):
17         return heappop(self.queue)
18 
19 
20 
21 
22 def heappush(heap, item):
23     """Push item onto heap, maintaining the heap invariant."""
24     heap.append(item)
25     _siftdown(heap, 0, len(heap)-1)
26 
27 
28 
29 
30 # 'heap' is a heap at all indices >= startpos, except possibly for pos.  pos
31 # is the index of a leaf with a possibly out-of-order value.  Restore the
32 # heap invariant.
33 def _siftdown(heap, startpos, pos):
34     newitem = heap[pos]
35     # Follow the path to the root, moving parents down until finding a place
36     # newitem fits.
37     while pos > startpos:
38         parentpos = (pos - 1) >> 1
39         parent = heap[parentpos]
40         if newitem < parent:
41             heap[pos] = parent
42             pos = parentpos
43             continue
44         break
45     heap[pos] = newitem

View Code

2、自己实现

待续

今天的文章Python 堆的实现 heapq PriorityQueue分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。