一、堆（Heap）核心概念

堆本质是完全二叉树，一般用数组存储，分为两种：

1、大顶堆：父节点 ≥ 左右孩子；堆顶是最大值

2、小顶堆：父节点 ≤ 左右孩子；堆顶是最小值

数组下标映射

假设数组下标从0开始：

    父节点下标：parent = (i - 1) / 2

    左孩子下标：left = i * 2 + 1

    右孩子下标：right = i * 2 + 2

如果数组下标从 1 开始：parent=i/2，left=2i，right=2i+1，写代码看习惯。

堆的两个核心操作

1、插入（上浮 shiftUp）

    1、新元素加到数组末尾

    2、和父节点比较，如果不满足堆性质，交换

    3、向上不断比较，直到满足堆性质 / 到根节点

时间复杂度 O(logn)
2. 弹出堆顶（下沉 shiftDown）

   1、把最后一个元素覆盖堆顶

   2、堆长度 - 1

   3、新堆顶和左右孩子比较，和符合条件的孩子交换

   4、向下循环，直到满足堆性质

时间复杂度 O(logn)

二、优先队列

优先队列 = 堆的封装。

普通队列：先进先出；优先队列：优先级最高的元素先出队。

C 语言标准库没有自带优先队列，需要自己手写堆；C++ 有priority_queue。

      TopK 问题最经典：在一堆数字中，找出前 K 大（或前 K 小）的数。

       技巧：找前 K 大 → 用大小为 K 的小顶堆；遍历数组，大于堆顶就入堆，最后堆里就是最大 K

个。

三、图论基础：DFS、BFS

图由顶点 + 边组成，分有向图、无向图；存储方式：邻接矩阵、邻接表（邻接表刷题更常用）。

     DFS 深度优先搜索：一路往深处走，走不通再回溯，类似二叉树前序遍历，递归实现

         重点：必须visited标记数组，防止重复访问、死循环！

     BFS 广度优先搜索：一层一层遍历，借助队列，适合求最短路径（无权图）

         重点：队列存待访问节点，同样需要 visited 数组标记