堆是如何插入一个元素的？什么是「上浮」？

简化版

插入分两步：先把新元素加到数组末尾（保持完全二叉树结构），再让它上浮（sift up）——不断和父节点比较，如果违反堆序（大顶堆里比父大 / 小顶堆里比父小）就和父交换，一直浮到「不再违反」或「到达堆顶」为止。因为只沿着一条到根的路径走，上浮最多 O(log n)。

详细版

以大顶堆为例：

void insert(int[] heap, int val) {   // 假设 heap 用 size 记录当前元素数
    heap[size] = val;                // 1. 放到末尾
    int i = size++;
    // 2. 上浮
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] <= heap[parent]) break;   // 满足堆序（父≥子），停止
        swap(heap, i, parent);                // 比父大，交换上浮
        i = parent;
    }
}

放末尾：完全二叉树的下一个空位就是数组末尾，保证结构不被破坏。
上浮：新元素可能比祖先大，需要一路和父比较、交换，直到就位。
小顶堆只需把比较方向反过来（比父小才上浮）。

完整版教学

一、为什么先放末尾

堆必须始终是完全二叉树。完全二叉树「下一个可插入的位置」永远是「最后一层最右边的下一个」，也就是数组的末尾。所以新元素只能先放数组末尾——这样结构性（完全二叉树）不会被破坏。但放末尾后，它可能违反堆序（比某些祖先大），所以要接着调整。

二、上浮：把「太大的」往上送

新元素放末尾后，只可能和它的祖先违反堆序（它的子树是空的，不会和孩子冲突）。上浮就是逐级修正：

和父节点比较。
大顶堆里，如果它比父大（违反「父 ≥ 子」），就和父交换，自己上升一层。
重复，直到「不再比父大」或「已经到根」。

因为每次只和父比较、上升一层，走的是一条从插入点到根的路径，最多树高 log n 步。

三、走一个例子

大顶堆 [9,7,8,3,5] 插入 10：
1) 放末尾: [9,7,8,3,5,10]，新元素 10 在下标 5
2) 上浮:
   父 = (5-1)/2 = 2，heap[2]=8，10>8 → 交换 → [9,7,10,3,5,8]，i=2
   父 = (2-1)/2 = 0，heap[0]=9，10>9 → 交换 → [10,7,9,3,5,8]，i=0
   到根，停止
结果堆顶变成 10 ✓

四、复杂度

时间 O(log n)：上浮最多走一条到根的路径，长度 = 树高 = log n。
空间 O(1)：原地交换，只用常数额外空间。

插入 n 个元素逐个 insert 建堆是 O(n log n)——注意这比「自底向上建堆 O(n)」慢，是两种建堆方式的区别（见建堆专题）。

五、易错点

比较方向别搞反：大顶堆「比父大才上浮」，小顶堆「比父小才上浮」。
停止条件：一旦满足堆序（不比父大/小）就要 break，不能一直交换到根。
先更新 size 再操作要对齐：新元素下标是旧的 size，放完再自增。

六、常见误区与追问

考点	正确口径
插入位置	先放数组末尾以保持完全二叉树
调整方向	和父节点比较，必要时上浮
停止条件	到根或父节点已经满足堆序

add x at index i
while i > 0 and heap[i] > heap[parent(i)]:
  swap(i, parent(i))
  i = parent(i)

插入堆时先保形状，再修堆序；上浮只会沿父链一路向上。

误区：新元素应该直接插到合适的中间位置。 堆的形状要求完全二叉树，只能先追加到末尾，再通过上浮调整。
误区：上浮要和两个孩子比较。 新节点从下往上走，破坏的只可能是它和父节点之间的堆序。
误区：上浮会影响整棵树。 每次只交换父子节点，其他子树本来满足堆序，调整路径是一条根到叶路径。
追问：最坏上浮多少次？ 最多从叶子到根，次数等于树高 O(log n)。
追问：插入相等元素怎么处理？ 可不交换相等元素以减少操作；堆本身不保证稳定性。
追问：小顶堆如何改？ 比较方向反过来，当前节点小于父节点时上浮。

七、加强记忆

堆插入两步：放数组末尾（保持完全二叉树结构）→ 上浮（siftUp）：和父比较，大顶堆比父大（小顶堆比父小）就交换上升，直到满足堆序或到根。只沿一条到根的路径走，O(log n)、原地 O(1)。注意比较方向别反、满足堆序即停。逐个插入建堆是 O(n log n)，慢于自底向上 heapify。

简化版

详细版