第四章：哈希表与堆

本章目标

本章学习两个高频工具：哈希表和堆。哈希表把查找从线性扫描变成平均 O(1)，堆可以在动态数据中维护最小值或最大值。

你会用 dict 统计频率，用 heapq 求 Top-K，并理解优先队列适合什么场景。

核心概念

哈希表通过 key 映射到存储位置，适合去重、计数、缓存和快速判断是否存在。

堆是一种满足父节点不大于子节点的树形结构。Python 的 heapq 是小根堆，弹出堆顶是 O(log n)。

Python 示例

dict 统计频率是哈希表最常见的入口。

def count_words(words):
    freq = {}
    for word in words:
        freq[word] = freq.get(word, 0) + 1
    return freq

heapq 可以维护最大的 k 个数：堆大小超过 k 时弹出当前最小值。

import heapq

def top_k(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return sorted(heap, reverse=True)

复杂度与常见误区

哈希表查找平均是 O(1)，但需要 O(n) 额外空间保存键值。堆插入和删除堆顶是 O(log k)，Top-K 常见复杂度是 O(n log k)。

常见误区是把堆当成完整排序。堆只保证堆顶最小，不保证内部数组整体有序。

本章要点

需要存在性、计数、映射时先考虑哈希表；需要动态取最值时考虑堆或优先队列。

Python 的 dict、set、heapq 是算法题和工程脚本都很实用的基础工具。