堆（Heap）作为优先队列的核心实现，是算法面试的高频考点。以下是手动实现大顶堆和小顶堆的详解，结合代码实例与面试技巧：

⚙️ 一、堆的核心特性

  1. 完全二叉树结构
    堆本质是完全二叉树，可用紧凑数组存储（索引从0开始）：
    • 父节点索引：parent(i) = (i-1)//2
    • 左子节点索引：left(i) = 2*i + 1
    • 右子节点索引：right(i) = 2*i + 2
  2. 堆序性质
    • 大顶堆：父节点值 ≥ 子节点值 → 根节点为最大值
    • 小顶堆：父节点值 ≤ 子节点值 → 根节点为最小值

🧱 二、手动实现堆的关键操作

1. 大顶堆完整实现（Python）
class MaxHeap:
    def __init__(self):
        self.heap = []

    def insert(self, val):
        self.heap.append(val)  # 插入末尾
        self._sift_up(len(self.heap) - 1)  # 上浮调整

    def extract_max(self):
        if not self.heap: return None
        max_val = self.heap[0]
        self.heap[0] = self.heap[-1]  # 末尾元素移至堆顶
        self.heap.pop()
        self._sift_down(0)  # 下沉调整
        return max_val

    def _sift_up(self, idx):
        while idx > 0:
            parent_idx = (idx - 1) // 2
            if self.heap[idx] <= self.heap[parent_idx]:
                break
            # 交换父节点与当前节点
            self.heap[idx], self.heap[parent_idx] = self.heap[parent_idx], self.heap[idx]
            idx = parent_idx

    def _sift_down(self, idx):
        size = len(self.heap)
        while (left_idx := 2*idx + 1) < size:  # 存在左子节点
            right_idx = 2*idx + 2
            largest = idx
            # 比较左子节点
            if self.heap[left_idx] > self.heap[largest]:
                largest = left_idx
            # 比较右子节点（若存在）
            if right_idx < size and self.heap[right_idx] > self.heap[largest]:
                largest = right_idx
            if largest == idx: break  # 堆序已满足
            # 交换并继续下沉
            self.heap[idx], self.heap[largest] = self.heap[largest], self.heap[idx]
            idx = largest
2. 小顶堆的改动点

仅需修改比较方向：

class MinHeap(MaxHeap):
    def _sift_up(self, idx):
        while idx > 0:
            parent_idx = (idx - 1) // 2
            if self.heap[idx] >= self.heap[parent_idx]:  # 改为≥
                break
            self.heap[idx], self.heap[parent_idx] = self.heap[parent_idx], self.heap[idx]
            idx = parent_idx

    def _sift_down(self, idx):
        size = len(self.heap)
        while (left_idx := 2*idx + 1) < size:
            right_idx = 2*idx + 2
            smallest = idx
            if self.heap[left_idx] < self.heap[smallest]:  # 改为<
                smallest = left_idx
            if right_idx < size and self.heap[right_idx] < self.heap[smallest]:  # 改为<
                smallest = right_idx
            if smallest == idx: break
            self.heap[idx], self.heap[smallest] = self.heap[smallest], self.heap[idx]
            idx = smallest

⚡️ 三、核心操作原理解析

1. 插入操作（上浮调整）
  • 步骤：
    1. 新元素插入数组末尾
    2. 与其父节点比较
    3. 若破坏堆序则交换，递归上浮
  • 时间复杂度：O(log n)
    示例（大顶堆插入92）：

mermaid graph TD A[原始堆：100,90,80,30,60] --> B[插入92到末尾：100,90,80,30,60,92] B --> C[92>60 → 交换：100,90,80,92,60,30] C --> D[92>90 → 交换：100,92,80,90,60,30] D --> E[92<100 → 停止]

2. 删除堆顶（下沉调整）
  • 步骤：
    1. 堆顶与末尾元素交换
    2. 移除原堆顶（最大值）
    3. 新堆顶与其较大子节点比较，若需交换则下沉
  • 时间复杂度：O(log n)
    示例（删除大顶堆的100）：

mermaid graph TD A[原始堆：100,92,80,90,60,30] --> B[交换堆顶与末尾：30,92,80,90,60,100] B --> C[移除100 → 新堆：30,92,80,90,60] C --> D[30<92 → 与92交换：92,30,80,90,60] D --> E[30<90 → 与90交换：92,90,80,30,60] E --> F[30无子节点 → 停止]

