隊列和優(yōu)先隊列（Priority Queue）

隊列是一種可以完成插入和刪除的數(shù)據(jù)結(jié)構(gòu)。普通隊列是先進先出（FIFO), 即先插入的先被刪除。

然而在某些時候我們需要按照任務的優(yōu)先級順序來決定出隊列的順序，這個時候就需要用到優(yōu)先級隊列了。優(yōu)先隊列是一種可以完成插入和刪除最小元素的數(shù)據(jù)結(jié)構(gòu)

python中有現(xiàn)成的優(yōu)先隊列類可以調(diào)用。

代碼示例

from queue import Queue   # 隊列，F(xiàn)IFO
from queue import PriorityQueue  #優(yōu)先級隊列，優(yōu)先級高的先輸出
###############隊列（Queue）的使用，/python中也可是用列表（list）來實現(xiàn)隊列###############
q = Queue(maxsize) 	#構(gòu)建一個隊列對象，maxsize初始化默認為零，此時隊列無窮大
q.empty()		#判斷隊列是否為空(取數(shù)據(jù)之前要判斷一下)
q.full()		#判斷隊列是否滿了
q.put()			#向隊列存放數(shù)據(jù)
q.get()			#從隊列取數(shù)據(jù)
q.qsize()		#獲取隊列大小，可用于判斷是否滿/空
###用法示例：
>>> q = Queue(3)
>>> for i in range(3):
>>>	q.put(i)
>>> q.full()
True
>>> while not q.empty():
>>> 	print(q.get())
0
1
2
###############優(yōu)先隊列（PriorityQueue）的使用###############
"""
隊列的變體，按優(yōu)先級順序（最低優(yōu)先）檢索打開的條目。
條目通常是以下格式的元組：
插入格式：q.put((priority number, data))
特點：priority number 越小，優(yōu)先級越高
其他的操作和隊列相同
"""
>>> q = PriorityQueue()
>>> q.put((2, "Lisa"))
>>> q.put((1, "Lucy"))
>>> q.put((0, "Tom"))
>>> i = 0
>>> while i < q.qsize()：
>>> 	print(q.get())
(0，"Tom")
(1，"Lucy")
(2，"Lisa")
#可見并沒有按照輸入的順序輸出的，而是按照優(yōu)先級順序輸出的
#優(yōu)先獨隊列的實質(zhì)是

堆（heap）

看完上面的示例我們也許會有疑惑，優(yōu)先隊列是如何來實現(xiàn)的了？

----------優(yōu)先隊列的實質(zhì)是每次插入時按照一定的規(guī)則插入，刪除時直接找到最小的那個元素彈出即可。插入和彈出最壞情況下的時間復雜度都是O(LogN)

下面我們就來介紹實現(xiàn)優(yōu)先隊列的一種數(shù)據(jù)結(jié)構(gòu)——堆(heap)。

簡介

堆的實質(zhì)是一個完全二叉樹(除最底層外，其余層都是滿二叉樹，且最底層的節(jié)點從左往右順序排列)。 堆主要分為大頂堆和小頂堆兩種

1.大頂堆：每個分支的根節(jié)點都大于等于其子節(jié)點。（ki >= k2i）and (ki >= k2i+1)

2.小頂堆：每個分支的根節(jié)點都小于等于其子節(jié)點。（ki <= k2i）and (ki <= k2i+1)

所以堆中的第i個元素的父親是floor(i/2)（向下取整）, 第i個元素的左右孩子分別是2i和2i+1

堆的根節(jié)點要從1開始計算，不能從0開始計算。(假如從零開始i=2時其父親節(jié)點為floor(2/2)=1, 顯然是錯誤的)

初始化構(gòu)建堆

將一個有k個元素的數(shù)組構(gòu)成一個大頂堆或者小頂堆。時間復雜度O(n)$

核心思路：從下往上，從右往左，且每次都從第floor(k/2)個元素開始進行調(diào)整依次遞減直到根節(jié)點

1.從floor(k/2)個元素開始進行調(diào)整，調(diào)整完畢，則i--；
    #調(diào)整節(jié)點，每次只調(diào)整該根節(jié)點以下的子樹
    while i <= k
        1.1 找出左右孩子中最大的那個
        1.2 該節(jié)點和較大的那個子節(jié)點比較，
                如果父節(jié)點較大，break
                如果子節(jié)點較大，記錄子節(jié)點的索引，把子節(jié)點的值給父節(jié)點
        1.3 將上面較大的那個字節(jié)點作為新的父節(jié)點開始一輪循環(huán)
    循環(huán)結(jié)束后，將父節(jié)點的值放到他應該去的子節(jié)點的位置上

例如有如下數(shù)組

把其轉(zhuǎn)化成完全二叉樹的形式就是

該數(shù)組一共有9個元素，所以從i = floor(9/2)=4 個元素開始，第4個元素是6, 其右孩子9最大，將6和9交換完成一次調(diào)整.

i=3,第三個元素是8,8比左右孩子都大，不用交換

