堆排序（Heap Sort）

堆积排序（Heapsort）是指利用堆积树（堆）这种数据结构所设计的一种排序算法。堆积树是一个近似完全二叉树的结构，并同时满足堆积属性：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序的平均时间复杂度为O(nlogn)，空间复杂度为O(1)。堆排序是不稳定的。

 1.小根堆和大根堆

堆有小根堆和大根堆两种，如下图所示：

 

2.堆的存储

堆积树是一个近似完全二叉树的结构，通常用一维数组来实现，在完全二叉树中双亲结点和孩子结点之间存在如下关系：

父节点i的左子节点在位置 (2*i)；

父节点i的右子节点在位置 (2*i+1)；

子节点i的父节点在位置 floor(i/2)。

3.用大根堆排序的基本思想

① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区；
② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key；
③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。

4.代码实现

 

public class HeapSort {
	
	private static int left(int i){
		return 2*i;
	}
	
	private static int right(int i){
		return 2*i + 1;
	}
	
	public static void maxHeapify(int[] data, int i, int heapSize){
		
		int l = left(i);
		int r = right(i);
		int largest;
		
		if(l < heapSize && data[l] > data[i]){
			largest = l;
		}else{
			largest = i;
		}
		
		if(r < heapSize && data[r] > data[largest]){
			largest = r;
		}
		
		if(largest != i){
			swap(data,i,largest);
			maxHeapify(data, largest, heapSize);
		}
	}
	
	public static void buildMaxHeap(int[] data){
		int heapSize = data.length;
		
		for(int i = heapSize/2; i >= 0; i--){
			maxHeapify(data, i, heapSize);
		}
	}
	
	public static void heapSort(int[] data){
		int heapSize = data.length;
		
		buildMaxHeap(data);
		for(int i = heapSize - 1; i > 0; i--){
			swap(data,0,i);
			heapSize = heapSize - 1;
			maxHeapify(data, 0, heapSize);
		}
	}
	
	public static void swap(int[] data, int i, int j) {
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}
	
	public static void main(String[] args) {
		int[] number = {49,38,65,97,76,13,27,49};
		
		heapSort(number);
		for(int i = 0; i < number.length; i++) {
			System.out.print(number[i] + " ");
		}
	}
}

 

 5.补充

• 堆在调整的过程中，就是一个选择的行为，每次将最大值选至树根，而选择的路径并不是所有的元素，而是由树根至树叶的路径，因而可以加快选择的过程，所以Heap排序法才会被称之为改良的选择排序法。
• 堆可用来实现优先级队列，或者说堆就是一种优先级队列。优先级队列是这样的一种数据结构，对它的访问或者删除操作只能对集合中通过指定优先级方法得出的最高优先级元素进行。