导航
1.了解什么是堆
2.如何创建最小堆，最大堆
3.新增值在堆中如何进行
4.完整的堆排序，升序和降序(两种方式)
——————————————————————————————————————
1.了解什么是堆
树型结构与图型结构的差别：
看是否有回路，无回路的是树型，有回路的是图型
满二叉树可以用数组进行存储,层次遍历顺序存储
设置其中父节点为k，儿子节点(左结点，右节点) 其中左节点 为2*k， 右节点为 2 * k+1
高度为log2^N
其中最典型的应用就是堆(也就是完全二叉树)
完全二叉树：
——————————————————————————————————————
2.如何将堆转化为最小堆，最大堆
有两层的直接用父结点来比较
三层的应该有倒数一层的右边节点开始依次往下
代码如下：（创建最小堆）
//这里用的是数组的方式存储堆 void siftdown(int i) //输入的是从i点往下找 { int t,flag=0; //flag用来表示无需再进行往下查找 //从i位置开始，判断是否有左孩子，并且没有找到最佳位置 while(i*2<=n&&flag==0) { if(h[i]>h[i*2]) //比较父节点与左节点的大小 t = i*2; else t = i; if(i*2+1<=n){ //判断是否存在右孩子 if(h[t]>h[i*2+1]) //比较上一次父节点与左节点的最小值与右孩子大小 t = i*2+1; } if(t!=i){ //判断得到最小值是否为父节点，是的话flag标志1，不是的话交换，继续往下找 swap(t,i); i=t; } else flag = 1; } }
创建最大堆：只需要将父节点与左右孩子节点的判大小符号换一下就可以了
——————————————————————————————————————
3.新增值在堆中如何进行
先插入到堆中最后一个位置，在进行与父节点依次比对，找到最合适的位置
整个都用数组保存
代码：
//这里弄得是最小堆 void siftup(int i) { int i,flag=0; //flag等于0表示当前子节点比父节点小 if(i==1) return; //如果为根节点直接返回 while(i!=1&&flag==0) { if(h[i]<h[i/2]) swap(i,i/2); else flag=1; i=i/2; //让子节点等于父节点的位置 } }
——————————————————————————————————————
4.完整的堆排序，升序和降序
输入提示： 14 99 5 36 7 22 17 46 12 2 19 25 28 1 92 升序： #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; } void siftdown(int i) { int t,flag=0; //flag用来表示无需再进行往下查找 //从i位置开始，判断是否有左孩子，并且没有找到最佳位置 while(i*2<=n&&flag==0) { if(h[i]>h[i*2]) //比较父节点与左节点的大小 t = i*2; else t = i; if(i*2+1<=n){ //判断是否存在右孩子 if(h[t]>h[i*2+1]) //比较上一次父节点与左节点的最小值与右孩子大小 t = i*2+1; } if(t!=i){ //判断得到最小值是否为父节点，是的话flag标志1，不是的话交换，继续往下找 swap(t,i); i=t; } else flag = 1; } } void create() { int i; for(i=n/2;i>=1;i--) siftdown(i); } //用于返回最小值 int deletemax() { int t; t=h[1]; h[1]=h[n]; n--; //删除一位 siftdown(1); //进行最小堆 return t; } int main() { int i,num; scanf("%d",&num); for(i=1;i<=num;i++) scanf("%d",&h[i]); n = num; //建立最小堆 create(); //删除顶部元素，接着将最后一个元素放入第一个顶点中，输出删除的元素 for(i=1;i<=num;i++) printf("%d ",deletemax()); return 0; }
其中deletemax()函数作用是每次返回最小值，并且将最后一个值移入到根节点再次进行最小堆，这样结束时数组中数据已不再是原来的。
若想用这样的来求降序也是可以的，只需要建立最大堆就行了，其余都一样
另一种方式来求解升序和降序
//之前创建的是最大堆 void headsort() { while(n>1) { swap(1,n); //将第一个与最后一个进行交换，此时最后一个点为最大值 n--; //下次建立最大堆不带上最后一个值 siftdown(1); //进行最大堆 } }
求解升序另一种方法完整：
#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; } void siftdown(int i) { int t,flag=0; //flag用来表示无需再进行往下查找 //从i位置开始，判断是否有左孩子，并且没有找到最佳位置 while(i*2<=n&&flag==0) { if(h[i]<h[i*2]) //比较父节点与左节点的大小 t = i*2; else t = i; if(i*2+1<=n){ //判断是否存在右孩子 if(h[t]<h[i*2+1]) //比较上一次父节点与左节点的最小值与右孩子大小 t = i*2+1; } if(t!=i){ //判断得到最小值是否为父节点，是的话flag标志1，不是的话交换，继续往下找 swap(t,i); i=t; } else flag = 1; } } //开始创建堆 void create() { int i; for(i=n/2;i>=1;i--) siftdown(i); } //之前创建的是最大堆 void headsort() { while(n>1) { swap(1,n); //将第一个与最后一个进行交换，此时最后一个点为最大值 n--; //下次建立最大堆不带上最后一个值 siftdown(1); //进行最大堆 } } int main() { int i,num; scanf("%d",&num); for(i=1;i<=num;i++) scanf("%d",&h[i]); n = num; //建立最小堆 create(); headsort(); //删除顶部元素，接着将最后一个元素放入第一个顶点中，输出删除的元素 for(i=1;i<=num;i++) printf("%d ",h[i]); return 0; }
