当前位置:   article > 正文

堆排序——c语言实现_堆排序c语言

堆排序c语言

堆的概念

堆的定义

可以定义为一颗二叉树,树的节点包含键(每个节点一个键),并且满足下面两个条件:

  1. 堆的形状要求是一颗完全二叉树,意识就是说,树的每一层都是满的,除了最后一层最右边的元素可能有缺位
  2. 父母优势要求,就是说每一个节点的键都要大于或等于它子女的键。

堆的判断

下面这个就不是堆,因为不是完全二叉树
在这里插入图片描述
下面这个也不是堆,堆的节点比子节点大,4比5小
在这里插入图片描述
下面这个是堆
在这里插入图片描述

堆的特性

在这里插入图片描述

  1. 一颗n个节点的完全二叉树。它的高度是:[log2n](log以2为底,[]表示向下取整)
  2. 堆的根总是包含堆的最大元素
  3. 堆的一个节点以及该节点的子孙也是一个堆
  4. 可以用数组来实现堆,方法是从上到下,从左到右的方式来记录堆的元素,当有n个元素时,存放在数组的1~n的位置上。此时有:
    a 父母节点会在位于数组的前n/2个位置中,而叶子节点将会在占据后n/2个位置
    b 在数组中,当父母位置为i时,则子女节点会在2i和2i+1。对于一个位于i的键来说,它的父母节点位于i/2。

堆的构造

构造堆有两种方法,一种是自底向上堆构造;另一种是自定向下堆构造。

自底向上构造

对于堆来说,每一个父母节点的值都要大于子女节点。所以从最后一个父母节点开始,一直到根节点,判断子女节点是否比父母节点的值小,如果大,则将交换父母节点和子女节点的值。
以2,9,7,6,5,8为例:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

自顶向下构造

自顶向下堆构造算法的效率低,就是通过把新的键连续插入预先构造好的堆,然后将其值与父母进行比较直至根节点或值小于父母节点时,来构造一个新堆。
比如在下面的堆中插入9:
在这里插入图片描述
在这里插入图片描述

关于最大堆,最小堆

最大堆就是父节点比子节点大,最小堆就是父母节点比子节点小。

堆排序

堆排序的一般过程

这里以

  1. 构造堆,堆给定的数组构造堆
  2. 删除最大键,将最大值和最后一个叶子结点进行交换,然后删除
  3. 将删除后重新整合,使之成为一个堆,重复2

堆排序样例过程图解

以2,9,7,6,5,8为例
在这里插入图片描述
在这里插入图片描述

c语言代码

#include <stdio.h>
int num;
void BuildHeap(int A[],int i,int N)	//构造堆  
{
	int c,temp;
    for (temp=A[i];2*i<=N;i=c)	//temp记录下父母节点的值,c为一个子女节点 
	{
        c=2*i;				
        if(c<N&& A[c+1]>A[c])//找到最大的子女节点 
            ++c;              
        if(temp<A[c])		//父母节点值等于子女节点中大的 
            A[i]=A[c];		
        else
            break;					
    }
    A[i]=temp;//对被交换的子女节点赋值 比如在2 9 8 6 5 7中9和2交换后,2需要和6再进行交换,最后只需要对6最开始的位置赋值2就行 
}
void Heapsort(int a[])	//排序 
	{
		int i,temp;
		for(i=num/2;i>=1;i--)	//从最后一个父母节点开始,知道根节点 
			{
				BuildHeap(a,i,num);
			}
		for(i=num;i>0;i--)	//删除根节点后,重新构造堆 
			{
				temp=a[1];
				a[1]=a[i];
				a[i]=temp;
				BuildHeap(a,1,i-1);
			}
	}
int main()
{
	printf("请输入要排序的数的个数:"); 
	scanf("%d",&num);
	int i,a[num+1];
	printf("请输入元素:");
	for(i=1;i<=num;i++)
		scanf("%d",&a[i]);
	Heapsort(a);
	for(i=1;i<=num;i++)
		printf("%d ",a[i]);
 } 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

在这里插入图片描述
参考书籍:算法设计与分析基础

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/615353
推荐阅读
相关标签
  

闽ICP备14008679号