堆是一颗完全二叉树,他的根节点大于或小于他的子节点(大根堆)(小根堆)
以数组heap方式存储的结构顺序就是二叉树的层序遍历顺序
创建堆有两种方式,一种是插入式的(也就是边插入边调整的),另一种是先在heap中存储数据然后调整的(先存储后调整)
方式1 下面以大根堆为例开始讲解
方式一的插入方式是在这个堆(二叉树)的最后插入一个结点,然后向上调整
向上调整的代码
1 | void upAdjust(int low,int high) |
插入
1 | void insert(int x) |
方式2
先存储,后调整
存储就是把他放在heap数组里面,没什么好说的
调整
从非叶子(1~n/2)结点从下往根部开始调整,可以节省时间。对于每个需要调整的结点,我们都需要把他往下调整
1 | void creatHeap() |
向下调整
1 | void downAdjust(int low,int high) |
删除根节点
删除根节点只需要找一个结点覆盖他就可以了,一般都用最后一个结点来覆盖他
1 | void deleteTop() |
堆排序
由于大根堆大的始终在上面的性质,所以上面出现的始终时最大的,我们讲最大的移动到最后面,然后对(1~n-1)进行调整,就又能找出最大的结点
1 | void heapSort() |
相关代码
1 | #include <iostream> |
本文作者: jiangyuhao
本文链接: http://example.com/2022/06/12/%E5%A0%86/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!