一:概念
堆排序(英文为Heap sort ): 是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。
引文:
----------------------------------------------------------------------------------------------------------------------
二叉树: 每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
分类:二叉树分为完全二叉树和满二叉树
图 1
----------------------------------------------------------------------------------------------------------------------
二:堆的分类
因为堆可以视为一个完全二叉树,则除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个结点对应数组中的一个元素.
数组与堆之间的关系:
图 2
因为是数组,所以索引下标应该是从0开始的:
从由数组转化堆的结构过程中,发现结论(用数学表达式标识):
l 索引i结点的父结点下标就为(i-1)/ 2。
l 它的左右子结点下标分别为2*i+1和2*i+2。
如图3中索引为1的结点(元素值为2),其左右子结点下标分别为2*1+1=3(元素值为4)和2*1+2=4(元素值为6)。
堆的分类:
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆(又称为:大根堆、大顶堆)
当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆(又称为:小根堆、小顶堆)
下图展示一个最小堆:
三:排序思想
在上面我们图解了如何构建一个最小堆,下面用java程序来实现如何构建最大/小堆:
import java.util.Arrays; public class HeapTest { public static void main(String[] args) { //int [] a = {17,8,45,84,2,94}; int [] a = {1,2,3,4,5,6}; arrayToBigHeap(a); System.out.println(); arrayToSmallHeap(a); } /* 构建大根堆 * 最大堆:当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆 * array[i] >= array[i*2+1] && array[i]>=array[i*2+2] * 构建思想:从下往上筛选进行构建 */ public static void arrayToBigHeap(int array[]){ int tempA = 0; //中间变量 //这里i=(array.length>>1-1),表示从最后一个非叶节点开始调整 for(int i = (array.length>>1-1);i>=0;i--){ int l_child = i*2+1; //i的左孩子节点序号 int r_child = i*2+2; //i的右孩子节点序号 if(l_child<array.length && array[i]<array[l_child]){ tempA = array[i]; array[i] = array[l_child]; array[l_child] = tempA; arrayToBigHeap(array); } if(r_child<array.length && array[i]<array[r_child]){ tempA = array[i]; array[i] = array[r_child]; array[r_child] = tempA; arrayToBigHeap(array); } System.out.println(Arrays.toString(array)); } } /* 构建最小堆 * 最小堆:当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆 * array[i] <= array[i*2+1] && array[i] <= array[i*2+2] * 构建思想:从下往上筛选进行构建 */ public static void arrayToSmallHeap(int array[]){ int tempA = 0; //这里i=(array.length>>1-1),表示从最后一个非叶节点开始调整 for(int i = (array.length>>1-1) ;i>=0;i--){ int l_child = i*2+1; //i的左孩子节点序号 int r_child = i*2+2; //i的右孩子节点序号 if(l_child<array.length && array[i]>array[l_child]){ tempA = array[i]; array[i] = array[l_child]; array[l_child] = tempA; arrayToSmallHeap(array); } if(r_child<array.length && array[i]>array[r_child]){ tempA = array[i]; array[i] = array[r_child]; array[r_child] = tempA; arrayToSmallHeap(array); } System.out.println(Arrays.toString(array)); } } }
从上面程序可以看出,其中心思想是:
由下而上的依次进行堆的构建,根据构建最大堆或最小堆的数学表达式,比较当前节点与左子节点和右子节点的值,满足表达式则进行值的互换,一旦发生节点之间值的互换后,从头开始进行重构!
该思想优点是,简单易懂。缺点是耗时长,多了一些不必要的数据比较!
堆排序适合于大量数据的排序,堆排序的前续工作花费的时间比较多,
下面我们以大根堆为例说说:
大根堆,就是根节点是最大的元素,所以每次把最大的元素选出来,与最后的一个元素交换,然后再把前n-1个元素(也就是除最后一个元素)进行一个堆的重构,让其具有大根堆的性质,重复上面的过程,直到只剩一个元素为止。这个过程其实是个选择排序的过程,但是少了交换的次数,堆排序的时间复杂度是 nlogn。
四:JAVA如何实现堆排序
public class HeapSort { /** 构建大根堆 * @param ar */ private static void keepHeap(int[] ar) { int n = ar.length; for (int i = ((n >> 1) - 1); i >= 0; --i) { keepHeap(ar, n, i); } } /** * 维持一个大根堆的性质 * @param heap * @param from * @param to */ private static void keepHeap(int[] a, int arrayLength, int i) { int x = a[i]; int l_child = 2*i + 1; //左子节点的索引值 while (l_child <= arrayLength - 1) { if (l_child < arrayLength - 1 && a[l_child] < a[l_child+1]) ++l_child; if (a[l_child] > x) { a[i] = a[l_child]; i = l_child; l_child = 2*i + 1; } else break; } a[i] = x; System.out.println(Arrays.toString(a)); } /** * 堆排序 原理:每次把最大的元素(即:堆根)与最后一个元素交换, 然后把前n-1个元素进行堆的重构,直到只剩一个元素为止。 * @param a */ private static void heapSort(int[] a) { int n = a.length; while (n > 0) { int tmp = a[0]; a[0] = a[n - 1]; a[n - 1] = tmp; keepHeap(a, --n, 0); } } public static void main(String[] args) { int[] ar = {1,2,3,4,5,6}; keepHeap(ar); heapSort(ar); } }
五:算法复杂度
从上述过程可知,堆排序其实也是一种选择排序,是一种树形选择排序。只不过直接选择排序中,为了从R[1...n]中选择最大记录,需比较n-1次,然后 从R[1...n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过,而树形选择排序恰好利用树形的 特点保存了部分前面的比较结果,因此可以减少比较次数。对于n个关键字序列,最坏情况下每个节点需比较log2(n)次,因此其最坏情况下时间复杂度为 nlogn。堆排序为不稳定排序,不适合记录较少的排序。
参考资料:
http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91
http://blog.csdn.net/morewindows/article/details/6709644
http://www.cnblogs.com/kkun/archive/2011/11/23/2260286.html
http://www.cnblogs.com/zabery/archive/2011/07/26/2117103.html
http://codereview.stackexchange.com/questions/32606/implementation-of-heap-sort
http://www.augustana.ca/~mohrj/courses/2004.winter/csc310/source/HeapSort.java.html
http://www.java-tips.org/java-se-tips/java.lang/heap-sort-implementation-in-java.html
http://dsbryz.iteye.com/blog/1182056
http://www.java3z.com/cwbwebhome/article/article19/res027.html?id=3754
相关推荐
自己写的堆排序算法 包含.c文件的全部内容
最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法
排序算法之堆排序【c语言版本】有注释,例子直接拿来演示即可,自行修改参数
排序算法中的堆排序的代码,其他排序算法的代码可以私信我~
排序算法之堆排序【java语言版本】有注释,例子直接拿来演示即可,自行修改参数
简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
堆排序的源代码; 平台:openSUSE 11.4 编译器:GCC version 4.5.1
包含了四种常见的排序算法,是招聘面试时常出的题目,最好自己编译跑一遍
// 堆排序 #include typedef int InfoType; // 定义其它数据项的类型 #include "compare.h" #include "sort.h" typedef SqList HeapType; // 堆采用顺序表存储表示 void HeapAdjust(HeapType &H,int s,int m) // ...
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
堆排序算法 java
一个堆排序算法 c++写的 逻辑相同 可自行 改为java 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一...
C语言实现的堆排序算法。 提供了堆排序算法的一个接口,可以为其它功能提供功能。
1、 实现堆排序算法。 2、 理论分析并实验验证堆排序算法的时间复杂度。
用c语言实现堆排序算法,堆排序算法的实现,分析堆排序算法
自己编写的堆排序算法实现函数,本人亲测过绝对好使的代码,在这里与大家分享交流,希望能够给你带来帮助
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...
自己看书时写的排序算法:堆排序 CPP文件