i=2,此時的子樹是：第二個元素是2,而此時以2為根節(jié)點的子樹如下左圖。交換過程為: a).2與9交換，此時的根節(jié)點就到了2現(xiàn)在的位置 (下中圖)。b).2與7交換。 c)交換完成，本次調(diào)整完畢

i=1,此時的父節(jié)點就是整棵樹的根節(jié)點,而此時整棵樹的狀態(tài)是下圖所示

a). 5和9交換，此時5到了9的位置(下左圖) b). 5和7交換，5到了7的位置(下中圖) c).最后5和6交換，完成調(diào)整。

經(jīng)過以上的floor(k/2)次的調(diào)整之后，由一個無序數(shù)組初始化構(gòu)建大頂堆就完成了

堆的插入（節(jié)點上?。?/h3>

時間復雜度O(log(k+1))

我們之前由一個無序數(shù)組構(gòu)造了一個大頂堆，那么現(xiàn)在我們要插入一個新的元素該怎么辦了，如下圖，如果直接在最末尾插入，則破壞了堆的結(jié)構(gòu)，所以還需要按進行調(diào)整。

調(diào)整規(guī)則：由于其他子樹的順序都已經(jīng)調(diào)整完畢，所以只需要調(diào)整根節(jié)點到插入節(jié)點所在的子路即可。

如下圖所示。(a)將11與4調(diào)整，(b)將11與7調(diào)整，©再將11與9調(diào)整。最后得到調(diào)整完畢的結(jié)果。

堆的刪除(節(jié)點下浮)

時間復雜度O(log(k-1))

由于堆是隊列結(jié)構(gòu)，只能從堆中刪除堆頂?shù)脑?。移除堆頂元素之后，之前的完全二叉樹就變成來兩個子樹，次數(shù)最方便的做法就是用堆的最后一個節(jié)點來填補取走的堆頂元素，并將堆的實際元素個數(shù)減1。但是這樣做以后又不滿足堆的定義了，還是要進行調(diào)整。

調(diào)整規(guī)則：從根節(jié)點開始逐層向下調(diào)整即可。

（a).將5與8調(diào)換，(b)調(diào)整完成，刪除完畢

堆的應用

之間講過的利用堆(python中是小頂堆)來實現(xiàn)優(yōu)先隊列

利用堆求Top k：

假如現(xiàn)在有1億個數(shù)據(jù)要求其中前十個最小的元素。最笨方法就是對所有數(shù)據(jù)進行排序，然后找出前十個最小的，即使使用快排，也需要O(NlogN)的時間復雜度。假如利用大頂堆的話–先利用前10個數(shù)據(jù)構(gòu)造一個大頂堆，然后順序遍歷數(shù)組與大頂堆頂點比較，假如比大于等于頂點直接刪除，否則就刪除堆頂點并插入新的節(jié)點，最后堆里面的元素就是最小的前是個元素。這樣求出來的時間復雜度為Nlog(k)

假如要求前十個最大的元素，那就要使用小頂堆來實現(xiàn)

最后放上python手動實現(xiàn)將數(shù)組轉(zhuǎn)化為大頂堆和小頂堆的代碼

class Heap:
	def __init__(self, _list):
		self._list = _list
		self.k = len(_list)
		
	def _bigHeapAdjuest(self, j):
		temp = self._list[j] #存放當前雙親節(jié)點的值,j代表當前節(jié)點的位置
		i = 2*j  			 #j的左孩子
		while i <= self.k:
			if i < self.k and self._list[i] < self._list[i+1]:  #i==n時由于只有一個子節(jié)點，所以沒有比較的必要
				i += 1
			#與雙親比較，如果雙親大則跳過
			#如果雙親小，就把大的給雙親
			if temp >= self._list[i]:
				break                 			#沒有必要修整
			self._list[j] = self._list[i]       #元素交換
			j = i                               #j記錄著temp應該去的位置,由于這個位置的節(jié)點發(fā)生了變動，所以需要再次調(diào)整
			i *= 2             					#接著找該節(jié)點的左孩子
		self._list[j] = temp	
	
    def _smallheapAdjuest(self, j):
        temp = self._list[i] #父節(jié)點
        i = 2*j  #左孩子
        while i <= self.k:
            if i < self.k and self._list[i] > self._list[i+1]:    #找最小的那個孩子
                i += 1
            #構(gòu)建小頂堆，小于父節(jié)點的都要上浮
            if self._list[i] >= temp:
                break
            self._list[j] = self._list[i]  #子節(jié)點交給父節(jié)點
            j= i    #記錄父節(jié)點應該去的索引位置
            i *= 2
        self._list[j] = temp
	
	def heapSort(self):
		self._list.insert(0, -1) 
		s = self.length // 2  
		#構(gòu)建大頂堆
		for j in range(s, 0, -1):
			self._bigHeapAdjuest(j) 
		#構(gòu)建小頂堆
			for j in range(s, 0, -1):
			self._SmallheapAdjuest(j) 
		

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論