堆的定义
堆（Heap）是一种特殊的树形数据结构，通常是一个完全二叉树。在堆中，每个节点都满足堆的性质：
- 最大堆：父节点的值大于或等于其所有子节点的值。例如，在最大堆中，根节点是整个堆中的最大值。
- 最小堆：父节点的值小于或等于其所有子节点的值。在最小堆中，根节点是整个堆中的最小值。
堆的存储
堆通常使用数组来实现存储。对于完全二叉树，假设根节点存储在数组索引为 0 的位置，对于任意节点存储在数组索引为 i 的位置：
- 它的左子节点存储在数组索引为
2 * i 1的位置。 - 它的右子节点存储在数组索引为
2 * i 2的位置。 - 它的父节点存储在数组索引为
(i - 1) // 2的位置（向下取整）。
堆的基本操作
- 插入元素：
- 先将新元素添加到堆的末尾（数组的最后一个位置）。
- 然后将新元素与其父节点进行比较，如果不满足堆的性质，则与父节点交换位置。
- 重复这个过程，直到新元素满足堆的性质或者到达根节点。
- 删除元素：
- 在最大堆中，删除操作通常是删除根节点（最大值）。将根节点与堆的最后一个元素交换位置，然后删除最后一个元素。
- 新的根节点可能不满足堆的性质，需要将其与子节点进行比较并交换，直到满足堆的性质。这个过程称为堆化（Heapify）。
- 构建堆：
- 可以从一个无序的数组构建堆。从最后一个非叶子节点开始，对每个非叶子节点执行堆化操作，直到整个数组满足堆的性质。
堆的应用场景
- 堆排序：利用堆的性质进行排序。可以在
O(nlogn)时间复杂度内对数组进行排序。 - 优先队列：堆可以高效地实现优先队列。优先队列是一种数据结构，其中每个元素都有一个优先级，元素按照优先级出队。例如，在操作系统中，任务调度可以使用优先队列，高优先级的任务先执行。
- Dijkstra 算法：用于在图中求单源最短路径，算法中使用最小堆来存储未确定最短路径的节点，每次从堆中取出距离源点最短距离的节点进行松弛操作。
- 前K个高频元素
Link: https://leetcode.cn/problems/g5c51o/description/
代码语言：javascript复制def heapAppend(heap, nMap, num):
heap.append(num)
cur = len(heap) - 1
parent = (cur - 1) // 2
while parent >= 0:
if nMap[heap[cur]] < nMap[heap[parent]]:
heap[cur], heap[parent] = heap[parent], heap[cur]
cur = parent
parent = (cur - 1) // 2
def heapify(heap, nMap, i):
if i >= len(heap):
return
leftChild = 2 * i 1
rightChild = 2 * i 2
minEle = i
if leftChild < len(heap) and nMap[heap[leftChild]] < nMap[heap[minEle]]:
minEle = leftChild
if rightChild < len(heap) and nMap[heap[rightChild]] < nMap[heap[minEle]]:
minEle = rightChild
if minEle != i:
heap[minEle], heap[i] = heap[i], heap[minEle]
heapify(heap, nMap, minEle)
def stack(heap, nMap, k):
for num in nMap.keys():
if len(heap) < k:
heapAppend(heap, nMap, num)
else:
if nMap[num] < nMap[heap[0]]:
continue
else:
heap[0] = num
heapify(heap, nMap, 0)
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
nMap = {}
heap = []
for num in nums:
if num not in nMap:
nMap[num] = 1
else:
nMap[num] = 1
stack(heap, nMap, k)
return heap用Python的heapq实现：
代码语言：javascript复制import heapq
def stack(heap, nMap, k):
for num in nMap.keys():
if len(heap) < k:
heapq.heappush(heap, (nMap[num], num))
else:
if nMap[num] < heap[0][0]:
continue
else:
heapq.heapreplace(heap, (nMap[num], num))
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
nMap = {}
heap = []
for num in nums:
if num not in nMap:
nMap[num] = 1
else:
nMap[num] = 1
stack(heap, nMap, k)
return [x[1] for x in heap]
