堆是一种完全二叉树, 只是是用数组的形式表示二叉树而已
它其实是利用完全二叉树的结构来维护一组数据
例如这样一棵完全二叉树:
它用堆的形式表现就是这样的:
当然, 一般的堆每个元素都是数字呢(不然小根堆与大根堆就没办法实现了呢)
大根堆与小根堆
顾名思义, 大根堆 / 小根堆就是保证根节点是所有数据中最大 / 小, 并且尽力让小的节点在上方
例如下面这个二叉树就是一个小根堆呢
(借鉴某书图片)
那如何将任意一个堆调整至大根堆 / 小根堆呢?
从上向下调整
让当前结点与它的左右孩子进行比较, 哪个比较小就和它交换, 更新询问节点的下标为被交换的孩子节点下标, 否则退出.
- void heapdown(int i) // 传入一个需要向下调整的结点编号 i
- {
- int t,flag=0;//flag 用来标记是否需要继续向下调整
- // 当 i 结点有儿子的时候 (其实是至少有左儿子的情况下) 并且有需要继续调整的时候循环需执行
- while(i*2<=n&&flag==0)
- {
- // 首先判断他和他左儿子的关系, 并用 t 记录值较小的结点编号
- if(h[i]>h[i*2])
- t=i*2;
- else t=i;
- // 如果他有右儿子的情况下, 再对右儿子进行讨论
- if(i*2+1<=n)
- {
- // 如果右儿子的值更小, 更新较小的结点编号
- if(h[t]>h[ i*2+1])
- t=i*2+1;
- }
- // 如果发现最小的结点编号不是自己, 说明子结点中有比父结点更小的
- if(t!=i)
- {
- swap(t,i);
- i=t;// 更新 i 为刚才与它交换的儿子结点的编号, 便于接下来继续向下调整
- }
- else flag=1;// 则否说明当前的父结点已经比两个子结点都要小了, 不需要在进行调整了
- }
- return;
- }
从下向上调整
让当前结点和它的父亲节点比较, 若比父亲节点小就交换, 然后将当前询问的节点下标更新为原父亲节点下标, 否则退出.
- void heapup(int i) // 传入一个需要向上调整的结点编号 i
- {
- int flag=0; // 用来标记是否需要继续向上调整
- if(i==1) return; // 如果是堆顶, 就返回, 不需要调整了
- while(i!=1&&flag==0)
- {
- // 判断是否比父结点的小
- if(h[i]<h[i/2])
- swap(i,i/2);// 交换他和他爸爸的位置
- else flag=1;// 表示已经不需要调整了, 当前结点的值比父结点的值要大
- i=i/2; // 这句话很重要, 更新编号 i 为它父结点的编号, 从而便于下一次继续向上调整
- }
- return;
- }
优先队列
优先队列其实是在普通队列的基础上增加了每个元素的优先性(值)
众所周知, 普通队列是遵循元素先进先出的原则, 进队只能从前面进, 出队只能出最后一个
而优先队列不再遵循先入先出的原则, 而是分为两种情况:
最大优先队列, 无论入队顺序, 当前最大的元素优先出队.
最小优先队列, 无论入队顺序, 当前最小的元素优先出队.
例如说下面的这个优先队列出队就需要出 8 这个元素
但这种算法的时间复杂度并不理想
如果只用线性数据结构的话, 入队和出队的时间复杂度都是 O(n)
但我们如果通过二叉堆的方式, 每次上浮最大的或最小的
这时出队和入队操作都只需要 O(logn)的时间复杂度了
但从来不用 STL 的本蒟蒻只能用结构体而不会 queue 的操作 QAQ
来源: http://www.bubuko.com/infodetail-2945322.html