#include <stdio.h>
#include <stdlib.h>
//交换两个位置
void swap(int a[],int pos1,int pos2)
{
a[pos1]=a[pos1]^a[pos2];
a[pos2]=a[pos1]^a[pos2];
a[pos1]=a[pos1]^a[pos2];
}
//调整start点的堆结构
void fix_max_heap(int a[],int start,int num)
{
int max_child;
//有两个节点
if((start*2+1)<=num)
{
if(a[start*2]>a[start*2+1])
{
max_child=start*2;
}
else
{
max_child=start*2+1;
}
if(a[max_child]>a[start])
{
swap(a,start,max_child);
fix_max_heap(a,max_child,num);
}
}
//有一个节点
else if((start*2==num)&&(a[start*2]>a[start]))
{
swap(a,start,start*2);
}
}
/*建立堆 */
void build_max_heap(int a[],int num)
{
if(num==0||a==NULL)
return ;
int parent=num/2; //最小父节点
//从最小父节点开始调整堆
while(parent!=0)
{
fix_max_heap(a,parent,num);
parent--;
}
}
#define N 7
int main()
{
int a[]={-1,2,45,75,34,26,100,34};
//建立大顶堆
build_max_heap(a,N);
int i;
//删除最大数,调整堆
for(i=N;i>=2;i--)
{
swap(a,1,i);
fix_max_heap(a,1,i-1);
}
for(i=1;i<=N;i++)
{
printf("%d ",a[i]);
}
printf("\n");
system("pause");
return 1;
}
分享到:
相关推荐
堆的出队,删除,插入节点(下筛法,上滤法),子树更新,节点修改,堆排序,堆的创建,销毁。
标题"堆排序C语言实现"指出我们将讨论如何用C语言来编写堆排序的代码。C语言是一种底层、高效的编程语言,适用于实现算法和数据结构。 描述"算法导论之堆排序,C语言实现版"表明这个话题是基于经典的《算法导论》这...
"C 语言算法集--超多C语言算法实现"是一个珍贵的资源库,包含了大量经典且实用的C语言实现的算法,对于学习者和开发者来说具有很高的参考价值。下面将详细探讨C语言中的关键算法类别及其重要性。 1. 排序算法:排序...
C语言实现的堆排序算法。 提供了堆排序算法的一个接口,可以为其它功能提供功能。
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 堆排序的平均时间复杂度为Ο...
### 堆排序C语言实现解析 #### 一、堆排序简介 堆排序是一种基于比较的排序算法,它利用了二叉堆的数据结构特性来进行排序。堆分为两种:最大堆和最小堆。最大堆指的是父节点总是大于或等于其子节点的堆;而最小堆...
以下是对堆排序及其C语言实现的详细解释。 ### 堆的概念与结构 1. **堆的定义**:堆是一个完全二叉树,可以分为大顶堆(父节点的值大于或等于其子节点的值)和小顶堆(父节点的值小于或等于其子节点的值)。 2. *...
堆排序算法原理及C语言实现.docx
C语言实现堆排序 #### 2.1 基本函数定义 - `output` 函数用于输出当前数组的状态,方便观察排序过程中数组的变化情况。 - `creat1` 函数用于将一个非完全二叉树转换成最大堆,通过自下而上的方式调整子树。 - `...
### c语言实现堆排序算法 堆排序是一种基于比较的排序算法,它利用了二叉堆的数据结构特性来高效地对数据进行排序。堆排序可以分为最大堆和最小堆两种,其中最大堆指的是父节点的值总是大于或等于任意一个子节点的...
c语言实现堆排序。代码实现的是建立大根堆
本文将深入探讨C语言中常见的六种排序算法:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序以及堆排序。每种排序算法都有其独特的实现方式和性能特点,适合不同的场景。 1. **起泡排序(Bubble Sort)*...
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort...选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序mergesort
8. **排序算法**:C语言中常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序。了解它们的时间复杂度和稳定性有助于优化程序性能。 9. **查找算法**:二分查找、顺序查找和二叉搜索树等都...
书中涉及到的知识点包括算法分析,列表,栈和队列,树,哈希,优先队列(堆),排序算法,离散集ADT,图算法,算法设计技术,摊还分析,以及高级数据结构和实现等。 算法分析是研究算法性能的过程,它包括时间...
- **堆排序**:构建一个大顶堆或小顶堆,然后逐步调整堆以完成排序。 接下来,我们深入到具体算法的实现: - **8.2 静态链表插入排序**:`StlinkedInsertSort`函数使用了一个静态链表结构,通过查找插入位置并...
在提供的压缩文件中,包含了用C语言实现HeapSort的源代码。通过对这段代码的学习,读者可以深入了解HeapSort的工作原理,并能动手实践,从而掌握这一重要的排序算法。通过实际编程,有助于提升对算法的理解,以及在...
二、C语言实现堆排序的步骤 1. **初始化**:创建一个数组来存储待排序的数据,并根据输入的数据构建大顶堆。 2. **建堆**:从最后一个非叶子节点(n/2-1)开始,自下而上遍历并调整,确保每个节点都满足堆的性质。...
- **堆排序**:利用堆这种数据结构所设计的一种排序算法,分为建堆和调整两个阶段。 - **归并排序**:同样基于分治法思想,将数组分成两半,递归地对每一半进行排序,然后合并结果。 ### 综合分析比较 本书不仅介绍...
在计算机科学中,排序算法是数据结构...在实际项目中,我们可能会根据具体需求选择更高效的排序算法,如快速排序、归并排序、堆排序等。然而,了解和掌握冒泡排序对于理解排序算法的基本逻辑和优化思路具有重要意义。