内容简介：优先队列，对比队列而已，顾名思义，就是正常入，按优先级出。可以按小到大，也可以按大到小，或者自定义一个属性，按属性的特征进行出队列。Heap常见的有小顶堆和大顶堆。小顶堆图上演示的是用二叉堆实现的，优先级越小的越排在前面，父亲节点的值比左孩子和右孩子都要小，有兴趣的可以自己实现一个小顶堆。
优先队列，对比队列而已，顾名思义，就是正常入，按优先级出。可以按小到大，也可以按大到小，或者自定义一个属性，按属性的特征进行出队列。
2. 实现机制
2.1 Heap 堆
Heap常见的有小顶堆和大顶堆。
小顶堆图上演示的是用二叉堆实现的，优先级越小的越排在前面，父亲节点的值比左孩子和右孩子都要小，有兴趣的可以自己实现一个小顶堆。
同理大顶堆类似，父亲节点的值比左右孩子的值都要大。
堆的实现其实还有很多种，给大家分享一个链接，Google Heap就能查找的到。 en.wikipedia.org/wiki/Heap_(…
这个内容里面有一张图给大家分享一下
各种堆的实现方式和时间复杂度，有兴趣的可以深入了解一下，刚才上面图片演示的就是Binary实现方式。
2.2 Binary Search Tree二叉搜索树
二叉搜索树，也叫二叉查找树，后面章节会详细介绍。简单介绍一个特性:
- 若任意节点的左⼦树不空，则左⼦树上所有结点的值均⼩于它的 根结点的值；
- 若任意节点的右⼦树不空，则右⼦树上所有结点的值均⼤于它的 根结点的值；
- 任意节点的左、右⼦树也分别为⼆叉搜索树。
简单的说二叉搜索树的值有序的，左孩子的值<父亲节点<右孩子的值，按照树的中序遍历，则是一个按小到大的顺序。
3. 面试题
3.1 703. Kth Largest Element in a Stream 返回数据流中K大的元素
题目要求
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 返回窗口的最大值
题目要求给定一个数组 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)
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
