堆排序

Published: 24 Aug 2011 Category:

堆排序(heapsort)兼有插入排序和合并排序的特点。类似于合并排序:它的运行时间是O(nlgn);类似于插入排序,它是一种原地排序算法:在任何时候,数组中只有常数个元素存储在输入数组意外。堆排序将插入排序和合并排序的优点结合起来。

堆数据结构是一种数组对象,可以被视为一棵完全二叉树。数的每一层都是填满的,最后一层可能除外。

表示堆的数组A是一个具有两个属性的对象:length[A]是数组中的元素个数,heap-size[A]是存放在A中的堆的元素个数。即A[heap-size[A]]之后的元素都不属于相应的堆,此处heap-size[A]<=length[A]。

数的根为A[1],给定某个节点下标i,父节点和左右儿子的关系为: <p style="margin-left: 27pt;">PARENT(i) = floor(i/2);</p> <p style="margin-left: 27pt;">LEFT(i) = 2i;</p> <p style="margin-left: 27pt;">RIGHT(i) = 2i + 1; </p> 二叉堆有两种,最大堆:堆中某个结点的值之多和其父节点一样大;最小堆:堆中某个结点的值一定不小于父节点。堆排序算法中使用最大堆,最小堆通常在构造优先队列时使用。

堆结构上的基本操作和运行时间:

MAX-HEAPIFY:O(lgn),保持最大堆性质

BUILD-MAX-HEAP:以线性时间运行,在无序的输入数组基础上构造出最大堆

HEAPSORT:运行时间为O(nlgn),对一个数组进行原地排序

保持堆的性质MAX-HEAPIFY

对输入数组A和下标i,假定LEFT[i]和RIGHT[i]为根的两颗子树都是最大堆,但A[i]可能小于其子女,违反了最大堆性质。MAX-HEAPIFY用于调整A[i]的位置,使以i为根的子树成为最大堆。

MAX-HEAPIFY的基本方法是,从A[i],A[Left[i]]和A[Right[i]]中找出最大的,如果A[i]最大,则堆已经是最大堆;否则将i结点值和最大的子节点值交换,再对交换过的结点为根的子树递归调用MAX-HEAPIFY。

MAX-HEAPIFY的时间复杂度是O(lgn),即对一个高度为h的结点所需的运行时间为O(h)。

建堆BUILD-MAX_HEAP

建堆过程:自底向上地将一个数组A[1..n]变成一个最大堆。

子数组A[(floor(n/2)..n]都是叶子节点,BUILD-MAX_HEAP过程对堆中的非叶子节点有调用一次MAX-HEAPIFY。

BUILD-MAX_HEAP的时间复杂度是O(n)。

堆排序算法HEAPSORT

堆排序算法的过程:

1.用BUILD-MAX_HEAP将数组A[1..n]构造成一个最大堆;

2.交换数组中最大元素A[1]和A[n],并将堆中结点n去掉(减小heap-size[A]);

3.对A[1..n-1]调用MAX-HEAPIFY使其恢复为最大堆;

4.重复2-3步骤(此时n将为n-1)。

HEAPSORT过程的时间代价是O(nlgn)。

完整的java版堆排序代码如下:

[code lang=”java”]public class HeapSort{

private static int[] A = {3, 2, 6, 1, 9, 7, 8, 5, 4};

public static int left(int i){
	//数组下标从0开始,此处有调整
	return 2 * i + 1;
}

public static int right(int i){
	//数组下标从0开始,此处有调整
	return 2 * i + 2;
}

public static int parent(int i){
	return (int)Math.floor(i / 2 );
}

public static void maxHeapify(int i, int heapSize){
	int l = left(i);
	int r = right(i);
	int largest = 0;
	if(l &lt; heapSize &amp;&amp; A[l] &gt; A[i]){
		largest = l;
	}else{
		largest = i;
	}
	if(r &lt; heapSize &amp;&amp; A[r] &gt; A[largest]){
		largest = r;
	}
	if(largest != i){
		int temp = A[largest];
		A[largest] = A[i];
		A[i] = temp;
		maxHeapify(largest, heapSize);
	}else{
		return;
	}
}

public static void buildMaxHeap(){
	int heapSize = A.length;
	for(int i = (int)Math.floor(heapSize / 2) - 1; i &gt;= 0; i--){
		maxHeapify(i, heapSize);
	}
}

public static void heapSort(){
	buildMaxHeap();
	int heapSize = A.length;
	for(int i = A.length - 1; i &gt;0; i--){
		int temp = A[i];
		A[i] = A[0];
		A[0] = temp;
		heapSize--;
		maxHeapify(0, heapSize);
	}
}

public static void main(String[] args){
	for(int i : A){
		System.out.print(i + &quot;,&quot;);
	}
	System.out.print(&quot;\n&quot;);
	heapSort();
	for(int i : A){
		System.out.print(i + &quot;,&quot;);
	}
} }[/code]