python deque heapq詳解

概念

deque子產品是python标準庫collections中的一項，它提供了兩端都可以操作的序列，這意味着，在序列的前後你都可以執行添加或删除操作。

使用deque(maxlen=N) 構造函數會建立一個固定大小的隊列。當新的元素加入并且這個隊列已經滿的時候， 最老的元素會被替換掉的。

from collections import deque
q = deque(maxlen=)
q.append()
q.append()
q.append()
print(q) #deque([1, 2, 3], maxlen=3)
q.append()
q.append()
print(q) # deque([3, 4, 5], maxlen=3)
           

可以在隊列的兩端 增加删除

q.appendleft()
print(q) #deque([6, 3, 4], maxlen=3)

p = q.pop()
print(p) #4
print(q) #deque([6, 3], maxlen=3)
print(q.popleft()) #6
           

擷取最大或者最小的N個元素

使用heapq 解決

import heapq

"""擷取最大或者最小的元素"""
nums = [,, ,, , ,,,,]
print(heapq.nlargest(, nums)) #[52, 44, 34]
print(heapq.nsmallest(, nums)) #[1, 2, 3]
           

接受關鍵字參數， 用于複雜的資料結構

portfolio = [
    {'name': 'IBM', 'shares': , 'price': },
    {'name': 'AAPL', 'shares': , 'price': },
    {'name': 'FB', 'shares': , 'price': },
    {'name': 'HPQ', 'shares': , 'price': },
    {'name': 'YHOO', 'shares': , 'price': },
    {'name': 'ACME', 'shares': , 'price': }
]
cheap = heapq.nlargest(, portfolio, key=lambda s: s['price'])
expensive = heapq.nsmallest(, portfolio, key=lambda s: s['price'])

print(cheap)
# [{'name': 'AAPL', 'shares': 50, 'price': 543.22}, {'name': 'ACME', 'shares': 75, 'price': 115.65}, {'name': 'IBM', 'shares': 100, 'price': 91.1}]
print(expensive)# [{'name': 'YHOO', 'shares': 45, 'price': 16.35}, {'name': 'FB', 'shares': 200, 'price': 21.09}, {'name': 'HPQ', 'shares': 35, 'price': 31.75}]
           

以上進行比較的時候是根據price 進行比較的， 支援key , 就像是sorted 排序一樣

總結：

對于取最大值最小值， 幾種方法比較和使用

- heapq.nlargest() : 當查找的元素個數相對比較小的時候

- max(),min() : 當僅僅查找唯一的最大值最小值時候

- sorted(items, key=) [:N】： 當N的大小和集合的大小比較接近時候，通常先排序再切片操作

heapq 的使用

下面是對應的函數

heapq.heappush(heap, item) 把item添加到heap中（heap是一個清單）

heapq.heappop(heap) 把堆頂元素彈出，傳回的就是堆頂

heapq.heappushpop(heap, item) 先把item加入到堆中，然後再pop，比heappush()再heappop()要快得多

heapq.heapreplace(heap, item) 先pop，然後再把item加入到堆中，比heappop()再heappush()要快得多

heapq.heapify(x) 将清單x進行堆調整，預設的是小頂堆

heapq.merge(*iterables) 将多個清單合并，并進行堆調整，傳回的是合并後的清單的疊代器

heapq.nlargest(n, iterable, key=None) 傳回最大的n個元素（Top-K問題）

heapq.nsmallest(n, iterable, key=None) 傳回最小的n個元素（Top-K問題）

實作按照優先級排列的隊列

print("heapq 是基于heap 堆的優先排序的算法")
import heapq


class PriorityQueue(object):
    def __init__(self):
        self._queue = []
        self._index = 

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 

    def pop(self):
        return heapq.heappop(self._queue)[-]

class Item(object):
    def __init__(self, name):
        self.name = name
    def __repr__(self):
        return 'Item({!r})'.format(self.name)

q = PriorityQueue()
q.push(Item('foo'), )
q.push(Item('bar'), )
q.push(Item('spam'), )
q.push(Item('grok'), )

print(q.pop()) # Item('bar')
print(q.pop()) # Item('spam')
print(q.pop()) #  Item('foo')
           

按照優先級等級（下面這個是上面的簡化版）

import heapq
import random
# mylist = list(random.sample(range(100), 10))
mylist = []
heapq.heappush(mylist, (-, , , ))
heapq.heappush(mylist, (-, , , ))
heapq.heappush(mylist, (, , , ))


print(mylist) #[(-6, 2, 3, 1), (-3, 2, 3, 5), (5, 2, 3, 7)]
print(heapq.heappop(mylist)) # (-6, 2, 3, 1)
print(heapq.heappop(mylist)[-]) #5
print(heapq.heappop(mylist)[-])# 7
           

分析：

第一個代表的是權重， 如果使用元組， 相同權重的優先級不能進行比較的。 是以在PriorityQueue 類的push方法 中使用了一個index 就確定了在第一個元素， 權重相同的情況下，就會直接 根據index 來進行排序和權重，這樣 最後一個元素不是可疊代，不能進行排序的時候就不會報錯，又可以取到。 是以中間用一個index 來進行自加， 這樣就避免了這個出現重複的問題權重問題。排序是按照先後順序的。

字典映射等多個值

print('=========')
from collections import defaultdict
d = defaultdict(list)
d['a'].append()
d['a'].append()
d['a'].append()

print(d) # defaultdict(<class 'list'>, {'a': [1, 2, 4]})
print(d['a']) #[1, 2, 4]

print("======set()")
d = defaultdict(set) # 是list 添加還是set添加在defaultdict() 中定義
d['a'].add()
d['a'].add()
d['b'].add()
print(d) # defaultdict(<class 'set'>, {'a': {1, 3}, 'b': {9}})

           

建立多值映射字典

d = defaultdict(list)
for key, value in pairs:
    d[key].append(value)