python之堆heapq子產品

堆是一種特殊的樹形結構，通常我們所說的堆的資料結構指的是完全二叉樹，并且根節點的值小于等于該節點所有子節點的值。

堆是非線性的樹形的資料結構，有兩種堆,最大堆與最小堆。（ heapq庫中的堆預設是最小堆）

• 最大堆，樹種各個父節點的值總是大于或等于任何一個子節點的值。
• 最小堆，樹種各個父節點的值總是小于或等于任何一個子節點的值。

我們一般使用二叉堆來實作優先級隊列,它的内部調整算法複雜度為logN。

堆是一個二叉樹，其中最小堆每個父節點的值都小于或等于其所有子節點的值。

整個最小堆的最小元素總是位于二叉樹的根節點。

常用方法

heappush(heap,item)	往堆中插入一條新的值
heappop(heap)	從堆中彈出最小值
heapreplace(heap,item)	從堆中彈出最小值，并往堆中插入item   【注意：與heappushpop(heap,item)的差別在于，順序不同，這裡是先進行删除，後壓入堆】
heappushpop(heap,item)	Python3中的heappushpop更進階  【注意：相當于先操作了heappush(heap,item)，然後操作heappop(heap)】
heapify(x)	以線性時間将一個清單轉化為堆  【直接會對清單進行排序變成堆排序】
merge(*iterables,key=None,reverse=False)	合并對個堆，然後輸出
nlargest(n,iterable,key=None)	傳回可枚舉對象中的n個最大值并傳回一個結果集list
nsmallest(n,iterable,key=None)	傳回可枚舉對象中的n個最小值并傳回一個結果集list

常用方法示例：

import heapq
import random


def test():
    li = list(random.sample(range(100), 6))
    print(li)

    n = len(li)
    # nlargest
    print("nlargest:", heapq.nlargest(n, li))
    # nsmallest
    print("nsmallest:", heapq.nsmallest(n, li))
    # heapify
    print('original list is', li)
    heapq.heapify(li)
    print('heapify  list is', li)
    # heappush & heappop  
    heapq.heappush(li, 105)
    print('pushed heap is', li)
    heapq.heappop(li)
    print('popped heap is', li)
    # heappushpop & heapreplace  
    heapq.heappushpop(li, 130)  # heappush -> heappop
    print('heappushpop', li)
    heapq.heapreplace(li, 2)  # heappop -> heappush
    print('heapreplace', li)


test()
           

運作結果：

堆排序示例　

heapq子產品中有幾張方法進行排序：

方法一：

import heapq


def heap_sort(iterable):
    heap = []
    for i in iterable:
        heapq.heappush(heap, i)

    return [heapq.heappop(heap) for _ in range(len(heap))]


if __name__ == '__main__':
    li = [30, 40, 60, 10, 20, 50]
    print(heap_sort(li))
           

運作結果：

方法二（使用nlargest或nsmallest）：

import heapq

li = [30, 40, 60, 10, 20, 50]
# nlargest
n = len(li)
print("nlargest:", heapq.nlargest(n, li))
# nsmallest
print("nsmallest:", heapq.nsmallest(n, li))
           

運作結果：

方法三（使用heapify）：

import heapq


def heap_sort(list):
    print(list)
    heapq.heapify(list)
    print(list)
    heap = []

    while (list):
        heap.append(heapq.heappop(list))

    print(heap)
    li[:] = heap
    print(li)


if __name__ == '__main__':
    li = [30, 40, 60, 10, 20, 50]
    heap_sort(li)
           

運作結果：

堆在優先級隊列中的應用

　　需求：實作任務的添加，删除(相當于任務的執行)，修改任務優先級

from heapq import *
import itertools

pq = []  # list of entries arranged in a heap
entry_finder = {}  # mapping of tasks to entries
REMOVED = '<removed-task>'  # placeholder for a removed task
counter = itertools.count()  # unique sequence count


def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)


def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED


def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')