用堆来实现一个有界优先队列

用堆来实现一个有界有点队列有两个步骤，以大顶堆为例，在加入元素时：

1. 堆不满时（未到达界限），每加入一个元素都需要一次从尾到头的最大堆调整；
2. 堆满时，需要将大顶堆堆顶值置换为队列尾的值，并进行一次从头到尾的最大堆调整，再将新元素加入到队尾，进行一次从尾到头的最大堆调整（步骤1）。

需要注意的是：无论是加入一个新元素或者弹出堆顶，都需要一次调整

实现代码：

class BoundedPriorityQueue:
    """优先对列(max heap)及相关实现函数"""
    def __init__(self, k):
        self.heap=[]
        self.k = k
    
    def items(self):
        return self.heap
    
    def parent(self,index):
        """返回父节点的index"""
        return int(index/2)
    
    def left_child(self, index):
        return 2 * index + 1
    
    def right_child(self, index):
        return 2 *index + 2
    
    def _dist(self, index):
        """返回index对应的值"""
        return self.heap[index]
    
    def max_heapify(self, index):
        """负责维护最大堆，使当前节点的所有子节点均小于该父节点"""
        left_index = self.left_child(index)
        right_index = self.right_child(index)
        
        largest = index
        if left_index < len(self.heap) and self._dist[left_index] > self._dist[index]:
            largest = left_index
        if right_index < len(self.heap) and self._dist[right_index] > self._dist(largest):
            largest = right_index
        if largest != index:
            self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
            self.max_heapify(largest)
            
    def propagate_up(self, index):
        """在index位置添加新元素后，通过不断和父节点比较并交换，维持最大堆的特性，
        保持堆中父节点的值永远大于子节点"""
        while index != 0 and self._dist(self.parent(index)) < self._dist(index):
            self.heap[index], self.heap[self.parent(index)] = self.heap[self.parent(index)], self.heap[index]
            index = self.parent(index)
    
    def add(self, obj):
        """如果当前值小于优先队列中的最大值，则将obj添加入队列，
        如果队列已满，则移除最大值再添加，这时原队列中的最大值将被obj取代"""
        size = self.size()
        if size == self.k:
            max_elem = self.max()
            if obj[1] < max_elem:
                self.extract_max()
                self.heap_append(obj)
        else:
            self.heap_append(obj)
            
    def heap_append(self, obj):
        """向队列中添加一个obj"""
        self.heap.append(obj)
        self.propagate_up(self.size() - 1) 
    
    def size(self):
        return len(self.heap)

    def max(self):
        return self.heap[0][4]
    
    def extract_max(self):
        """将最大值从队列中移除，同时对新队列排序"""
        max = self.heap[0]
        data = self.heap.pop()
        if len(self.heap) > 0:
            self.heap[0] = data
            sele.max_heapify(0)
        return max