🐵指尖猴全新升级
第8课:大根堆与小根堆
⚖️

大根堆与小根堆

堆顶永远站着冠军,一眼锁定最值!

📖知识引入

⬆️大根堆
每个父节点都不小于孩子,堆顶是全场最大值
⬇️小根堆
每个父节点都不大于孩子,堆顶是全场最小值
🏆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课完成!继续探索下一课吧 🚀