文章目录
堆排序 一、 堆二、基本思想三、代码实现
1.`heapify`:2.`build_heap`:从中间的结点开始向上依次堆化3.`heap_sort`: 完整代码如下:
一、 堆
堆要满足两个条件:
1.是一个完全二叉树
2.堆中某个节点的值总是不大于或不小于其父节点的值
什么是父节点子节点呢?看下图二叉树:
大顶堆(大根堆):每个父结点的值都大于等于其子节点的值,左边的子节点可以形象称为左孩子,右边的子节点则为右孩子
小顶堆(小根堆):每个父结点的值都小于等于其子节点的值
二、基本思想
由于堆的连续存储方式,可以采用数组来进行进行存储,将堆中的数字按照一定顺序存入数组中,例如上图中的大顶堆,可以存储如下:
以大顶堆为例,堆排序的基本思路是
1.首先将待排序的数构造为一个大顶堆,那么整个数组的最大值就是堆结构的顶端
2.将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1
3.将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,反复这个过程,就可与完成排序
三、代码实现用 i 表示数组下标,n代表待排序的数字个数,c1、c2为左孩子与右孩子,可以下列公式来寻找第i个节点的父节点与子节点
先将待排序的数字写成树的结构,此时树上的数字并不满足父节点大于或等于其子节点,因此要进行堆化(heapify)
从一个结点出发,将它与左孩子右孩子比较,选择三者中中的最大值作为新的父节点,反复该过程直到成为一个大顶堆
int heapify(int tree[10000],int n,int i) { if(i>=n)//i表示数组下标,n代表待排序的数字个数 { return ; } int c1,c2,max;//c1,c2为两个子节点 c1=2*i+1; c2=2*i+2; max=i; if(c1tree[max]) {max=c1;} if(c2 tree[max]) {max=c2;} if(max!=i) { swap(tree,max,i);//为了方便写一个swap函数,详情见(1) heapify(tree,n,max); } }
(1)swap交换函数
int swap(int arr[10000],int i,int j) { int t; t=arr[i]; arr[i]=arr[j]; arr[j]=t; }2.build_heap:从中间的结点开始向上依次堆化
int build_heap(int tree[10000],int n) { int last_node=n-1; int parent=(last_node-1)/2; int i; for(i=parent;i>=0;i--) { heapify(tree,n,i); } }3.heap_sort:
每将最大值与最后一个节点交换后,堆的结构就被破坏了,需要再次堆化。
我们可以理解为每交换一次最大值,就将连接最大值的树枝砍断,那么需要排列的数就从n变为n-1,继续对n-1个数重复这个过程
int heap_sort(int tree[10000],int n) { build_heap(tree,n); int i; for(i=n-1;i>=0;i--) { swap(tree,i,0); heapify(tree,i,0); } }完整代码如下:
#includeint swap(int arr[10000],int i,int j) { int t; t=arr[i]; arr[i]=arr[j]; arr[j]=t; } int heapify(int tree[10000],int n,int i) { if(i>=n) { return ; } int c1,c2,max; c1=2*i+1; c2=2*i+2; max=i; if(c1 tree[max]) {max=c1;} if(c2 tree[max]) {max=c2;} if(max!=i) { swap(tree,max,i); heapify(tree,n,max); } } int build_heap(int tree[10000],int n) { int last_node=n-1; int parent=(last_node-1)/2; int i; for(i=parent;i>=0;i--) { heapify(tree,n,i); } } int heap_sort(int tree[10000],int n) { build_heap(tree,n); int i; for(i=n-1;i>=0;i--) { swap(tree,i,0); heapify(tree,i,0); } } int main() { int i,tree[10000],n; scanf("%d",&n); scanf("%d",&tree[0]); for(i=1;i 提示:该博客为学习@正月点灯笼《堆排序》的笔记
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)