第8课:大根堆与小根堆
进度 0/24
⚖️
大根堆与小根堆
堆顶永远站着冠军,一眼锁定最值!
📖知识引入
⬆️大根堆
每个父节点都不小于孩子,堆顶是全场最大值
⬇️小根堆
每个父节点都不大于孩子,堆顶是全场最小值
🏆O(1)拿最值
不管堆里有多少元素,看一眼堆顶就是最值
🎯应用场景
TOP-K问题、优先级调度、动态求最值,到处都有它
💡
记住大根堆是“大的往上冒”,小根堆恰好相反——先想清楚要最大还是最小再动手
🔍判断是不是大根堆
bool isMaxHeap(int h[], int n) {
for (int i = 1; i <= n; i++) {
int l = 2 * i, r = 2 * i + 1;
if (l <= n && h[l] > h[i]) return false; // 左孩子更大,违规
if (r <= n && h[r] > h[i]) return false; // 右孩子更大,违规
}
return true; // 所有父亲都镇得住孩子
}逐个检查每个父亲是否都不小于自己的孩子。
🎯小测验
第1题:大根堆的堆顶是什么?
第2题:小根堆中父与子的大小关系是?
第3题:查看堆顶最值的时间复杂度是?
📝本课知识点
- ✓大根堆堆顶最大
- ✓小根堆堆顶最小
- ✓取最值只要O(1)
第8课完成!继续探索下一课吧 🚀
