「漫步计算机系统」之数据结构与算法（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);

}

算法描述：

1. 从头至尾迭代数组；
2. 将数组元素压入最大堆maxHeap；
3. 若压入的数量超出了K，弹出堆的根元素，即队中最大值元素；
4. 迭代结束，堆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();

}

算法描述：

1. 设置一个大顶堆left和小顶堆right；
2. 当数据流的个数为偶数，将输入的数插入大顶堆left，并将大顶堆的根元素弹出插入小顶堆right；
3. 当数据流的个数为奇数，将输入的数插入小顶堆right，并将大顶堆的根元素弹出插入大顶堆left；
4. 这样right里面的数都比left里面的数大，若数据流个数为偶数，要获得中位数大小，取left和right根元素的平均值；
5. 若数据流个数为奇数，此时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();

}

算法描述：

1. 定义一个128位的整型数组cnts（每个元素代表一个ASCII码字符），以及一个字符型队列queue；
2. 每输入一个字符，该字符对应的cnts位元素值加1；
3. 将该字符入队列queue；
4. 从头至尾迭代队列queue，若队列字符对应的cnts位元素值大于1，队列头元素弹出；
5. 此时队列的头元素即为字符流中第一个不重复的字符。

问题四：滑动窗口的最大值

例如，如果输入数组 {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;

}

算法描述：

1. 设置一个最大堆heap，窗口大小为size；
2. 先将数组中前size个元素入堆中，得到根元素为第一个窗口的最大值，入最大值链表；
3. 将窗口第一个元素从堆中删除，即将窗口向前移动一位；窗口最右边的新元素入堆中，再将此时堆中根元素入最大值链表；
4. 迭代至窗口滑动到最右边，返回最大值链表，程序结束。

注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。