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

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

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

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

代碼示例

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

堆（heap）

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

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

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

簡(jiǎn)介

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

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

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

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

堆的根節(jié)點(diǎn)要從1開(kāi)始計(jì)算，不能從0開(kāi)始計(jì)算。(假如從零開(kāi)始i=2時(shí)其父親節(jié)點(diǎn)為floor(2/2)=1, 顯然是錯(cuò)誤的)

初始化構(gòu)建堆

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

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

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

例如有如下數(shù)組

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

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

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

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

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

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

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

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

時(shí)間復(fù)雜度O(log(k+1))

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

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

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

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

時(shí)間復(fù)雜度O(log(k-1))

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

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

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

堆的應(yīng)用

之間講過(guò)的利用堆(python中是小頂堆)來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列

利用堆求Top k：

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

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

最后放上python手動(dòng)實(shí)現(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] #存放當(dāng)前雙親節(jié)點(diǎn)的值,j代表當(dāng)前節(jié)點(diǎn)的位置
		i = 2*j  			 #j的左孩子
		while i <= self.k:
			if i < self.k and self._list[i] < self._list[i+1]:  #i==n時(shí)由于只有一個(gè)子節(jié)點(diǎn)，所以沒(méi)有比較的必要
				i += 1
			#與雙親比較，如果雙親大則跳過(guò)
			#如果雙親小，就把大的給雙親
			if temp >= self._list[i]:
				break                 			#沒(méi)有必要修整
			self._list[j] = self._list[i]       #元素交換
			j = i                               #j記錄著temp應(yīng)該去的位置,由于這個(gè)位置的節(jié)點(diǎn)發(fā)生了變動(dòng)，所以需要再次調(diào)整
			i *= 2             					#接著找該節(jié)點(diǎn)的左孩子
		self._list[j] = temp	
	
    def _smallheapAdjuest(self, j):
        temp = self._list[i] #父節(jié)點(diǎn)
        i = 2*j  #左孩子
        while i <= self.k:
            if i < self.k and self._list[i] > self._list[i+1]:    #找最小的那個(gè)孩子
                i += 1
            #構(gòu)建小頂堆，小于父節(jié)點(diǎn)的都要上浮
            if self._list[i] >= temp:
                break
            self._list[j] = self._list[i]  #子節(jié)點(diǎn)交給父節(jié)點(diǎn)
            j= i    #記錄父節(jié)點(diǎn)應(yīng)該去的索引位置
            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) 
		

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

最新評(píng)論