1 class PriorQueque: 2 def __init__(self, list1=[]): 3 self.__list = [] 4 self.__MakeMaxHeap(list1) 5 6 def __HeapUp(self): 7 curIndex = len(self.__list) - 1 #tail element 8 parentIndex = (curIndex-1)//2 9 while(parentIndex >= 0 and self.__list[curIndex] > self.__list[parentIndex]): 10 self.__list[curIndex], self.__list[parentIndex] = 11 self.__list[parentIndex], self.__list[curIndex] 12 curIndex = parentIndex 13 parentIndex = (curIndex-1)//2 14 15 def __HeapDown(self): 16 retValue = self.__list[0] 17 self.__list[0] = self.__list.pop() 18 disorderValue = self.__list[0] 19 lastIndex = len(self.__list) - 1 20 bigIndex = 0 21 curIndex = 0 22 leftIndex = 2 * curIndex + 1 23 while(leftIndex <= lastIndex): 24 bigIndex = leftIndex 25 if(leftIndex < lastIndex and self.__list[leftIndex] < self.__list[leftIndex + 1]): 26 bigIndex = leftIndex + 1 27 if(disorderValue >= self.__list[bigIndex]): 28 break 29 self.__list[curIndex] = self.__list[bigIndex] 30 curIndex = bigIndex 31 leftIndex = 2 * curIndex + 1 32 self.__list[curIndex] = disorderValue 33 return retValue 34 35 def Pop(self): 36 if(len(self.__list) <= 2): 37 return self.__list.pop() 38 else: 39 return self.__HeapDown() 40 41 def Push(self, value): 42 self.__list.append(value) 43 self.__HeapUp() 44 45 def Top(self): 46 return self.__list[0] 47 48 def __MakeMaxHeap(self, list1): 49 for i in list1: 50 self.Push(i) 51 52 def __repr__(self): 53 return self.__list.__repr__() 54 55 56 57