[算法面试现场] PriorityQueue 优先队列

优先队列，对比队列而已，顾名思义，就是正常入，按优先级出。可以按小到大，也可以按大到小，或者自定义一个属性，按属性的特征进行出队列。

2. 实现机制

2.1 Heap 堆

Heap常见的有小顶堆和大顶堆。

小顶堆图上演示的是用二叉堆实现的，优先级越小的越排在前面，父亲节点的值比左孩子和右孩子都要小，有兴趣的可以自己实现一个小顶堆。

同理大顶堆类似，父亲节点的值比左右孩子的值都要大。

堆的实现其实还有很多种，给大家分享一个链接，Google Heap就能查找的到。 en.wikipedia.org/wiki/Heap_(…

这个内容里面有一张图给大家分享一下

各种堆的实现方式和时间复杂度，有兴趣的可以深入了解一下，刚才上面图片演示的就是Binary实现方式。

2.2 Binary Search Tree二叉搜索树

二叉搜索树，也叫二叉查找树，后面章节会详细介绍。简单介绍一个特性:

1. 若任意节点的左⼦树不空，则左⼦树上所有结点的值均⼩于它的 根结点的值；
2. 若任意节点的右⼦树不空，则右⼦树上所有结点的值均⼤于它的 根结点的值；
3. 任意节点的左、右⼦树也分别为⼆叉搜索树。

简单的说二叉搜索树的值有序的，左孩子的值<父亲节点<右孩子的值，按照树的中序遍历，则是一个按小到大的顺序。

3. 面试题

3.1 703. Kth Largest Element in a Stream 返回数据流中K大的元素

leetcode 第703题

题目要求

Design a class to find the kth largest element in a stream.
  设计一个找到数据流中第K大元素的类（class）
复制代码

Example:

int k = 3;
  int[] arr = [4,5,8,2];
  KthLargest kthLargest = new KthLargest(3, arr);
  kthLargest.add(3);   // returns 4
  kthLargest.add(5);   // returns 5
  kthLargest.add(10);  // returns 5
  kthLargest.add(9);   // returns 8
  kthLargest.add(4);   // returns 8
复制代码

解题思路

假设K=1的话，其实就是从数据流中的最大值，问题就比较简单了，即每次记录最大值即可，比如例子中的[4,5,8,2]，那只要每次和记录的Max比较即可。 同理，如果是求第K个最大的元素，有2种解法:

• 第一种: 用一个array保留前K个最大的元素，并将其排序。即每次来一个元素，则与这个array中最小的值比较，如果元素的值比最小的值大，则将array中最小的元素pop掉，将当前元素插入array，并再次排序。 时间复杂度是 N * klogk，klogk是 排序 的时间复杂度（算最快的快排）。
• 第二种: 第一种的话还是有点慢，第二种则采用今天的主题优先队列来实现，每次维护一个小顶堆MinHeap即可。MinHeap的size是k，每次来元素与堆顶的元素比较，比堆顶元素小，则继续往下走，比堆顶元素大，则剔除堆顶元素，将当前元素插入MinHeap，并重新调整堆的顺序。时间复杂度，N * (1 or log2K），最差是每次都需要调整堆，调整堆的时间复杂度是Log2K。如果不需要调整，则是O(1)。

代码实现

代码实现以第二种方式。

import heapq

    class KthLargest(object):
      def __init__(self, k, nums):
          """
          :type k: int
          :type nums: List[int]
          """
          self.k = k
          self.min_heap = []
          for i in nums:
              self.add(i)

      def add(self, val):
          """
          :type val: int
          :rtype: int
          """
          if len(self.min_heap) < self.k:
              heapq.heappush(self.min_heap, val)
          else:
              if val > self.min_heap[0]:
                  heapq.heappop(self.min_heap)
                  heapq.heappush(self.min_heap, val)
          return self.min_heap[0]
复制代码

这里用了 python 内置实现小顶堆的模块heapq，如果是别的语言，应该也有对应的内部实现堆的函数。heappush就是往堆里面插入元素，函数会再次调整好顺序，heappop就是讲堆顶元素pop。代码实现思路与上面文字描述一致。

3.2 239. Sliding Window Maximum 返回窗口的最大值

leetcode 第239题

题目要求给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。 返回滑动窗口最大值。

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7      3
1 [3  -1  -3] 5  3  6  7       3
1  3 [-1  -3  5] 3  6  7       5
1  3  -1 [-3  5  3] 6  7       5
1  3  -1  -3 [5  3  6] 7       6
1  3  -1  -3  5 [3  6  7]      7
复制代码

解题思路此题也有两种解法。

• 第一种解法: 采用大顶端实现，维护一个size=k的MaxHeap，同时再维护一个Count的Map，记录每一个值得位置。比如开始[1,3,-1]，则堆顶是3，返回最大值是3,如果再来一个-3，比3小，堆顶依然是3，但是最初的1需要从堆中去掉，将-3加入进来。所以需要维护这个堆，删除旧元素，加入新元素，同时结果就是堆顶。代码会待会给大家演示。时间复杂度是 NlogK 。
• 第二种: 第一种还是比较复杂的，还可以简化，题目的特点是每次需要维护的窗口是一定的，即size=k，那么可以使用上一篇讲的Queue实现，但是有点区别是这里需要使用双端队列deque，即两边都可以进和出。怎么实现了？ 将k个元素依次加入到deque里，同时每次一个新元素进来的话进行队列的维护。 重点就在维护的逻辑，首先保证deque的长度不能大于k, 同时最左边的元素永远是最大的元素。 比如[1,3,-1]，那么deque维护之后就变成[3, -1]，因为1比3小，还比3老，那肯定不会是我们要找的元素，结果就是3。再加一个-3，deque就变成[3,-1,-3]，因为-3比3小，所以加到最新的位置即可，结果还是3。再来一个5，首先将旧元素-3剔除，变成[-1,-3,5]，如果比较这三个元素，发现-1,-3都比5小，则全部再次剔除变成[5]，所以结果是5。 文字描述举例输出结果就是[3,3,5]

代码实现

• 第一种解法: MaxHeap实现

import collections
import heapq

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        count_map, max_heap, result = collections.Counter(), [], []
        for i, num in enumerate(nums):
            heapq.heappush(max_heap, -num)
            count_map[num] += 1 # 记录每个元素的count
            while not count_map[-max_heap[0]]: # 清除堆顶的旧元素
                heapq.heappop(max_heap)
            if i >= k - 1:
                result.append(-max_heap[0])
                count_map[nums[i - k + 1]] -= 1 # 将位置在k之前的元素count变为0
        return result
复制代码

大顶端还是使用heapq实现，CountMap使用python内部实现的Counter()，里面就是一个Map，key是num，value是count。需要说明的是，heapq默认是小顶堆，如果需要实现大顶端，需要小技巧，就是将num变负数，比如[1,2,3]，默认情况下是堆顶是1，但是变负数-num，[-1,-2,-3]，则就变成堆顶是-3，从而实现了MaxHeap。 还有一个注意的是，这里没有每次去不是堆顶的且count=0的旧元素，而是等它变成堆顶的情况，如果发现是少于size=k之前的元素，则清除。这样比较好实现一点，可能理解上稍微变难了点。

• 第二种解法: deque双端队列 （推荐解法）

class Solution(object):
    """
    deque实现
    """
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if not nums:
            return []
        result, window = [], []
        for i, num in enumerate(nums):
            if i >= k and window[0] <= i - k:
                window.pop(0) # 从队列最左边清除旧元素
            while window and nums[window[-1]] <= num:
                window.pop() # 从队列右边清除比当前元素小的元素
            window.append(i)
            if i >= k - 1:
                result.append(nums[window[0]])
        return result
复制代码

第二种解法采用双端队列，循环枚举nums，window是记录nums元素的下标，而不是值，如果发现window最左边的元素下标超过i-k，则元素过时，需要从队列的最左边将元素剔除。如果发现window最右边的元素比当前元素小，则也全部剔除，当前元素肯定比这些元素小的要更新，将当前元素插入window即可，同时取window最左边的值为结果，因为最左边的值永远最大。

完整代码已上传github github.com/CrystalSkyZ…

更多算法文章请关注小专栏 xiaozhuanlan.com/leetcode_tc

更多精彩文章请关注公众号 天澄的技术笔记 (ChengTian_Tech)