第9课：堆的插入与删除
进度 0/24
🔄
堆的插入与删除
上浮下沉，秩序井然，离信奥更近一步！
📖知识引入
⬆️插入与上浮
新元素先放到数组末尾，和父亲比大小，该升就一路换上去
⬇️删除与下沉
堆顶出堆后末尾元素补位，和较大的孩子比较往下沉
⏱️O(log n)
上浮下沉最多走一条从底到顶的路径，步数就是树高
⚠️边界提醒
下沉前先判断孩子是否存在，别和空气交换
💡
删除堆顶用最后一个元素补位而不是直接删，是为了保住完全二叉树的形状
🔍手写push与pop
void push(int v) { // 插入：放末尾，向上浮
heap[++n] = v;
int i = n;
while (i > 1 && heap[i] > heap[i / 2]) { // 大根堆
swap(heap[i], heap[i / 2]);
i /= 2;
}
}
void pop() { // 删除堆顶：末尾补位，向下沉
heap[1] = heap[n--];
int i = 1;
while (2 * i <= n) {
int son = 2 * i; // 先选左孩子
if (son + 1 <= n && heap[son + 1] > heap[son]) son++; // 换更大的
if (heap[i] >= heap[son]) break;
swap(heap[i], heap[son]);
i = son;
}
}插入往上浮、删除往下沉，一套代码撑起整个堆。
🎯小测验
第1题：堆插入新元素时先放在哪里？
第2题：大根堆下沉时要和哪个孩子交换？
第3题：堆插入和删除的时间复杂度是？
📝本课知识点
- ✓插入=末尾上浮
- ✓删除=堆顶下沉
- ✓两者都是O(log n)
第9课完成！继续探索下一课吧 🚀