堆结构的应用

1.随时找到数据流的中位数

【题目】有一个源源不断地吐出整数的数据流，假设你有足够的空间来保存吐出的数。请设计一个名叫MedianHolder的结构，
MedianHolder可以随时取得之前吐出所有数的中位数。
【要求】

• 如果MedianHolder已经保存了吐出的N个数，那么任意时刻
  将一个新数加入到MedianHolder的过程，其时间复杂度是
  O(logN)。
• 取得已经吐出的N个数整体的中位数的过程，时间复杂度为
  O(1)。

【一些概念】
中位数：对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。
ArrayList：底层是数组结构，getIndex很快，但是remove很慢。
LinkedList：底层是双向链表结构，getIndex很慢，但是remove很快。

【解题思路】借用两个堆，一个为大根堆，一个为小根堆。希望数据排序后，前N/2的数据放入大根堆，后N/2的数据放入小根堆，那么大根堆的堆顶和小根堆的堆顶就为中位数。

【代码思路】

• 第一个数放入大根堆；
• 如果接下来的一个数比大根堆的堆顶小，就放入大根堆，反之放入小根堆，插入的过程就是heapInsert的过程；（实际上以什么策略进堆不重要，反正之后都要进行堆调整，用到了Java的PriorityQueue，优先级队列的底层就是堆）
• 如果大根堆的size和小根堆的size的差值大于1，就将size大的堆顶弹出放入另一个堆中；弹出堆顶的堆的调整过程就是将size--，最后一个元素放到堆顶，然后将堆顶进行heapify过程。

【时间复杂度】heapInsert为O(logN)，poll为O(logN)，得到中位数为O(1)。过程中无需进行排序操作。
【堆的应用】当你需要一群数中的最大/最小值，并且最大/最小值弹出后，可以获取剩余的最大最小值，就用堆结构。

2.如何切金条最省铜板

【题目】一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半，都要花费20个铜板。一群人想整分整块金条，怎么分最省铜板？

• 例如，给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60。金条要分成10,20,30三个部分。
• 如果，先把长度60的金条分成10和50，花费60；再把长度50的金条分成20和30，花费50；一共花费110铜板。
• 但是如果，先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20，花费30；一共花费90铜板。
• 输入一个数组，返回分割的最小代价。

【一些概念】
贪心策略（往往只在笔试中出现）：是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在【旅行推销员问题】中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

【思路】（哈夫曼编码的应用）。将所有数加入到小根堆中，每次弹出两个栈顶，即最小的两个数，然后将两个数的和cur重新加入到小根堆中，同时sum+=cur，最后返回sum。

3.如何做项目能获取最大钱数

【题目】
输入：
参数1，正数数组costs
参数2，正数数组profits
参数3，正数k
参数4，正数m

costs[i]表示i号项目的花费
profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
k表示你不能并行、只能串行的最多做k个项目
m表示你初始的资金

说明：你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。

输出：你最后获得的最大钱数。

【解题思路】总钱数解锁你可以做的项目，然后在所有可以做的项目池中选择可以获取最大利润的项目，以此往复。
【代码思路】

• 将所有项目节点加入cost的小根堆
• 依次弹出小根堆堆顶，如果小于总钱数，就解锁该项目，加入到profit的大根堆
• 然后弹出大根堆的堆顶
• 直至大根堆为空或者做完k个项目