线性代数(Gelbert)的复习已经写到复习三了，不过依然不保证进度。写这篇一则是好久没更新了；二是表示一下，虽然开了新的数学坑，但是说过的复习部分我还是没有放弃的。

    最近为了能对大数据平台的运行情况做一些细致的监控，写了不少抓取运行情况日志的脚本。之前都是我自己看，就一直乱着来的。现在要展现了，不能靠人眼排序了。于是今天下午写了个简单的优先级队列(注意：实现十分粗糙，虽然能满足我的需求，但是没有处理并发等等各种情况，也没优化过。如果有人想用，最好自己调整一下)。用二叉堆实现的，关于它的原理，可以参考我为了讲课整理的一些记录(其中的优先级队列部分)：

https://github.com/saaavsaaa/saaavsaaa.github.io/blob/master/aaa/Structure_Abstract2.md

    直接看代码了。用了个全局的列表，其他就主要是插入和删除节点两个方法：

class PriorityQueue:    heap_list = []
        def insert(self, e):        self.heap_list.append(e) # 只是为了增加一个位置，可以append任何值        self.percolateUp(len(self.heap_list) - 1, e)
    def pop(self):        top = self.heap_list[0]        self.heap_list[0] = self.heap_list[-1]  # 用倒数第一个替代        self.heap_list.pop() # heap_list = heap_list[0:-1]        if (len(self.heap_list) > 0):            self.percolateDown()        return top

    很明显其中起主要作用的就是 percolateUp 和 percolateDown 方法，看代码注释吧。其中的各种pass不要在意，主要是懒得删空格。

    def percolateUp(self, index, value):        j = 0        while(index > 0):            j = int((index - 1)/2)   # index对应节点的直接前驱的秩            if (value > self.heap_list[j]):                self.heap_list[index] = self.heap_list[j] # 依次下移                index = j                pass            else:                break        self.heap_list[index] = value # 没有依次更新，省几次交换        pass
    def percolateDown(self):        index = 0        last = self.heap_list[0] # 原末节点        while index < len(self.heap_list):            l_child = 2 * index + 1 # 左后继的秩            r_child = 2 * (index + 1) # 右后继的秩            sort_list = [(index, last)] # 这是为了找到当前节点和左右子节点中大的那个            if l_child > len(self.heap_list) - 1:                break            else:                sort_list.append((l_child, self.heap_list[l_child]))                        if r_child < len(self.heap_list):                sort_list.append((r_child, self.heap_list[r_child]))                pass                        sort_list.sort(key=self.takeSecond, reverse=True) # 排序找出其中值比较大的            largest_index = sort_list[0][0]            if largest_index == index:                break # 如果最大的就是当前节点，那么堆序性就满足了            else:                self.heap_list[index] = self.heap_list[largest_index]                index = largest_index # 与左右子节点中大的那个交换                pass            pass        self.heap_list[index] = last # 同为了少几次交换        return index

    测试插入：

from priority_queue import PriorityQueue
pq = PriorityQueue()pq.insert(2)print(pq.display())pq.insert(5)print(pq.display())pq.insert(3)print(pq.display())pq.insert(4)print(pq.display())pq.insert(1)print(pq.display())pq.insert(6)print(pq.display())pq.insert(5)print(pq.display())pq.insert(6)print(pq.display())

    输出：

[2][5, 2][5, 2, 3][5, 4, 3, 2][5, 4, 3, 2, 1][6, 4, 5, 2, 1, 3][6, 4, 5, 2, 1, 3, 5][6, 6, 5, 4, 1, 3, 5, 2]

    测试出队：

while len(pq.display()) > 0:    print(pq.pop())    print(pq.display())

    输出：

6[6, 4, 5, 2, 1, 3, 5]6[5, 4, 5, 2, 1, 3]5[5, 4, 3, 2, 1]5[4, 2, 3, 1]4[3, 2, 1]3[2, 1]2[1]1[]

公众号：