练习内容：
1.创建一个类，实现优先级队列功能。
2.使用优先级队列求解IPO问题。
IPO问题：
输入：参数1：正数数组costs；参数2：正数数组profits；参数3：正数k；参数4，正数m
costs[i]表示i号项目的花费;
profits[i]表示i号项目在扣除花费之后还能挣到的钱;
k表示你不能并行，只能串行的最多做k个项目;
m表示你最初的资金;
说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
输出：你最后获得的最大钱数。
1.实现优先级队列
1 1 __author__ = 'Orcsir' 2 2 3 3 4 4 class PriorityQueue: 5 5 def __init__(self, comparator=lambda x, y: x > y): 6 6 self._lst = [] 7 7 self.comparator = comparator 8 8 9 9 def __heap_insert(self, index): 1010 array = self._lst 1111 while index != 0 and self.comparator(array[index], array[(index - 1) >> 1]): 1212 array[index], array[(index - 1) >> 1] = array[(index - 1) >> 1], array[index] 1313 index = (index - 1) >> 1 1414 1515 def __heap_ify(self, index, size): 1616 array = self._lst 1717 left = 2 * index + 1 1818 while left < size: 1919 # 选出左右孩子中的最值 2020 largest = left 2121 right = left + 1 2222 if right < size: 2323 largest = left if self.comparator(array[left], array[right]) else right 2424 2525 if self.comparator(array[index], array[largest]): 2626 break 2727 2828 array[index], array[largest] = array[largest], array[index] 2929 index = largest 3030 left = 2 * index + 1 3131 3232 def is_empty(self): 3333 return True if len(self._lst) == 0 else False 3434 3535 def add(self, obj): 3636 self._lst.append(obj) 3737 self.__heap_insert(len(self._lst) - 1) 3838 3939 def pop(self): 4040 self._lst[0], self._lst[-1] = self._lst[-1], self._lst[0] 4141 obj = self._lst.pop() 4242 self.__heap_ify(0, len(self._lst)) 4343 return obj 4444 4545 def peek(self): 4646 return self._lst[0] 4747 4848 poll = pop
2.创建数据类，用于描述每一个项目
11 class Project: 22 __slots__ = ("cost", "profit") 33 44 def __init__(self, cost, profit): 55 self.cost = cost 66 self.profit = profit
3.求解IPO问题。策略：建立两个优先级队列：最小花费堆，最大收益堆。根据资金持续解锁花费堆，并向收益堆中发货
1 1 def max_heap_comparator(obj1, obj2): 2 2 return obj1.profit > obj2.profit # 大根堆 3 3 4 4 5 5 def min_heap_comparator(obj1, obj2): 6 6 return obj1.cost < obj2.cost # 小根堆 7 7 8 8 9 9 def findMaximizedCapital(costs: list, profits: list, k: int, m: int) -> int: 1010 min_cost_heap = PriorityQueue(min_heap_comparator) 1111 max_profit_heap = PriorityQueue(max_heap_comparator) 1212 1313 for cost, profit in zip(costs, profits): 1414 min_cost_heap.add(Project(cost, profit)) 1515 1616 for i in range(0, k): 1717 while not min_cost_heap.is_empty() and min_cost_heap.peek().cost <= m: 1818 obj = min_cost_heap.pop() 1919 max_profit_heap.add(obj) 2020 2121 if max_profit_heap.is_empty(): 2222 break 2323 m += max_profit_heap.poll().profit 2424 return m
4. 简单测试代码
11 if __name__ == '__main__': 22 costs = [2, 10, 14, 1] 33 profits = [5, 20, 8, 10] 44 k = 4 55 m = 15 66 ret = 0 77 ret = findMaximizedCapital(costs, profits, k, m) 88 print(ret)