1、优先队列好像一般都叫堆，以大顶堆为例，顶部第一个元素最大，底部最后一个元素最小，自顶向底是递减的（更准确的说是非递增的），对外只能访问顶部第一个元素（对应索引为0）和底部最后一个元素（对应索引为-1）；在Python中，heapq默认维护小顶堆，构造大顶堆时需要在入堆时添加相反数
2、本次博客总结下用优先队列解决TopK简单问题，比如数组中第K大或小的元素、单个序列里第K大或小的距离、根据元素的出现频率排序的问题
1、TopK简单问题的经典题目：求第K大，直接想到用大顶堆，把数组中所有元素入堆，返回堆中第k个元素作为结果
2、该题也可以用小顶堆，始终维护堆的元素总数为k，那么堆顶元素即为第k个最大元素——这种解法在实际中更合适，好像有一种TopK 大用小顶堆，TopK 小用大顶堆反着来的意思
from typing import List
import heapq
'''
215. 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
题眼：Top K
思路1、大顶堆：返回堆中第k个元素作为结果
思路2、小顶堆：始终维护堆的元素总数为k，那么堆顶元素即为第k个最大元素
'''
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
# # 思路1、大顶堆：返回堆中第k个元素作为结果
# que = []
# for n in nums:
# heapq.heappush(que, -n) # 添加相反数：因为python默认维护小顶堆
# for _ in range(k - 1):
# heapq.heappop(que)
# return -que[0]
# 思路2、小顶堆：始终维护堆的元素总数为k，那么堆顶元素即为第k个最大元素
que = []
for n in nums:
heapq.heappush(que, n)
if len(que) > k:
heapq.heappop(que)
return que[0]
if __name__ == "__main__":
obj = Solution()
while True:
try:
in_line = input().strip().split('=')
nums = []
for n in in_line[0].split('[')[1].split(']')[0].split(','):
nums.append(int(n))
k = int(in_line[1].strip())
print(obj.findKthLargest(nums, k))
except EOFError:
break
1、TopK简单问题的经典题目：是“215. 数组中的第K个最大元素”的特例，K取3，同时注意这个题有两个细节：一是要把元素去重（使用集合），二是去重后元素总数不足3个时，返回最大值
2、按照上一个题的经验：TopK 大用小顶堆，TopK 小用大顶堆反着来，这道题直接用小顶堆，并始终维护堆的元素总数不超过k
from typing import List
import heapq
'''
414. 第三大的数
给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。
示例 1:
输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。
题眼：Top K
思路：“215. 数组中的第K个最大元素”的扩展，需要先将元素去重复
'''
class Solution:
def thirdMax(self, nums: List[int]) -> int:
nums = set(nums) # 去重
# 小顶堆，维持元素总数为3
que = []
for n in nums:
heapq.heappush(que, n)
if len(que) > 3:
heapq.heappop(que)
if len(que) < 3:
return que[-1]
else:
return que[0]
if __name__ == "__main__":
obj = Solution()
while True:
try:
in_line = input().strip()[1: -1]
nums = [int(i) for i in in_line.split(',')]
print(obj.thirdMax(nums))
except EOFError:
break
1、TopK简单问题的经典题目：是“215. 数组中的第K个最大元素”的扩展，数组会不断的添加新元素进来，并要求添加元素时返回此时新数组的第 K 大元素
2、按照“215. 数组中的第K个最大元素”的经验：TopK 大用小顶堆，TopK 小用大顶堆反着来，这道题直接用小顶堆，并始终维护堆的元素总数不超过K，这样添加新元素时，进行一次入堆和一次出堆就搞定了，用大顶堆就会比较麻烦了
from typing import List
import heapq
'''
703. 数据流中的第 K 大元素
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
示例 1:
输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]
解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8
题眼：Top K（“215. 数组中的第K个最大元素”的扩展）
思路、小顶堆：始终维护堆的元素总数为k，那么堆顶元素即为第k个频率的元素
'''
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.que = []
self.k = k
# 建立小顶堆维护，并保持总的元素数量为k，那么堆顶即为第k个最大的数
for n in nums:
heapq.heappush(self.que, n)
if len(self.que) > k:
heapq.heappop(self.que)
def add(self, val: int) -> int:
heapq.heappush(self.que, val) # 为了防止队列内元素总数不足k个，因此把元素先加进去
if len(self.que) > self.k:
heapq.heappop(self.que)
return self.que[0]
if __name__ == "__main__":
obj = KthLargest(3, [4, 5, 8, 2])
print(obj.add(3))
print(obj.add(5))
print(obj.add(10))
print(obj.add(9))
print(obj.add(4))
1、TopK简单问题的经典题目：是“215. 数组中的第K个最大元素”的扩展，只要简单计算下距离就转换为第K小元素了
2、按照“215. 数组中的第K个最大元素”的经验：TopK 大用小顶堆，TopK 小用大顶堆反着来，这道题直接用大顶堆，并始终维护堆的元素总数不超过K，注意用小顶堆在Python中是添加相反数
from typing import List
import heapq
'''
973. 最接近原点的 K 个点
给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。
这里，平面上两点之间的距离是 欧几里德距离（ √(x1 - x2)2 + (y1 - y2)2 ）。
你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案 确保 是 唯一 的。
示例 1:
输入：points = [[1,3],[-2,2]], k = 1
输出：[[-2,2]]
解释：
(1, 3) 和原点之间的距离为 sqrt(10)，
(-2, 2) 和原点之间的距离为 sqrt(8)，
由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。
题眼：Top K（“215. 数组中的第K个最大元素”的扩展）
思路、题目是要求k个最小值，大顶堆：始终维护堆的元素总数为k，那么堆内元素即为k个最小值
'''
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
# k个最小值，大顶堆：维持元素总数为k
result = []
que = []
for point in points:
x, y = point[0], point[1]
d = x * x + y * y
heapq.heappush(que, (-d, [x, y])) # 添加相反数：因为python默认维护小顶堆
if len(que) > k:
heapq.heappop(que)
for _ in range(k):
result.append(heapq.heappop(que)[1])
return result
if __name__ == "__main__":
obj = Solution()
while True:
try:
in_line = input().strip().split('=')
points = []
for row in in_line[1][2: -5].split(']')[: -1]:
points.append([int(n) for n in row.split('[')[1].split(',')])
k = int(in_line[2].strip())
print(obj.kClosest(points, k))
except EOFError:
break
1、TopK简单问题的经典题目：是“215. 数组中的第K个最大元素”的扩展，需要先统计元素出现频率的哈希表，然后就是Top K问题的模板了
2、按照“215. 数组中的第K个最大元素”的经验：TopK 大用小顶堆，TopK 小用大顶堆反着来，这道题直接用小顶堆，并始终维护堆的元素总数不超过K，注意入堆的形式为（频率，元素）的元组
from typing import List
import heapq
'''
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
题眼：Top K（“215. 数组中的第K个最大元素”的扩展）
思路1、大顶堆：返回堆中第k个频率的元素作为结果
思路2、小顶堆：始终维护堆的元素总数为k，那么堆顶元素即为第k个频率的元素
'''
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# # 思路一、大顶堆：返回堆中第k个频率的元素作为结果
# # 1、统计数组元素频率
# hashTable = {}
# for n in nums:
# if n not in hashTable:
# hashTable[n] = 1
# else:
# hashTable[n] += 1
# # 2、构建大顶堆
# que = []
# for key in hashTable:
# heapq.heappush(que, (-hashTable[key], key)) # 添加相反数：因为python默认维护小顶堆
# # 3、输出大顶堆的前k个元素
# result = []
# for i in range(k):
# result.append(heapq.heappop(que)[1])
# return result
# # 思路二、小顶堆：始终维护堆的元素总数为k，那么堆顶元素即为第k个频率的元素
# 1、统计数组元素频率
hashTable = {}
for n in nums:
if n not in hashTable:
hashTable[n] = 1
else:
hashTable[n] += 1
# 2、构建小顶堆，并维持其元素数量不多于k
que = []
for key in hashTable:
heapq.heappush(que, (hashTable[key], key))
if len(que) > k:
heapq.heappop(que)
# 3、输出大顶堆的k个元素，逆序放入结果数组
result = [0] * k
for i in range(k - 1, -1, -1):
result[i] = heapq.heappop(que)[1]
return result
if __name__ == "__main__":
obj = Solution()
while True:
try:
in_line = input().strip().split('=')
nums = [int(i) for i in in_line[1].split('[')[1].split(']')[0].split(',')]
k = int(in_line[2].strip())
print(obj.topKFrequent(nums, k))
except EOFError:
break
1、TopK简单问题的经典题目：是“215. 数组中的第K个最大元素”的扩展，同样需要先统计元素出现频率的哈希表，
2、这道题是要对所有的字符出现频率进行排序，因此和“215. 数组中的第K个最大元素”的经验：TopK 大用小顶堆，TopK 小用大顶堆不那么一致了，直接用大顶堆，将所有（频率，元素）的元组入堆，然后持续出堆返回结果就可以了
import heapq
'''
451. 根据字符出现频率排序
给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串。如果有多个答案，返回其中任何一个。
示例 1:
输入: s = "tree"
输出: "eert"
解释: 'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
题眼：Top K
思路：这道题是要对所有的字符出现频率进行排序，因此和“215. 数组中的第K个最大元素”的经验：TopK 大用小顶堆，TopK 小用大顶堆不那么一致了，直接用大顶堆，
将所有（频率，元素）的元组入堆，然后持续出堆返回结果就可以了
'''
class Solution:
def frequencySort(self, s: str) -> str:
# 1、统计词频
hashTable = {}
for ch in s:
if ch not in hashTable:
hashTable[ch] = 1
else:
hashTable[ch] += 1
# 2、建立大顶堆
que = []
for k in hashTable:
heapq.heappush(que, (-hashTable[k], k))
# 3、建立结果字符串
result = ''
while len(que) > 0:
pair = heapq.heappop(que)
result += pair[1] * (-pair[0])
return result
if __name__ == "__main__":
obj = Solution()
while True:
try:
s = input().strip().split('=')[1].strip()[1: -1]
print(obj.frequencySort(s))
except EOFError:
break
1、TopK简单问题的经典题目：是“215. 数组中的第K个最大元素”的扩展，同样需要先统计元素出现频率的哈希表，额外增加了对词频相同的元素的排序要求：字典次序小的排前面，因此需要重写<，即__lt__()函数
2、按照“215. 数组中的第K个最大元素”的经验：TopK 大用小顶堆，TopK 小用大顶堆反着来，这道题直接用小顶堆，并始终维护堆的元素总数不超过K，注意入堆的形式为（频率，元素）的元组，
3、由于维护的是小顶堆，那么频率值小的就要排在堆顶，频率值一样时让字典次序大的排在堆顶，这样保留下来的K个元素就满足题意要求的频率值大，字典次序小，最后把这些元素出堆逆序存放到结果数组中
from typing import List
import heapq
'''
692. 前K个高频单词
给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
示例 1:
输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 "i" 在 "love" 之前。
题眼：Top K（“215. 数组中的第K个最大元素”的扩展）
思路：题目是要求k个最大值，小顶堆：始终维护堆的元素总数为k，那么堆内元素即为k个最大值
难点：这道题对答案的唯一性进行了限制，因此要重写小于号！
'''
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
class Comparer: # 重写小于号：出现次数少的在堆顶、次数一样字典序大的在堆顶
def __init__(self, val, key):
self.val = val
self.key = key
def __lt__(self, other):
if self.val != other.val:
return self.val < other.val
return self.key > other.key
# 1、统计词频
hashTable = {}
for n in words:
if n not in hashTable:
hashTable[n] = 1
else:
hashTable[n] += 1
# 2、建立优先队列：维护元素总数为k
que = []
for key in hashTable:
heapq.heappush(que, Comparer(hashTable[key], key))
if len(que) > k:
heapq.heappop(que)
# 3、输出结果
result = ['0'] * k
for i in range(k - 1, -1, -1):
result[i] = heapq.heappop(que).key
return result
