堆的定义

堆（Heap）是一种特殊的树形数据结构，通常是一个完全二叉树。在堆中，每个节点都满足堆的性质：

  • 最大堆：父节点的值大于或等于其所有子节点的值。例如，在最大堆中，根节点是整个堆中的最大值。
  • 最小堆：父节点的值小于或等于其所有子节点的值。在最小堆中，根节点是整个堆中的最小值。

堆的存储

堆通常使用数组来实现存储。对于完全二叉树，假设根节点存储在数组索引为 0 的位置，对于任意节点存储在数组索引为 i 的位置：

  • 它的左子节点存储在数组索引为 2 * i + 1 的位置。
  • 它的右子节点存储在数组索引为 2 * i + 2 的位置。
  • 它的父节点存储在数组索引为 (i - 1) // 2 的位置（向下取整）。

堆的基本操作

  1. 插入元素：
  • 先将新元素添加到堆的末尾（数组的最后一个位置）。
  • 然后将新元素与其父节点进行比较，如果不满足堆的性质，则与父节点交换位置。
  • 重复这个过程，直到新元素满足堆的性质或者到达根节点。
  1. 删除元素：
  • 在最大堆中，删除操作通常是删除根节点（最大值）。将根节点与堆的最后一个元素交换位置，然后删除最后一个元素。
  • 新的根节点可能不满足堆的性质，需要将其与子节点进行比较并交换，直到满足堆的性质。这个过程称为堆化（Heapify）。
  1. 构建堆：
  • 可以从一个无序的数组构建堆。从最后一个非叶子节点开始，对每个非叶子节点执行堆化操作，直到整个数组满足堆的性质。

堆的应用场景

  • 堆排序：利用堆的性质进行排序。可以在O(nlogn)时间复杂度内对数组进行排序。
  • 优先队列：堆可以高效地实现优先队列。优先队列是一种数据结构，其中每个元素都有一个优先级，元素按照优先级出队。例如，在操作系统中，任务调度可以使用优先队列，高优先级的任务先执行。
  • Dijkstra 算法：用于在图中求单源最短路径，算法中使用最小堆来存储未确定最短路径的节点，每次从堆中取出距离源点最短距离的节点进行松弛操作。
  1. 前K个高频元素

Link: https://leetcode.cn/problems/g5c51o/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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]