什么是堆以及堆排序原理

1.什么是堆？

答：堆是一种特殊的完全二叉树

问：什么是完全二叉树？

答：完全二叉树是二叉树的一种

问：什么是二叉树？

答：二叉树是树的一种

问：什么是树？

答：enmmmm，下面让我们来简单从头捋一遍，最后就知道什么是堆，以及堆排序是如何实现的了

1. 树：树是不包含回路的连通无向图（任意的两个节点仅有唯一的一条路径连通，在一棵树中加一条边会构成图）
2. 二叉树：是一种特殊的树，只要不为空，就由根节点、左子树和右子树组成，左子树和右子树分别是一棵二叉树
3. 完全二叉树：完全二叉树和满二叉树都是一种特殊的二叉树，两者可以一起记，如下图，左边为满二叉树：每个分支节点都有左子树和右子树，所有叶子都在同一层上。右边为完全二叉树，是从右向左减少叶子节点的满二叉树

    4.堆的结构

大顶堆：所有父节点都比子节点大

小顶堆：所有父节点都比子节点小

                                     大顶堆                                                                                   小顶堆

     5.堆的存储

那么堆是如何存储在顺序表中的呢？如下图，是从上到下，从左到右依次编号：

如果它的父节点编号为k，那么它的左儿子编号为2*k，右儿子编号就是2k+1

如果它的儿子编号为x，那么它的父节点编号为x/2

 

2.堆的建立和堆排序：

这个是一个小顶堆，若删除最小的数，插入一个新数80，则用70替换最小堆的堆顶位置10，由于不符合最小堆特性，然后做调整

80先和它的两个儿子20和70比较，80大于两个儿子且20是较小的儿子，所以两者交换，保证交换上去的父节点是比两个儿子小的，80再和现在的两个儿子30和50比较，依然和选择和30做交换，最后和两个儿子60,40比较，最后和40做交换。先插入的数80最后找到了自己的位置

1.当需要调整的数字下标i为1时，这时候需要向下调整，向下调整的代码如下：

//1.判断有无左儿子，2*i<n?进入循环，找到最小节点的下标： 
//2.判断大小,和左儿子i*2比较，和右儿子i*2+1比较
//3.判断有无变换，如果向下调整了，就继续while循环，向下一个左右儿子比较，如果没有调整就说明在合适位置了 
void siftdown(int i)//i为传入的向下调整位置的节点编号，若i=1，则从根节点开始调整 
{
	int t,flag=0;//t为比待调整的数要小的最小值下标 
	while(i*2<n&&flag==0)//flag?
	{
		//判断和左儿子的大小 
		if(h[i]>h[i*2])
		{
			t=i*2;
		}
		else{
			t=i;
		}
		//如果右儿子的值更小，就把右儿子的下标更新为最小值下标 
		if(i*2+1<n&&flag==0)
		{
			if(h[t]>h[i*2+1])
			{
				t=i*2+1;
			}
		 }
		 if(t!=i)        //比较完和左儿子、右儿子的大小后，如果发现比儿子大，就交换 
		 {
		 	swap(i,t);
		  } 
		 if(t==i)
		 {
		 	flag=1;     //如果比左右儿子都小，就停止循环，已经找到合适位置 
		  } 
		
	 } 
 } 

 时间复杂度分析：

可以看出，如果用扫描法排序，那么有9个数就要循环9次，在对80进行调整的时候，扫描法的复杂度也是O(N)，而用对排序的向下调整仅仅进行了3次比较，如果是1亿的数据，扫描法的插入数据到有序需要1亿次，而堆排序只需要O(logN)次，即27次！

for(int i=1;i<=9;i++)

{
    if(a[i]<min)
    {
        min=a[i];

    }

}

 

2.如果想要增加一个值，如何在原有的堆上插入一个新元素呢？只需要将元素插入到末尾，再根据情况判断是否向上移，比如传入一个需要向上调整的下标为i的数时，向上调整的代码如下：

 void siftup(int i)
 {
 	int t,flag=0;//i时传入的待调整的数字的下标，flag用来标记是否需要继续向上调整 
 	while(flag==0)
 	{
 		//判断是否比父节点小 
 		if(h[i]<h[i/2])
 		{
 			swap(i,i/2);//如果比父节点小，就和父节点交换位置 
		 }
		 else
		 {
		 	flag=1;//已经不需要调整了 
		 }
		i=i/2;//更新编号i为它父节点编号，以便下一次循环从父节点开始往上比较 
	 }
 	
 }

3.堆的建立是在数的上调下调等操作的基础上建立的，有两种建堆的方式

    （1）一边插入数据一边比较调整建堆，因为插入第i个元素所用时间是O(log i)，所以插入所有元素的整体时间复杂度为                         O(NlogN)，代码如下

n=0;
for(i=1;i<=m;i++)
{
    n++;
    h[n]=a[i];
    siftup(n);
}

 

      （2）先将数据按编号顺序插入到完全二叉树中，然后根据二叉树的快速的比较排序特性完成有序，速度更快

  //建立堆的函数
  void create()
  {
  	int i;
  	//从最后一个非叶节点到第1个节点，依次向下调整以找到每个数自己合适的位置
	  for(i=n/2;i>=1;i--)
	  {
	  	siftdown(i);
	   } 
	   return;
   } 

完整代码

#include<stdio.h>
int h[101];//用来存放堆的数组
int n;//用来存储堆中元素的个数，也就是堆的大小
//交换函数 
void swap(int x,int y)
{
	int t;
	t=h[x];
	h[x]=h[y];
	h[y]=t;
	return;
}
//向下调整的函数
void siftdown(int i)//i为传入的向下调整位置的节点编号，若i=1，则从根节点开始调整 
{
	int t,flag=0;//t为比待调整的数要小的最小值下标 
	while(i*2<n&&flag==0)//flag?
	{
		//判断和左儿子的大小 
		if(h[i]>h[i*2])
		{
			t=i*2;
		}
		else{
			t=i;
		}
		//如果右儿子的值更小，就把右儿子的下标更新为最小值下标 
		if(i*2+1<n&&flag==0)
		{
			if(h[t]>h[i*2+1])
			{
				t=i*2+1;
			}
		 }
		 if(t!=i)        //比较完和左儿子、右儿子的大小后，如果发现比儿子大，就交换 
		 {
		 	swap(i,t);
		  } 
		 if(t==i)
		 {
		 	flag=1;     //如果比左右儿子都小，就停止循环，已经找到合适位置 
		  } 
		
	 } 
 } 
 //建立堆的函数
void create()
{
   int i;
//从最后一个非叶节点到第1个节点，依次向下调整以找到每个数自己合适的位置
  for(i=n/2;i>=1;i--)
  {
  	siftdown(i);
   } 
   return;
}  

//堆排序
void heapsort()
{
	while(n>1)
	{
		swap(1,n);
		n--;
		siftdown(1);
	}
	return;
 } 
 int main()
 {
 	int i,num;
 	scanf("%d",&num);
 	for(i=1; i<=num; i++)
 	{
 		scanf("%d",&h[i]);
	 }
	 n=num;
	 
	 //建堆
	 heapsort();
	 
	 //输出
	 for(i=1;i<=num;i++)
	 {
	 	printf("%d",h[i]);
	  } 
	  getchar();
	  getchar();
	  return 0;
 }

 

摘自《啊哈！算法》《大话数据结构》