练习内容：
1.创建一个类，实现优先级队列功能。
2.使用优先级队列求解IPO问题。IPO问题：
输入：参数1：正数数组costs；参数2：正数数组profits；参数3：正数k；参数4，正数mcosts[i]表示i号项目的花费;
profits[i]表示i号项目在扣除花费之后还能挣到的钱; k表示你不能并行，只能串行的最多做k个项目; m表示你最初的资金;说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
输出：你最后获得的最大钱数。1.实现优先级队列
1 __author__ = 'Orcsir' 2 3 4 class PriorityQueue: 5 def __init__(self, comparator=lambda x, y: x > y): 6 self._lst = [] 7 self.comparator = comparator 8 9 def __heap_insert(self, index):10 array = self._lst11 while index != 0 and self.comparator(array[index], array[(index - 1) >> 1]):12 array[index], array[(index - 1) >> 1] = array[(index - 1) >> 1], array[index]13 index = (index - 1) >> 114 15 def __heap_ify(self, index, size):16 array = self._lst17 left = 2 * index + 118 while left < size:19 # 选出左右孩子中的最值20 largest = left21 right = left + 122 if right < size:23 largest = left if self.comparator(array[left], array[right]) else right24 25 if self.comparator(array[index], array[largest]):26 break27 28 array[index], array[largest] = array[largest], array[index]29 index = largest30 left = 2 * index + 131 32 def is_empty(self):33 return True if len(self._lst) == 0 else False34 35 def add(self, obj):36 self._lst.append(obj)37 self.__heap_insert(len(self._lst) - 1)38 39 def pop(self):40 self._lst[0], self._lst[-1] = self._lst[-1], self._lst[0]41 obj = self._lst.pop()42 self.__heap_ify(0, len(self._lst))43 return obj44 45 def peek(self):46 return self._lst[0]47 48 poll = pop
2.创建数据类，用于描述每一个项目
1 class Project:2 __slots__ = ("cost", "profit")3 4 def __init__(self, cost, profit):5 self.cost = cost6 self.profit = profit 3.求解IPO问题。策略：建立两个优先级队列：最小花费堆，最大收益堆。根据资金持续解锁花费堆，并向收益堆中发货
1 def max_heap_comparator(obj1, obj2): 2 return obj1.profit > obj2.profit # 大根堆 3 4 5 def min_heap_comparator(obj1, obj2): 6 return obj1.cost < obj2.cost # 小根堆 7 8 9 def findMaximizedCapital(costs: list, profits: list, k: int, m: int) -> int:10 min_cost_heap = PriorityQueue(min_heap_comparator)11 max_profit_heap = PriorityQueue(max_heap_comparator)12 13 for cost, profit in zip(costs, profits):14 min_cost_heap.add(Project(cost, profit))15 16 for i in range(0, k):17 while not min_cost_heap.is_empty() and min_cost_heap.peek().cost <= m:18 obj = min_cost_heap.pop()19 max_profit_heap.add(obj)20 21 if max_profit_heap.is_empty():22 break23 m += max_profit_heap.poll().profit24 return m
4. 简单测试代码
1 if __name__ == '__main__': 2 costs = [2, 10, 14, 1]3 profits = [5, 20, 8, 10]4 k = 45 m = 156 ret = 07 ret = findMaximizedCapital(costs, profits, k, m)8 print(ret)