`
周凡杨
  • 浏览: 234301 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

排序算法之堆排序

阅读更多
 

一:概念

 

堆排序(英文为Heap sort :  是指利用这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

 

引文:

----------------------------------------------------------------------------------------------------------------------

   二叉树: 每个节点最多有两个子树的树结构。通常子树被称作左子树left subtree)和右子树right subtree)。二叉树常被用于实现二叉查找树二叉堆

 

   分类:二叉树分为完全二叉树和满二叉树

 

                       1

 

----------------------------------------------------------------------------------------------------------------------

 

二:堆的分类

 

因为堆可以视为一个完全二叉树,则除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个结点对应数组中的一个元素.

 

数组与堆之间的关系:

 



 

 

                               2  

 

  

 

因为是数组,所以索引下标应该是从0开始的:



 

 

 

从由数组转化堆的结构过程中,发现结论(用数学表达式标识):

 

l  索引i结点的父结点下标就为(i-1)/ 2

 

l  它的左右子结点下标分别为2*i+12*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

  • 大小: 155 KB
  • 大小: 48.3 KB
  • 大小: 27.7 KB
  • 大小: 23.4 KB
0
0
分享到:
评论

相关推荐

    排序算法之堆排序算法:用C++语言实现堆排序算法

    标题"排序算法之堆排序算法:用C++语言实现堆排序算法",意味着我们将讨论如何用C++编程语言来实现堆排序的过程。C++是面向对象的编程语言,具有丰富的库支持和高效的执行性能,是实现算法的理想选择。 描述"排序...

    排序算法 之 堆排序

    堆排序是一种基于比较的排序算法,其基本思想是利用二叉堆这一数据结构来实现数组或链表的排序。在计算机科学中,二叉堆通常可以分为最大堆和最小堆,最大堆中每个父节点的值都大于或等于其子节点的值,而最小堆则...

    排序算法之堆排序【c语言版本】

    排序算法之堆排序【c语言版本】有注释,例子直接拿来演示即可,自行修改参数

    排序算法之堆排序代码

    排序算法中的堆排序的代码,其他排序算法的代码可以私信我~

    排序算法之堆排序【java语言版本】

    排序算法之堆排序【java语言版本】有注释,例子直接拿来演示即可,自行修改参数

    排序算法编程 堆排序 快速排序

    Hoare在1960年提出,是目前最常用的内部排序算法之一。快速排序的核心思想是分治法:选取一个基准元素,将数组划分为两部分,一部分的元素都小于基准,另一部分的元素都大于基准,然后对这两部分分别进行快速排序。...

    堆排序算法源代码

    堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。...尽管现代计算机中有更快的排序算法(如快速排序、归并排序等),但堆排序因其简单性和稳定性,仍然是许多程序员的首选工具之一。

    C++语言的算法实现包括插入排序冒泡排序堆排序快速排序

    快速排序是C++中最常用的排序算法之一,由英国计算机科学家C.A.R. Hoare提出。它使用分治策略,选择一个基准元素,将数组分为两部分,一部分的所有元素都小于基准,另一部分的元素都大于基准,然后递归地对这两部分...

    C++堆排序实现算法

    简单的堆排序算法:以定长数组为例,动态数组等可以以此类推

    应用Java和Python分别实现堆排序算法

    堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和...

    7大排序算法实现程序(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)

    2. 冒泡排序:是最简单的排序算法之一,通过不断交换相邻位置的元素来逐渐达到排序的目的。每一轮遍历都能确保最大(或最小)的元素被放置到正确的位置,重复这个过程直到整个数组排序完成。 3. 选择排序:每次从未...

    堆排序详细图解(通俗易懂)+排序算法-堆排序(超详细)

    堆排序详细图解(通俗易懂)+排序算法----堆排序(超详细)堆排序详细图解(通俗易懂)+排序算法----堆排序(超详细)堆排序详细图解(通俗易懂)+排序算法----堆排序(超详细)堆排序详细图解(通俗易懂)+排序算法...

    十大经典排序算法堆排序详细图解(通俗易懂)

    十大经典排序算法堆排序详细图解(通俗易懂)十大经典排序算法堆排序详细图解(通俗易懂)十大经典排序算法堆排序详细图解(通俗易懂)十大经典排序算法堆排序详细图解(通俗易懂)十大经典排序算法堆排序详细图解...

    堆排序算法实现堆排序

    堆排序是一种基于比较的排序算法,它通过构造一个近似完全二叉树的堆结构来实现数据的排序。在此,我们将深入探讨堆排序的基本概念、原理以及如何通过编程实现。 一、堆排序的概念 堆是一个近似完全二叉树的结构,...

    堆排序算法实例

    堆排序是一种基于比较的排序算法,它通过构造一个近似完全二叉树的堆数据结构来实现排序。在计算机科学中,堆是一个可以被看作是一棵树形结构的数据集合,其中每个父节点的值都大于或等于其子节点的值(大顶堆)或...

    最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法

    最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法

    c++ 7 种排序.快速排序, 归并排序,插入排序,选择排序,起泡排序,堆排序,希尔排序

    下面将详细讲解这7种排序算法:快速排序、归并排序、插入排序、选择排序、冒泡排序、堆排序以及希尔排序。 1. **快速排序**:由C.A.R. Hoare提出的,采用分治策略。基本思想是选取一个基准元素,通过一趟排序将待...

    算法设计实验报告堆排序代码

    堆排序是一种高效的比较排序算法,其主要思想是利用堆这种数据结构进行数据的排序。堆是一个近似完全二叉树的结构,同时满足堆的性质:即父节点的键值总是大于或等于(在最大堆中)或小于或等于(在最小堆中)其子...

    六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。

    本话题主要探讨六种内部排序算法:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序以及堆排序。这六种排序算法各有优劣,适用于不同的场景,接下来我们将逐一进行详细阐述。 1. **直接插入排序**: 直接...

    C++实现希尔、快速、堆排序、归并排序算法

    Hoare在1960年提出,是目前应用最广泛的排序算法之一。它采用分治策略,通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行...

Global site tag (gtag.js) - Google Analytics