💡 四、面试高频考点与技巧

  1. 手写堆排序
    • 步骤：
      1. 将无序数组构建成大顶堆（从最后一个非叶子节点开始调整）
      2. 重复交换堆顶与末尾元素 → 移除堆顶 → 调整剩余堆
    • 代码关键：
def heap_sort(arr):
    n = len(arr)
    # 构建大顶堆（从最后一个非叶子节点开始）
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)
    # 逐个提取最大值
    for i in range(n-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 交换堆顶与末尾
        heapify(arr, i, 0)  # 调整剩余堆
  1. Top K问题优化
    • 场景：海量数据中找前K个最大值
    • 解法：维护小顶堆（堆顶为最小屏障）
def top_k_max(nums, k):
    min_heap = []
    for num in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)
        elif num > min_heap[0]:  # 当前值 > 堆顶
            heapq.heapreplace(min_heap, num)  # 替换堆顶
    return min_heap
  1. 双向比较陷阱
    • 错误示例：下沉时未同时比较左右子节点
    • 正确做法：先比较左右子节点大小，再与父节点比较
# 在大顶堆下沉函数中：
left_val = heap[left_idx]
right_val = heap[right_idx] if right_idx < size else -float('inf')
larger_child = max(left_val, right_val)  # 先找到较大子节点
if larger_child > parent_val:  # 再与父节点比较
    swap(parent, larger_child)

🚀 五、性能优化技巧

  1. 减少交换次数
    上浮/下沉时暂存目标值，最后一次性写入（避免多次交换）：
def _sift_up_fast(self, idx):
     tmp = self.heap[idx]
     while idx > 0:
         parent_idx = (idx - 1) // 2
         if tmp <= self.heap[parent_idx]: break
         self.heap[idx] = self.heap[parent_idx]  # 父节点下移
         idx = parent_idx
     self.heap[idx] = tmp  # 最终位置写入
  1. 批量建堆优化
    直接对无序数组建堆（时间复杂度O(n)，优于逐个插入的O(n log n)）：
def build_heap(arr, is_max_heap=True):
     n = len(arr)
     for i in range(n//2 - 1, -1, -1):  # 从最后一个非叶子节点开始
         heapify(arr, n, i, is_max_heap)

💎 总结

操作 大顶堆实现要点 小顶堆改动点
插入(上浮) 与父节点比较，若更大则交换 与父节点比较，若更小则交换
删除(下沉) 与较大子节点比较并交换 与较小子节点比较并交换
应用场景 堆排序、Top K最小值 Top K最大值、Dijkstra算法

面试技巧：

# 面试 # python
Logo
长沙城市开发者社区

惟楚有才，于斯为盛。欢迎来到长沙！！！ 茶颜悦色、臭豆腐、CSDN和你一个都不能少~

更多推荐

cover

【保姆级选型指南】2025年国产开源AI算力平台怎么选？覆盖企业级_制造业_国际化场景

avatar 长沙城市开发者社区

Maple Mono多语言支持：简繁中日字符集兼容

在当今全球化开发环境中，开发者经常需要处理包含简体中文、繁体中文、日文和英文的混合代码。传统等宽字体往往无法完美支持这种多语言场景，导致：- 中英文字符宽度比例失调，表格对齐困难- 标点符号显示不一致，影响代码可读性- 特殊符号和连字功能在多语言环境下失效- 终端图标与中文字符兼容性问题Maple Mono字体通过创新的技术方案，彻底解决了这些痛点，为多语言开发者提供了完美的字体...

avatar 长沙城市开发者社区

Graphite直方图分析：图形色彩分布的视觉化工具

还在为图像色彩分布不均衡而烦恼？想要精确掌握图像中的色彩构成却无从下手？Graphite的直方图分析功能为你提供了一套完整的色彩分布视觉化解决方案，让你能够深入理解图像的色彩特性并进行精准的色彩调整。## 什么是直方图分析？直方图（Histogram）是数字图像处理中用于表示像素值分布的重要工具。在Graphite中，直方图分析能够：- **可视化色彩分布**：直观展示RGB各通道的像...

avatar 长沙城市开发者社区