#-*- coding:utf-8 -*-
classArray(object):def __init__(self, size=32):
self._size=size
self._items= [None] *sizedef __getitem__(self, index):returnself._items[index]def __setitem__(self, index, value):
self._items[index]=valuedef __len__(self):returnself._sizedef clear(self, value=None):for i inrange(len(self._items)):
self._items[i]=valuedef __iter__(self):for item inself._items:yielditemclassMaxHeap(object):def __init__(self, maxsize=None):
self.maxsize=maxsize
self._elements=Array(maxsize)
self._count=0def __len__(self):returnself._countdefadd(self, value):if self._count >=self.maxsize:raise Exception(‘full‘)
self._elements[self._count]=value
self._count+= 1self._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)defextract(self):if self._count <=0:raise Exception(‘empty‘)
value=self._elements[0]
self._count-= 1self._elements[0]=self._elements[self._count]
self._siftdown(0)returnvaluedef_siftdown(self, ndx):
left= 2 * ndx + 1right= 2 * ndx + 2
#determine which node contains the larger value
largest =ndxif (left < self._count and #有左孩子
self._elements[left] >= self._elements[largest] andself._elements[left]>= self._elements[right]): #原书这个地方没写实际上找的未必是largest
largest =leftelif right < self._count and self._elements[right] >=self._elements[largest]:
largest=rightif largest !=ndx:
self._elements[ndx], self._elements[largest]=self._elements[largest], self._elements[ndx]
self._siftdown(largest)classPriorityQueue(object):def __init__(self, maxsize):
self.maxsize=maxsize
self._maxheap=MaxHeap(maxsize)defpush(self, priority, value):
entry=(priority, value)
self._maxheap.add(entry)def pop(self, with_priority=False):
entry=self._maxheap.extract()ifwith_priority:returnentryelse:return entry[1]defis_empty(self):return len(self._maxheap) ==0deftest_priority_queue():
size= 5pq=PriorityQueue(size)
pq.push(5, ‘purple‘)
pq.push(0,‘white‘)
pq.push(3, ‘orange‘)
pq.push(1, ‘black‘)
res=[]while notpq.is_empty():
res.append(pq.pop())assert res == [‘purple‘, ‘orange‘, ‘black‘, ‘white‘]