【数据结构-二叉树】堆(Heap)
2023-02-19 12:20:36 时间
堆是属于数据结构树的一个分支,它其实就是一颗二叉树,堆分有大顶堆和小顶堆
大顶堆:父节点的值永远大于子结点
小顶堆:父节点的值永远小于子结点
在堆中插入元素,我们一般在尾部插入,然后又个上浮操作(以大根堆为操作)
来个动态图
http://www.wzl1.top/wp-content/uploads/2022/02/e085fb0010a45e0758a384a074593cb1.mp4
那取出头节点就不说了,主要来说说删除头节点
得有个下浮的过程,我们一般会把头节点复制一份放在堆的后面一位(堆排序有用),然后对左右子结点进行操作,然后再进行操作,一直把头节点移到最后,然后堆的长度减一
堆排序就是每次对堆进行pop操作,然后这时候相当于每次都是把最大(最小)值给放到了最后(堆顶一定最大)
下面是源代码:
//https://blog.csdn.net/gsjwxhn/article/details/103051851
#include <bits/stdc++.h>
using namespace std;
template<typename T>
class Tree{
private:
T *data=NULL;
int count=0;//当前树的长度
int length=0;//表示堆的最大容量
public:
Tree(int length){
data = new T[length+1];
this->length = length+1;
}
void print(){
for (int i = 1; i < length; ++i) {
cout<<this->data[i]<<" ";
}
}
void set_Data(T *data){
this->data = data;
}
void Insert(T data){
this->data[++count]=data;
percolate_up(count);//上浮
}
void percolate_up(int cnt){
while(cnt>1 && data[cnt]>data[cnt/2]){
swap(data[cnt],data[cnt/2]);
cnt/=2;
}
}
T pop_Head(){
T data =this->data[1];
swap(this->data[1],this->data[count--]);
percolate_Down(1);//下浮
return data;
}
void percolate_Down(int cnt){
//count是当前结点个数4
//cnt=2
while(cnt*2<=count){
int j=cnt*2;
if(j+1<=count&&data[j]<data[j+1])j++;
if(data[cnt]>data[j])break;
swap(data[cnt],data[j]);
cnt=j;
}
count--;
}
};
int main(){
Tree<int> Heap =Tree<int>(10);
// 9 2 5 1 7 8 3 6 4 10
for (int i = 0; i < 10; ++i) {
int k;
cin>>k;
Heap.Insert(k);
}
Heap.print();
cout<<endl;
//下面是堆排序的操作
Heap.pop_Head();
Heap.pop_Head();
Heap.pop_Head();
Heap.pop_Head();
Heap.pop_Head();
Heap.pop_Head();
Heap.pop_Head();
Heap.pop_Head();
Heap.pop_Head();
Heap.pop_Head();
Heap.print();
return 0;
}
相关文章
- 前端后端都可以用的精美Json数据查看神器
- Pandas处理数据太慢,来试试Polars吧!
- 如果后端API一次返回10万条数据,前端应该如何处理?
- 一行Pandas代码制作数据分析透视表,太牛了!
- 云卷云舒:2022 数据库总结从Gartner到IDC
- 大道至简:数据库的终极未来
- Pandas 实用技能,数据筛选 query 函数详细介绍
- 歌神影帝:搞过数据库的人,职业宽度超乎你的想象
- 三个用于时间序列数据整理的Pandas函数
- 软件测试|Yaml实现测试数据驱动
- 如何构建高性能可视化架构?一个交互式实时数据引擎的架构设计
- MySQL8.0默认加密连接方式
- 自动增量计算:构建高性能数据分析系统的任务编排
- 面试官:如果要存ip地址,用什么数据类型比较好
- Pandas与SQL的超强结合,爆赞!
- MongoDB数据的导出导入及日志分析
- 严选交易数据源独立切换实践
- 邮件安全:从 安全网关 到 基于图建模的数据运营
- 简单的六种防止数据重复提交的方法!
- 迪塔维王珂:聚焦数据治理,助力高校信息化高质量建设 | 镁客·请讲