浼樺厛绾ч槦鍒?python)，,鏍囩锛?a hre

浼樺厛绾ч槦鍒?python)，,鏍囩锛?a hre

鏍囩锛?a href='http://www.byrx.net/so/1/ems' title='ems'>ems

# -*- coding:utf-8 -*-class Array(object):    def __init__(self, size=32):        self._size = size        self._items = [None] * size    def __getitem__(self, index):        return self._items[index]    def __setitem__(self, index, value):        self._items[index] = value    def __len__(self):        return self._size    def clear(self, value=None):        for i in range(len(self._items)):            self._items[i] = value    def __iter__(self):        for item in self._items:            yield itemclass MaxHeap(object):       def __init__(self, maxsize=None):        self.maxsize = maxsize        self._elements = Array(maxsize)        self._count = 0    def __len__(self):        return self._count    def add(self, value):        if self._count >= self.maxsize:            raise Exception(鈥?/span>full鈥?/span>)        self._elements[self._count] = value        self._count += 1        self._siftup(self._count-1)      def _siftup(self, ndx):        if ndx > 0:            parent = int((ndx-1)/2)            if self._elements[ndx] > self._elements[parent]:                    self._elements[ndx], self._elements[parent] = self._elements[parent], self._elements[ndx]                self._siftup(parent)       def extract(self):        if self._count <= 0:            raise Exception(鈥?/span>empty鈥?/span>)        value = self._elements[0]            self._count -= 1        self._elements[0] = self._elements[self._count]            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 (left < self._count and     # 鏈夊乏瀛╁瓙                self._elements[left] >= self._elements[largest] and                self._elements[left] >= self._elements[right]):  # 鍘熶功杩欎釜鍦版柟娌″啓瀹為檯涓婃壘鐨勬湭蹇呮槸largest            largest = left        elif right < self._count and self._elements[right] >= self._elements[largest]:            largest = right        if largest != ndx:            self._elements[ndx], self._elements[largest] = self._elements[largest], self._elements[ndx]            self._siftdown(largest)class PriorityQueue(object):    def __init__(self, maxsize):        self.maxsize = maxsize        self._maxheap = MaxHeap(maxsize)    def push(self, priority, value):        entry = (priority, value)            self._maxheap.add(entry)    def pop(self, with_priority=False):        entry = self._maxheap.extract()        if with_priority:            return entry        else:            return entry[1]    def is_empty(self):        return len(self._maxheap) == 0def test_priority_queue():    size = 5    pq = PriorityQueue(size)    pq.push(5, 鈥?/span>purple鈥?/span>)    pq.push(0, 鈥?/span>white鈥?/span>)    pq.push(3, 鈥?/span>orange鈥?/span>)    pq.push(1, 鈥?/span>black鈥?/span>)    res = []    while not pq.is_empty():        res.append(pq.pop())    assert res == [鈥?/span>purple鈥?/span>, 鈥?/span>orange鈥?/span>, 鈥?/span>black鈥?/span>, 鈥?/span>white鈥?/span>]

浼樺厛绾ч槦鍒?python)

鏍囩锛?a href='http://www.byrx.net/so/1/ems' title='ems'>ems

鍘熸枃鍦板潃锛歨ttps://www.cnblogs.com/muzinan110/p/11167091.html