第7课：堆的概念
进度 0/24
⛰️
堆的概念
把完全二叉树压进数组里，妙不可言！
📖知识引入
⛰️堆是什么
一棵完全二叉树，父节点和孩子之间的大小关系有严格约定
📦数组存堆
从1号位开始存，不用指针，下标公式直接算出亲戚关系
🔗下标公式
节点i的左孩子是2i，右孩子是2i+1，父亲是i/2
⚡天生高效
插入删除只沿一条路径走，最多log n步，快得惊人
💡
堆必须是完全二叉树——中间不许留空位，否则下标公式就全部失灵了
🔍堆的亲戚下标计算
int heap[10005], n = 0; // heap[1] 开始存堆，n 是元素个数
int parent(int i) { return i / 2; } // i 的父亲
int leftChild(int i) { return 2 * i; } // i 的左孩子
int rightChild(int i) { return 2 * i + 1; } // i 的右孩子
// 例：节点 2 的父亲是 1，左孩子是 4，右孩子是 5
// 靠的就是完全二叉树层层排满、绝无空位完全二叉树没有空位，父亲孩子的位置全靠下标公式。
🎯小测验
第1题：堆必须是什么样的二叉树？
第2题：数组存堆时，节点i的左孩子下标是？
第3题：下标为5的节点，它的父亲下标是？
📝本课知识点
- ✓堆=完全二叉树+大小约定
- ✓左孩子2i右孩子2i+1
- ✓父亲下标是i/2
第7课完成！继续探索下一课吧 🚀