C语言数据结构堆排序顺序存储（升序）_网络技术

C语言数据结构堆排序顺序存储（升序）

发布时间 - 2026-01-11 01:13:43 点击率：次

堆排序顺序存储（升序）

一：完全二叉树的概念：前h-1层为满二叉树，最后一层连续缺失右结点！

二：首先堆是一棵全完二叉树：

a:构建一个堆分为两步：⑴创建一棵完全二叉树 ⑵调整为一个堆

（标注：大根堆为升序，小根堆为降序）

b:算法描述：①创建一棵完全二叉树

②while(有双亲){
A:调整为大根堆；
B:交换根和叶子结点；
C:砍掉叶子结点；
}

c:时间复杂度为 O(nlogn) ,空间复杂度为 O(1), 是不稳定排序！

代码实现：

/*堆排序思想:[完全二叉树的定义:前 h-1 层为满二叉树一最后一层连续缺失右结点(即右子女)]，(大根堆升序排序，小根堆降序排列) 
  首先堆是一个完全二叉树 ，根据数组下标就可建成了一棵完全二叉树 
  其次:while(有双亲){ 
    A: 调整为一个大根堆         【Adjust()函数实现】 
    B: 交换最后一个叶子结点和根结点    【Swap()函数实现】 
    C: 砍掉最后一个叶子结点      【即元素个数 n--】 
  } 
*/ 
 
#include <iostream> 
#define N 100 
 
using namespace std;  
 
int b[N]={0};    //存储数据的数组  
int n=0;      //记录数据的总个数【0单元不要,实际元素个数为(n-1)个】 
 
void Swap(int *x,int *y){ 
  int t; 
  t=*x; 
  *x=*y; 
  *y=t; 
}  
 
void Adjust(){ 
  int p;         //记录双亲结点  
  int tag=1;       //记录是否已经调整为大根堆(标志性的变量) 
  while(tag){       //判断是否已经调整好为大根堆 
    p=(n-1)/2;     //最后一个双亲结点的下标 
    tag=0;       //凡是交换后，tag=1,标志着还没有调整为大根堆，否则继续调整  
    while(p>0){     //确保有双亲结点 
      if(b[p]<b[2*p]){     //若根结点大于左子女结点，就交换  
        Swap(&b[p],&b[2*p]); 
        tag=1; 
      } 
      if(2*p+1<n && b[p]<b[2*p+1]){ //若存在右子女，并且根结点大于右子女结点，就交换  
        Swap(&b[p],&b[2*p+1]); 
        tag=1;      
      } 
      p--;        //直到最后一个双亲结点调整完  
    }  
  }  
} 
 
void HeapSort(){ 
  while(n>2){         //保证有双亲结点  
    Adjust();        //调整大根堆函数 
    Swap(&b[1],&b[n-1]);  //将最后一个叶子结点和根结点交换  
    n--;          //裁剪最后的叶子结点  
  } 
}   
    
int main(void){ 
  int i,m; 
  cout<<"请输入数据的总数【0单元不要,实际元素个数为(n-1)个】:"<<endl; 
  cin>>n; 
  m=n; 
  cout<<"请输入各个数据【0单元不要,实际元素个数为(n-1)个】:"<<endl; 
  b[0]=0; 
  for(i=1;i<n;i++){ 
    cin>>b[i]; 
  } 
  HeapSort();           //堆排序 
  cout<<"大根堆升序排列为:"<<endl; 
  for(i=1;i<m;i++){ 
    cout<<b[i]<<" "; 
  }  
  cout<<endl; 
  return 0; 
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

# C语言 # 数据结构堆排序顺序存储 # 堆排序 # C语言数据结构中堆排序的分析总结 # C语言数据结构之堆排序详解 # C语言数据结构之堆排序源代码 # C语言实现堆排序的简单实例 # C语言对堆排序一个算法思路和实现代码 # C语言植物大战数据结构堆排序图文示例 # 二叉树 # 升序 # 一棵 # 为大 # 数为 # 请输入 # 是一个 # 还没有 # 降序 # 希望能 # 就可 # 谢谢大家 # 不稳定 # 标志着 # 两步 # 判断是否 # 构建一个 # brush # class # nlogn

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：TensorFlow模型导出常见错误解析与正确保存方法

下一篇：ubuntu安装mmdetection

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：TensorFlow模型导出常见错误解析与正确保存方法

下一篇：ubuntu安装mmdetection

C语言 数据结构堆排序顺序存储（升序）

C语言数据结构堆排序顺序存储（升序）