漫步计算机系统之数据结构与算法（10）堆和队列

　　问题一： 给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
　　代码如下：
　　public ArrayList GetLeastNumbers_Solution(int[] nums, int k) {
　　if (k > nums.length || k <= 0)
　　return new ArrayList<>();
　　PriorityQueue maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
　　for (int num : nums) {
　　maxHeap.add(num);
　　if (maxHeap.size() > k)
　　maxHeap.poll();
　　}
　　return new ArrayList<>(maxHeap);
　　}
　　算法描述： 从头至尾迭代数组； 将数组元素压入最大堆maxHeap； 若压入的数量超出了K，弹出堆的根元素，即队中最大值元素； 迭代结束，堆maxHeap中保存的即为最小的K个元素。
　　问题二： 得到一个数据流中的中位数
　　代码如下：
　　/* 大顶堆，存储左半边元素 */
　　private PriorityQueue left = new PriorityQueue<>((o1, o2) -> o2 - o1);
　　/* 小顶堆，存储右半边元素，并且右半边元素都大于左半边 */
　　private PriorityQueue right = new PriorityQueue<>();
　　/* 当前数据流读入的元素个数 */
　　private int N = 0;
　　public void Insert(Integer val) {
　　/* 插入要保证两个堆存于平衡状态 */
　　if (N % 2 == 0) {
　　/* N 为偶数的情况下插入到右半边。
　　* 因为右半边元素都要大于左半边，但是新插入的元素不一定比左半边元素来的大，
　　* 因此需要先将元素插入左半边，然后利用左半边为大顶堆的特点，取出堆顶元素即为最大元素，此时插入右半边 */
　　left.add(val);
　　right.add(left.poll());
　　} else {
　　right.add(val);
　　left.add(right.poll());
　　}
　　N++;
　　}
　　public Double GetMedian() {
　　if (N % 2 == 0)
　　return (left.peek() + right.peek()) / 2.0;
　　else
　　return (double) right.peek();
　　}
　　算法描述： 设置一个大顶堆left和小顶堆right； 当数据流的个数为偶数，将输入的数插入大顶堆left，并将大顶堆的根元素弹出插入小顶堆right； 当数据流的个数为奇数，将输入的数插入小顶堆right，并将大顶堆的根元素弹出插入大顶堆left； 这样right里面的数都比left里面的数大，若数据流个数为偶数，要获得中位数大小，取left和right根元素的平均值； 若数据流个数为奇数，此时right里元素比left里刚好多一个，要获得中位数大小，取right根元素值即可。
　　问题三：字符流中第一个不重复的字符
　　请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 ＂go＂ 时，第一个只出现一次的字符是 ＂g＂。当从该字符流中读出前六个字符＂google＂ 时，第一个只出现一次的字符是 ＂l＂。
　　代码如下：
　　private int[] cnts = new int[128];
　　private Queue queue = new LinkedList<>();
　　public void Insert(char ch) {
　　cnts[ch]++;
　　queue.add(ch);
　　while (!queue.isEmpty() && cnts[queue.peek()] > 1)
　　queue.poll();
　　}
　　public char FirstAppearingOnce() {
　　return queue.isEmpty() ? ＂#＂ : queue.peek();
　　}
　　算法描述： 定义一个128位的整型数组cnts（每个元素代表一个ASCII码字符），以及一个字符型队列queue； 每输入一个字符，该字符对应的cnts位元素值加1； 将该字符入队列queue； 从头至尾迭代队列queue，若队列字符对应的cnts位元素值大于1，队列头元素弹出； 此时队列的头元素即为字符流中第一个不重复的字符。
　　问题四：滑动窗口的最大值
　　例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，他们的最大值分别为 {4, 4, 6, 6, 6, 5}。
　　代码如下：
　　public ArrayList maxInWindows(int[] num, int size) {
　　ArrayList ret = new ArrayList<>();
　　if (size > num.length || size < 1)
　　return ret;
　　PriorityQueue heap = new PriorityQueue<>((o1, o2) -> o2 - o1); /* 大顶堆 */
　　for (int i = 0; i < size; i++)
　　heap.add(num[i]);
　　ret.add(heap.peek());
　　for (int i = 0, j = i + size; j < num.length; i++, j++) { /* 维护一个大小为 size 的大顶堆 */
　　heap.remove(num[i]);
　　heap.add(num[j]);
　　ret.add(heap.peek());
　　}
　　return ret;
　　}
　　算法描述： 设置一个最大堆heap，窗口大小为size； 先将数组中前size个元素入堆中，得到根元素为第一个窗口的最大值，入最大值链表； 将窗口第一个元素从堆中删除，即将窗口向前移动一位；窗口最右边的新元素入堆中，再将此时堆中根元素入最大值链表； 迭代至窗口滑动到最右边，返回最大值链表，程序结束。
　　注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。