周凡杨

浏览: 234589 次
性别:
来自: 上海

最近访客更多访客>>

apex53

qsjiangs

yuanyuan7891

汪小洋

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

排序算法之堆排序

博客分类：

算法

算法数据结构归并排序 java

一：概念

堆排序（英文为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。堆排序为不稳定排序，不适合记录较少的排序。