堆

#堆

• 什么是堆
• 堆的结构
• 添加数据
• 取出数据
• 时间复杂度
• 应用场景

#什么是堆

堆是一种树形结构的数据结构，用于实现优先队列——可以自由添加数据，但取出数据时总是从最小值（或最大值）开始取。

把堆想象成一个金字塔：最顶端放着最小（或最大）的元素，往下逐渐变大。

          1        ← 根结点（最小值在这里）
        /   \
       3     6
      / \   /
     4   8 7

#堆的结构

堆是一棵完全二叉树，满足以下规则：

• 每个结点最多有两个子结点
• 结点从上到下、从左到右依次排列（没有空隙）
• 子结点必定大于（或小于）父结点——这保证了最小值（或最大值）在根结点

结点的排列顺序:

  第1层:         [1]           ← 根结点
  第2层:       [3]  [6]
  第3层:     [4][8] [7]

从上到下、从左到右，没有空隙

#添加数据

往堆里添加数字 5：

第 1 步：把新数据放在最下面一排的最左空位

        1
      /   \
     3     6
    / \   / \
   4   8 7   5  ← 新数据加在这里

第 2 步：比较新数据和父结点。如果父结点更大，就交换

  5 的父结点是 6，6 > 5 → 交换

        1
      /   \
     3     5    ← 5 上移
    / \   / \
   4   8 7   6  ← 6 下移

第 3 步：继续与新的父结点比较。5 的父结点是 1，1 < 5，符合规则，停止。

这个过程叫向上调整（sift up）。

#取出数据

取出数据时，总是取根结点（最小值）。取出后需要重新调整堆。

第 1 步：取出根结点 1

        _        ← 1 被取走了
      /   \
     3     5
    / \   / \
   4   8 7   6

第 2 步：把最后一个结点（6）移到根位置

        6        ← 最后的元素移到顶部
      /   \
     3     5
    / \   /
   4   8 7

第 3 步：比较根结点和子结点，与较小的子结点交换

  6 的子结点是 3 和 5，3 更小，3 < 6 → 交换

        3
      /   \
     6     5
    / \   /
   4   8 7

第 4 步：继续向下比较。6 的子结点是 4 和 8，4 更小，4 < 6 → 交换

        3
      /   \
     4     5
    / \   /
   6   8 7

6 已经是叶子结点，调整完成。这个过程叫向下调整（sift down）。

#时间复杂度

操作	时间复杂度	说明
取出最小值	O(1)	直接取根结点
取出后重构堆	O(log n)	向下调整，最多走树的高度
添加数据	O(log n)	向上调整，最多走树的高度

堆的高度为 log₂n，所以添加和删除的时间复杂度都是 O(log n)。

#应用场景

• 优先队列：任务调度中按优先级取出任务
• 狄克斯特拉算法：每一步从候补顶点中选择距离最近的顶点
• 堆排序：利用堆进行排序，时间复杂度 O(n log n)
• Top K 问题：从海量数据中找出前 K 大（或前 K 小）的元素
• 合并有序流：合并多个有序数据流时用堆高效取最小值

#小结

• 堆是棵完全二叉树，子结点总是大于（或小于）父结点
• 最小值（或最大值）始终在根结点，取出的时间复杂度为 O(1)
• 添加和删除（含重构）的时间复杂度为 O(log n)
• 主要用于实现优先队列，凡是需要「频繁取最值」的场景都适合用堆