算法基础 5 - 优先队列与二叉堆 Binary Heap

优先队列（Priority Queue）

特性：用于维护一组元素构成的集合，key=priority，能够快速/移除获取最重要的元素

• 计算机操作系统的作业调度，在任务队列中选择最高优先级的任务执行
• 离散事件的时间系统模拟，事件必须按照时间发生的顺序进行模拟

接口：

优先队列排序：

• 任意的优先队列数据结构都可以转化为一种排序算法：
  • build(A)，按照输入顺序构建数据结构
  • 重复执行delete_min()/delete_max()以确定排序顺序
• 许多排序算法可以被看做一种优先队列

class PriorityQueue:
    def __init__(self):
        self.A = []

    def insert(self, x):
        self.A.append(x)

    def delete_max(self):
        if len(self.A) < 1:
            return False
        return self.A.pop()

    @classmethod
    def sort(Queue, A):
        pq = Queue()
        for x in A:
            pq.insert(x)
        out = [pq.delete_max() for _ in A]
        out.reverse()
        return out

class PQ_Array(PriorityQueue):
    def delete_max(self):
        n, A, m = len(self.A), self.A, 0
        for i in range(1, n):
            if A[m].key < A[i].key:
                m = i
        A[m], A[n] = A[n], A[m]
        return super().delete_max()

class PQ_SortedArray(PriorityQueue):
    def insert(self, *args):
        super().insert(*args)
        i, A = len(self.A)-1, self.A
        while 0 < i and A[i+1].key < A[i].key:
            A[i+1], A[i] = A[i], A[i+1]
            i -= 1

---

二叉堆

• 结合AVL树和动态数组的数据结构，既有AVL的快速排序，有动态数组的直接存取
• 在AVL树的基础上，所有节点为左对齐的，因此可以使用数组表示一个树的数据结构

二叉堆的特性

• 直接索引：每个节点的父节点，和左右子节点，都可以由计算的序号通过数组索引

$$\operatorname{left}(i)=2 i+1, \ \operatorname{right}(i) =2 i+2, \ \operatorname{parent}(i) =\left\lfloor\frac{i-1}{2}\right\rfloor$$

• 最大堆特性：每个节点的优先级都高于其子节点，进一步高于其子树的所有节点

$$Q[i] \geq Q[j],\quad \text { for } j \in\{\operatorname{left}(i), \operatorname{right}(i)\}$$

• 堆的插入（上浮）：
  • 将新元素插入到数组末尾(最右叶节点)
  • 从该节点开始，若子节点优先级高于父节点，则交换数组中两个元素位置，并递归
• 堆的删除（下沉）：
  • 将根节点和最右子节点交换(数组首尾元素交换)，并删除数组末尾元素
  • 从根节点开始，若父节点优先级小于子节点，则交换父节点与优先级最高的子节点，并递归

class PriorityQueue:
    def __init__(self, A):
        self.A = []
        self.n = 0

    def insert(self, x):
        self.A.append(x)
        self.n += 1

    def delete_max(self):
        if len(self.A) < 1:
            return False
        self.n -= 1
        return self.A.pop()

    @classmethod
    def sort(Queue, A):
        pq = Queue(A)
        for x in A:
            pq.insert(x)
        out = [pq.delete_max() for _ in A]
        out.reverse()
        return out

class PQ_Heap(PriorityQueue):
    def insert(self, *args):
        super().insert(*args)
        n, A = self.n, self.A
        self.max_heapify_up(A, n, n-1)

    def delete_max(self):
        n, A = self.n, self.A
        A[0], A[n-1] = A[n-1], A[0]
        self.max_heapify_down(A, n-1, 0)
        return super().delete_max()

    def parent(self, i):
        p = (i - 1) // 2
        return p if 0 < i else i

    def left(self, i, n):
        l = 2 * i + 1
        return l if l < n else i

    def right(self, i, n):
        r = 2 * i + 2
        return r if r < n else i

    def max_heapify_up(self, A, n, c):
        p = self.parent(c)
        if A[p].key < A[c].key:
            A[c], A[p] = A[p], A[c]
            self.max_heapify_up(A, n, p)

    def max_heapify_down(self, A, n, p):
        l, r = self.left(p, n), self.right(p, n)
        if A[r].key < A[l].key:
            c = l
        else:
            c = r
        if A[p].key < A[c].key:
            A[c], A[p] = A[p], A[c]
            self.max_heapify_down(A, n, c)