優(yōu)先隊(duì)列

復(fù)雜度：

• 使用堆時(shí)，優(yōu)先隊(duì)列插入和刪除元素的復(fù)雜度都是O(log2n)
• 另一種描述方法是采用有序線性表,當(dāng)元素按遞增次序排列,使用鏈表時(shí)則按遞減次序排列,這兩種描述方法的刪除時(shí)間均為( 1 ),插入操作所需時(shí)間為(n).

定義

• 普通的隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，元素在隊(duì)列尾追加，而從隊(duì)列頭刪除。在優(yōu)先隊(duì)列中，元素被賦予優(yōu)先級。當(dāng)訪問元素時(shí)，具有最高優(yōu)先級的元素最先刪除。優(yōu)先隊(duì)列具有最高級先出 （first in, largest out）的行為特征。通常采用堆數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。

常見方法

• Create ( ):創(chuàng)建一個(gè)空的優(yōu)先隊(duì)列
• Size ( ):返回隊(duì)列中的元素?cái)?shù)目
• Max ( ):返回具有最大優(yōu)先權(quán)的元素
• Insert (x):將x插入隊(duì)列
• DeleteMax (x):從隊(duì)列中刪除具有最大優(yōu)先權(quán)的元素,并將該元素返回至x

實(shí)現(xiàn)方法

• is_empty：檢查隊(duì)列是否沒有元素。
• insert_with_priority：使用關(guān)聯(lián)的優(yōu)先級向隊(duì)列添加元素。
• pull_highest_priority_element / get_minimum_element（pop_element）：從隊(duì)列中刪除具有最高優(yōu)先級的元素，并將其返回。
• peek（find-max / find-min）返回最高優(yōu)先級元素但不修改隊(duì)列，此操作及其性能對于許多優(yōu)先級隊(duì)列應(yīng)用程序至關(guān)重要。
• 更高級的實(shí)現(xiàn)可能支持更復(fù)雜的操作，例如檢查前幾個(gè)最高或最低優(yōu)先級元素，清除隊(duì)列，清除隊(duì)列子集，執(zhí)行批量插入，將兩個(gè)或多個(gè)隊(duì)列合并為一個(gè)，增加優(yōu)先級任何元素等。

python實(shí)現(xiàn)

#CSDN-bebr實(shí)現(xiàn)
class Heap_Pri_Queue(object):
    def __init__(self, elems=[]):
        self._elems = list(elems)
        if self._elems:
            self.buildheap()

    def is_empty(self):
        return self._elems is []

    def peek(self):   #取出堆頂元素，但不刪除
        if self.is_empty():
            raise HeapPriQueueError("in pop")
        return self._elems[0]

    def enqueue(self, e):   #在末尾增加一個(gè)元素
        self._elems.append(e)  # 此時(shí)，總的元素的長度增加了1位
         self.siftup(e, len(self._elems) - 1)

    def siftup(self, e, last):  # 向上篩選
         elems, i, j = self._elems, last, (last - 1) // 2  # j為last位置的父結(jié)點(diǎn)
         while i > 0 and e < elems[j]:  # 如果需要插入的元素小于當(dāng)前的父結(jié)點(diǎn)的值
             elems[i] = elems[j]  # 則將父結(jié)點(diǎn)的值下放到其子結(jié)點(diǎn)中去
             i, j = j, (j - 1) // 2  # 更新i為當(dāng)前父結(jié)點(diǎn)的位置，j更新為當(dāng)前父結(jié)點(diǎn)的父結(jié)點(diǎn)的位置
         elems[i] = e  # 如果i已經(jīng)更新為0了，直接將e的值賦給位置0.或者需要插入的元素
                         # 大于當(dāng)前父結(jié)點(diǎn)的值，則將其賦給當(dāng)前父結(jié)點(diǎn)的子結(jié)點(diǎn)

     def dequeue(self):
        if self.is_empty():
            raise HeapPriQueueError("in pop")
        elems = self._elems
        e0 = elems[0]  # 根結(jié)點(diǎn)元素
         e = elems.pop()  # 將最后一個(gè)元素彈出，作為一個(gè)新的元素經(jīng)過比較后找到插入的位置，以維持棧序
         if len(elems) > 0:
            self.siftdown(e, 0, len(elems))
        return e0

     def siftdown(self, e, begin, end):  # 向下篩選
         elems, i, j = self._elems, begin, begin * 2 + 1  # j為i的左子結(jié)點(diǎn)
         while j < end:
            if j + 1 < end and elems[j] > elems[j + 1]:  # 如果左子結(jié)點(diǎn)大于右子結(jié)點(diǎn)
                j += 1  # 則將j指向右子結(jié)點(diǎn)，將j指向較小元素的位置
             if e < elems[j]:  # j已經(jīng)指向兩個(gè)子結(jié)點(diǎn)中較小的位置，
                break  # 如果插入元素e小于j位置的值，則為3者中最小的
             elems[i] = elems[j]  # 能執(zhí)行到這一步的話，說明j位置元素是三者中最小的，則將其上移到父結(jié)點(diǎn)位置
             i, j = j, j * 2 + 1  # 更新i為被上移為父結(jié)點(diǎn)的原來的j的位置，更新j為更新后i位置的左子結(jié)點(diǎn)
         elems[i] = e  # 如果e已經(jīng)是某個(gè)子樹3者中最小的元素，則將其賦給這個(gè)子樹的父結(jié)點(diǎn)
                        # 或者位置i已經(jīng)更新到葉結(jié)點(diǎn)位置，則將e賦給這個(gè)葉結(jié)點(diǎn)。

      def buildheap(self):
        end = len(self._elems)
        for i in range(end // 2 - 1, -1, -1):  # 初始位置設(shè)置為end//2 - 1。 如果end=len(elems)-1,則初始位置為(end+1)//2-1.
            #            print(self._elems[i])
            self.siftdown(self._elems[i], i, end)

if __name__ == "__main__":
    temp = Heap_Pri_Queue([5, 6, 8, 1, 2, 4, 9])
    print(temp._elems)
    temp.dequeue()
    print(temp._elems)
    temp.enqueue(0)
    print(temp._elems)
    print(temp.peek())

python headq實(shí)現(xiàn)簡單優(yōu)先隊(duì)列

#CSDN-bebr實(shí)現(xiàn)
from heapq import *
class Heap_Pri_Queue(object):
    def __init__(self, heap=[]):
        self.heap = heap
        heapify(self.heap)

    def enqueue(self, val):
        heappush(self.heap, val)

    def dequeue(self):
        return heappop(self.heap)

if __name__ == "__main__":
    lst = [5, 6, 8, 1]
    heap = Heap_Pri_Queue(lst)
    print(heap.dequeue()) #1
    heap.enqueue(3)
    print(heap.heap)  #[3, 5, 8, 6]