又被为优先队列(priority queue)。尽管名为优先队列，但堆并不是队列。回忆一下，在队列中，我们可以进行的限定操作是dequeue和enqueue。
dequeue是按照进入队列的先后顺序来取出元素。而在堆中，我们不是按照元素进入队列的先后顺序取出元素的，而是按照元素的优先级取出元素。
堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质。
上浮（Promotion）
情境: 子节点的键值变为比父节点的键值大；如下面添加字节点
消除这种违反项：
堆的添加：
下沉（Demotion）
情境：父节点的键值变得比子节点（一个或者2个） 的键值还小 ，如下面删除了根节点后拿了个小子节点补充上来的情况
消除这种违反项：
删除最大值
参考博客：python数据结构之堆(heap) - kumata - 博客园
python实现常见堆操作
# 堆化实现 heapify(x)
def heapify(heap, n,index):
# Transform list into a heap, in-place,index开始标志
#n = len(heap)
left = index * 2 + 1 # 左孩子下标
while left < n:
largest = left+1 if left + 1 < n and heap[left + 1] > heap[left] else left
largest = largest if heap[largest] > heap[index] else index
if largest == index:
break
heap[index], heap[largest] = heap[largest], heap[index]
index = largest
left = index * 2 + 1
def heapinsert(heap, index):
f=int((index-1)>>1)
while heap[index]>heap[f]:
heap[index],heap[f] =heap[f] ,heap[index]
index=f
def heapSort(arr):
n = len(arr)
# Build a maxheap.
for i in range(n, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # 交换
heapify(arr, i, 0)
if __name__ == '__main__':
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
# for i in range(0, n, 1):
# heapinsert(arr, i)
print("排序后")
for i in range(n):
print("%d" % arr[i])
python内置方法创建堆有两种方式，heappush()和heapify()
heaqp模块提供了堆队列算法的实现，也称为优先级队列算法。
要创建堆，请使用初始化为[]的列表，或者可以通过函数heapify（）将填充列表转换为堆。 提供以下功能： heapq.heappush（堆，项目） 将值项推入堆中，保持堆不变。
heapq.heapify（x） 在线性时间内将列表x转换为堆。 heapq.heappop（堆） 弹出并返回堆中的最小项，保持堆不变。如果堆是空的，则引发IndexError。
'''
heaqp模块提供了堆队列算法的实现，也称为优先级队列算法。
要创建堆，请使用初始化为[]的列表，或者可以通过函数heapify（）将填充列表转换为堆。
提供以下功能：
heapq.heappush（堆，项目）
将值项推入堆中，保持堆不变。
heapq.heapify（x）
在线性时间内将列表x转换为堆。
heapq.heappop（堆）
弹出并返回堆中的最小项，保持堆不变。如果堆是空的，则引发IndexError。
'''
import heapq
#1 heappush生成堆+ heappop把堆从小到大pop出来
heap = []
data = [1,3,5,7,9,2,4,6,8,0]
for i in data:
heapq.heappush(heap,i)
print(heap)
lis = []
while heap:
lis.append(heapq.heappop(heap))
print(lis)
#2 heapify生成堆+ heappop把堆从小到大pop出来
data2 = [1,5,3,2,9,5]
heapq.heapify(data2)
print(data2)
lis2 = []
while data2:
lis2.append(heapq.heappop(data2))
print(lis2)
#输出结果
[0, 1, 2, 6, 3, 5, 4, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 5, 9, 5]
[1, 2, 3, 5, 5, 9]215. 数组中的第K个最大元素
难度中等950
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:输入:
[3,2,1,5,6,4] 和k = 2 输出: 5示例 2:输入:
[3,2,3,1,2,4,5,5,6] 和k = 4 输出: 4
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
nums.sort(reverse=True)
return nums[k-1]
方法二：堆排序
方法三快速选择
#215. 数组中的第K个最大元素
import heapq
def findKthLargest(nums, k: int) :
# nums.sort(reverse=True)
# return nums[k-1]
heap=[]
for i in nums:
heapq.heappush(heap, i*-1)
print(heap)
while k>1:
k=k-1
heapq.heappop(heap)
print(heap)
return heap[0]*-1
nums=[3,2,1,1,5,6,4]
k=2
# nums=[3,2,3,1,2,4,5,5,6]
# k=4
print(findKthLargest(nums, k))692. 前K个高频单词
难度中等222
给一非空的单词列表，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
示例 1：
输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2 输出: ["i", "love"] 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。 注意，按字母顺序 "i" 在 "love" 之前。
#692. 前K个高频单词
from collections import Counter
def topKFrequent(words, k: int):
count = Counter(words)
candidates = list(count.keys())
candidates.sort(key=lambda w: (-count[w], w))
print(candidates)
return candidates[:k]
words=["i", "love", "leetcode", "i", "love", "coding"]
k = 2
print(topKFrequent(words, k))
from collections import Counter
import heapq
def topKFrequent(words, k: int):
count = Counter(words)
# candidates = list(count.keys())
# candidates.sort(key=lambda w: (-count[w], w))
# print(candidates)
# return candidates[:k]
#堆
heap,ans=[],[]
heap = [(-freq, word) for word, freq in count.items()]
heapq.heapify(heap)
for i in range(k):
ans.append(heapq.heappop(heap)[1])
return ans
words=["i", "leetcode","love", "leetcode", "i", "love", "coding"]
k = 2
print(topKFrequent(words, k))
