priority queue优先级相同的元素

[fantasycz]

在priority queue里，如果只是比较tuple。在存在优先级相同的元素的时候，可能会出现问题。因为如果优先级相同，就会比较后面的value，这就不能保证FIFO。

[lihujun101]

上面的优先级队列不完善，如果同优先级的，则应该保持先进先出。需改进 改进思路：

1. 堆中的元素和队列有个关系，如k_v={5:queue5,4:queue4}
2. 堆每次抛出一个最大值的时候，k_v[5].pop()
3. 堆每次添加的时候，kv[5].push("张三")

# -*- coding:utf-8 -*-
​
#####################################################
# heap 实现
#####################################################
​
​
class MaxHeap:
    """
    Heaps:
    完全二叉树，最大堆的非叶子节点的值都比孩子大，最小堆的非叶子结点的值都比孩子小
    Heap包含两个属性，order property 和 shape property(a complete binary tree)，在插入
    一个新节点的时候，始终要保持这两个属性
    插入操作：保持堆属性和完全二叉树属性, sift-up 操作维持堆属性
    extract操作：只获取根节点数据，并把树最底层最右节点copy到根节点后，sift-down操作维持堆属性
    用数组实现heap，从根节点开始，从上往下从左到右给每个节点编号，则根据完全二叉树的
    性质，给定一个节点i， 其父亲和孩子节点的编号分别是:
        parent = (i-1) // 2
        left = 2 * parent + 1
        rgiht = 2 * parent + 2
    使用数组实现堆一方面效率更高，节省树节点的内存占用，一方面还可以避免复杂的指针操作，减少
    调试难度。
​
    放弃指针操作吧，头晕呜呜呜呜呜呜呜，哭 /-\
    """
​
    def __init__(self, maxsize=32):
        self.maxsize = maxsize
        self._elements = [None] * self.maxsize
        self._count = 0
​
    def __len__(self):
        return self._count
​
    def add(self, value):
        if self._count >= self.maxsize:  # 正常情况下self._count最大下标只有31
            raise Exception("full")
        self._elements[self._count] = value
        self._siftup(self._count)
        self._count += 1
​
    def _siftup(self, idx):
        if idx > 0:
            parent_idx = (idx - 1) // 2
            if self._elements[parent_idx] < self._elements[idx]:
                self._elements[parent_idx], self._elements[idx] = self._elements[idx], self._elements[parent_idx]
                self._siftup(parent_idx)
​
    def extract(self):
        value = self._elements[0]
        if self._count >= 1:
            self._elements[0] = self._elements[self._count - 1]
            self._elements[self._count - 1] = None
        self._count -= 1
        self._siftdown(0)
        return value
​
    def _siftdown(self, ndx):
        left = 2 * ndx + 1
        right = 2 * ndx + 2
        # determine which node contains the larger value
        largest = ndx
        if (right < self._count and  # 有右孩子
                self._elements[right] >= self._elements[largest] and
                self._elements[left] <= self._elements[right]):  # 原书这个地方没写实际上找的未必是largest
            largest = right
        elif left < self._count and self._elements[left] >= self._elements[largest]:
            largest = left
        if largest != ndx:
            self._elements[ndx], self._elements[largest] = self._elements[largest], self._elements[ndx]
            self._siftdown(largest)
​
​
class PriorityQueue:
    def __init__(self):
        self._maxheap = MaxHeap()
        self.kv = {}
​
    def push(self, key, value):
        from collections import deque
        # 注意这里把这个 tuple push 进去，python 比较 tuple 从第一个开始比较
        # 这样就很巧妙地实现了按照优先级排序
        self._maxheap.add(key)
        if self.kv.get(key) is None:
            deque = deque()
            self.kv[key] = deque
        self.kv[key].append(value)
​
    def pop(self):
        key = self._maxheap.extract()
        m = self.kv[key].popleft()
        if len(self.kv[key]) == 0:
            del self.kv[key]
        return m
​
    def is_empty(self):
        return len(self._maxheap) == 0
​
​
def test_priority_queue():
    pq = PriorityQueue()
    pq.push(5, 'purple')  # key, value
    pq.push(0, 'white')
    pq.push(3, 'orange')
    pq.push(1, 'black')
    pq.push(1, 'black1')
​
    res = []
    while not pq.is_empty():
        res.append(pq.pop())
    assert res == ['purple', 'orange', 'black', 'black1', 'white']
​
​
if __name__ == '__main__':
    test_priority_queue()
​```

[PegasusWang]

建议提一个 mr，使用一个新的类吧，叫做 PrirotyQueueStrict ? 感觉如何呢？保留两个类