python之堆heapq子產品

堆heapq子產品

堆（heap），它是一種優先隊列。優先隊列讓你能夠以任意順序添加對象，并随時（可能是在兩次添加對象之間）找出（并删除）最小的元素。相比于清單方法min，這樣做的效率要高得多。

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個 最小的元素

>>> from heapq import * 
>>> from random import shuffle 
>>> data = list(range(10)) 
>>> shuffle(data) 
>>> heap = [] 
>>> for n in data: 
... 	heappush(heap, n) 
... 
>>> heap 
[0, 1, 3, 6, 2, 8, 4, 7, 9, 5] 
>>> heappush(heap, 0.5) 
>>> heap 
[0, 0.5, 3, 6, 1, 8, 4, 7, 9, 5, 2]
           

heappush

元素的排列順序并不像看起來那麼随意。它們雖然不是嚴格排序的，但必須保證一點：位置i處的元素總是大于位置i // 2處的元素（反過來說就是小于位置2 * i和2 * i + 1處的元素）。這是底層堆算法的基礎，稱為堆特征（heap property）。

heappop

函數heappop彈出最小的元素（總是位于索引0處），并確定剩餘元素中最小的那個位于索引0處（保持堆特征）。雖然彈出清單中第一個元素的效率通常不是很高，但這不是問題，因為heappop會在幕後做些巧妙的移位操作。

>>> heappop(heap) 
0 
>>> heappop(heap) 
0.5 
>>> heappop(heap) 
1 
>>> heap 
[2, 5, 3, 6, 9, 8, 4, 7]
           

heapify

函數heapify通過執行盡可能少的移位操作将清單變成合法的堆（即具備堆特征）。如果你的堆并不是使用heappush建立的，應在使用heappush和heappop之前使用這個函數。

>>> heap = [5, 8, 0, 3, 6, 7, 9, 1, 4, 2] 
>>> heapify(heap) 
>>> heap 
[0, 1, 5, 3, 2, 7, 9, 8, 4, 6] 
           

heapreplace

函數heapreplace用得沒有其他函數那麼多。它從堆中彈出最小的元素，再壓入一個新元素。相比于依次執行函數heappop和heappush，這個函數的效率更高。

>>> heapreplace(heap, 0.5) 
0 
>>> heap 
[0.5, 1, 5, 3, 2, 7, 9, 8, 4, 6] 
>>> heapreplace(heap, 10) 
0.5 
>>> heap 
[1, 2, 5, 3, 6, 7, 9, 8, 4, 10] 
           

nlargest(n, iter)和nsmallest(n, iter)

分别用于找出可疊代對象iter中最大和最小的n個元素 。 這種任務也可通過先排序（如使用函數sorted）再切片來完成，但堆算法的速度更快，使用的記憶體更少（而且使用起來也更容易）。

import heapq
li = [6,7,9,4,3,5,8,10,1]
heapq.heapify(li)
print('the 3 largest numbers in list are:', end="")
print(heapq.nlargest(3,li))
print('the 3 smallest numbers in list are:', end="")
print(heapq.nsmallest(3,li))
output:
the 3 largest numbers in list are: [10,9,8]
the 3 smallest numbers in list are:[1,3,4]
           

時間複雜度和空間複雜度