# Priority Queue Interface & Implementation

## Priority Queue Interface

Priority Queue 在 Queue 的基础上，为 Queue 中的每个元素设置优先级，从而影响 dequeue 的顺序。我们知道 Queue 的 dequeue 是遵循 FIFO 策略，但现实中有很多场景的 dequeue 需要按照一定的优先级实施调度策略：

* 飞机头等舱与经济舱的登机顺序
* 操作系统的进程调度管理
* ...

将这些场景抽象起来，就得到了 Priority Queue Interface:

| 方法                       | 功能                                |
| ------------------------ | --------------------------------- |
| $$insert(Q, x)$$         | 将元素 x 插入到队列 Q 中                   |
| $$max(Q)$$               | 返回队列 Q 中优先级最高的元素                  |
| $$extractMax(Q)$$        | 将队列 Q 中优先级最高的元素出列，并返回             |
| $$increaseKey(Q, x, k)$$ | 将队列 Q 中的元素 x 的优先级变成 k （k 大于当前优先级） |

## Implementation

在 Priority Queue 中，元素处于一种 **“半排序”** 的状态，它需要高效地支持三种操作：

* 定位优先级最高的元素
* 优先级最高的元素出列后，定位下一个优先级最高的元素
* 新的元素入列后处在合理的排序位置

这也是实现好的 Priority Queue 的关键所在。

### Binary Heap （以 Max Heap 为例）

| 方法               | 时间复杂度         | 空间复杂度    |
| ---------------- | ------------- | -------- |
| $$insert(x)$$    | $$O(log(n))$$ | $$O(1)$$ |
| $$max()$$        | $$O(1)$$      | $$O(1)$$ |
| $$extractMax()$$ | $$O(log(n))$$ | $$O(1)$$ |

Binary Heap 有两个不变特性（invariants)：

* Structure Property: 结构上它是一棵二叉完全数（binary complete tree）
* Heap Order Property: 父节点的取值大于它的子节点的取值

实现示例：

{% code title="binary\_heap.py" %}

```python
# 参考
# http://interactivepython.org/courselib/static/pythonds/Trees/BinaryHeapImplementation.html
class MaxHeap:
    def __init__(self):
        # start from index 1, so that for node i
        # parent index: i//2
        # left child index: 2*i
        # right child index: 2*i+1
        self.h = [0]
        self.n = 0

    def insert(self, x):
        # time complexity: O(logn)
        self.h.append(x)
        self.n += 1
        self._bubbleUp(self.n)
    
    def max(self):
        # time complexity: O(1)
        self._ensureNotEmpty()
        return self.h[1]

    def heapify(self, A):
        # time complexity: O(n)
        self.h, self.n = [0] + A, len(A)
        for i in range(self.n//2, 0, -1):
            self._bubbleDown(i)
            
    def extractMax(self):
        # time complexity: O(logn)
        m = self.max()
        if self.n == 1:
            self.h, self.n = [0], 0
        else:
            self.h[1], self.h[self.n] = self.h[self.n], self.h[1]
            del self.h[self.n]
            self.n -= 1
            self._bubbleDown(1)
        return m
    
    def _ensureNotEmpty(self):
        if self.n <= 0:
            raise Exception("empty tree")
        
    def _bubbleUp(self, i):
        while i//2 > 0:
            if self.h[i] > self.h[i//2]:
                self.h[i//2], self.h[i] = self.h[i], self.h[i//2]
            i = i//2
    
    def _bubbleDown(self, i):
        while (i*2) <= self.n:
            mci = self._maxChild(i)
            if self.h[i] < self.h[mci]:
                self.h[i], self.h[mci] = self.h[mci], self.h[i]
            i = mci   
    
    def _maxChild(self, i):
        if i*2 + 1 > self.n:
            return i*2
        else:
            if self.h[i*2] > self.h[i*2+1]:
                return i*2
            else:
                return i*2+1
```

{% endcode %}

### Python heapq

## 参考

* [python heapq source code](https://github.com/python/cpython/blob/master/Lib/heapq.py)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/mit-6.006/priority-queue-interface-and-implementation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.