优先队列

复杂度：

• 使用堆时，优先队列插入和删除元素的复杂度都是O(log2n)
• 另一种描述方法是采用有序线性表,当元素按递增次序排列,使用链表时则按递减次序排列,这两种描述方法的删除时间均为( 1 ),插入操作所需时间为(n).

定义

• 普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现。

常见方法

• Create ( ):创建一个空的优先队列
• Size ( ):返回队列中的元素数目
• Max ( ):返回具有最大优先权的元素
• Insert (x):将x插入队列
• DeleteMax (x):从队列中删除具有最大优先权的元素,并将该元素返回至x

实现方法

• is_empty：检查队列是否没有元素。
• insert_with_priority：使用关联的优先级向队列添加元素。
• pull_highest_priority_element / get_minimum_element（pop_element）：从队列中删除具有最高优先级的元素，并将其返回。
• peek（find-max / find-min）返回最高优先级元素但不修改队列，此操作及其性能对于许多优先级队列应用程序至关重要。
• 更高级的实现可能支持更复杂的操作，例如检查前几个最高或最低优先级元素，清除队列，清除队列子集，执行批量插入，将两个或多个队列合并为一个，增加优先级任何元素等。

python实现

#CSDN-bebr实现
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):   #在末尾增加一个元素
        self._elems.append(e)  # 此时，总的元素的长度增加了1位
         self.siftup(e, len(self._elems) - 1)

    def siftup(self, e, last):  # 向上筛选
         elems, i, j = self._elems, last, (last - 1) // 2  # j为last位置的父结点
         while i > 0 and e < elems[j]:  # 如果需要插入的元素小于当前的父结点的值
             elems[i] = elems[j]  # 则将父结点的值下放到其子结点中去
             i, j = j, (j - 1) // 2  # 更新i为当前父结点的位置，j更新为当前父结点的父结点的位置
         elems[i] = e  # 如果i已经更新为0了，直接将e的值赋给位置0.或者需要插入的元素
                         # 大于当前父结点的值，则将其赋给当前父结点的子结点

     def dequeue(self):
        if self.is_empty():
            raise HeapPriQueueError("in pop")
        elems = self._elems
        e0 = elems[0]  # 根结点元素
         e = elems.pop()  # 将最后一个元素弹出，作为一个新的元素经过比较后找到插入的位置，以维持栈序
         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的左子结点
         while j < end:
            if j + 1 < end and elems[j] > elems[j + 1]:  # 如果左子结点大于右子结点
                j += 1  # 则将j指向右子结点，将j指向较小元素的位置
             if e < elems[j]:  # j已经指向两个子结点中较小的位置，
                break  # 如果插入元素e小于j位置的值，则为3者中最小的
             elems[i] = elems[j]  # 能执行到这一步的话，说明j位置元素是三者中最小的，则将其上移到父结点位置
             i, j = j, j * 2 + 1  # 更新i为被上移为父结点的原来的j的位置，更新j为更新后i位置的左子结点
         elems[i] = e  # 如果e已经是某个子树3者中最小的元素，则将其赋给这个子树的父结点
                        # 或者位置i已经更新到叶结点位置，则将e赋给这个叶结点。

      def buildheap(self):
        end = len(self._elems)
        for i in range(end // 2 - 1, -1, -1):  # 初始位置设置为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实现简单优先队列

#CSDN-bebr实现
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]