快捷導(dǎo)航

Java 堆排序?qū)嵗?大頂堆、小頂堆)

更新時(shí)間：2017年12月04日 10:17:09 作者：Sun_Ru

下面小編就為大家分享一篇Java 堆排序?qū)嵗?大頂堆、小頂堆)，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

堆排序的平均時(shí)間復(fù)雜度為Ο(nlogn) 。

算法步驟：

1. 創(chuàng)建一個(gè)堆H[0..n-1]

2. 把堆首（最大值）和堆尾互換

3. 把堆的尺寸縮小1，并調(diào)用shift_down(0),目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置

4. 重復(fù)步驟2，直到堆的尺寸為1

堆：

堆實(shí)際上是一棵完全二叉樹，其任何一非葉節(jié)點(diǎn)滿足性質(zhì)： Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2] 即任何一非葉節(jié)點(diǎn)的關(guān)鍵字不大于或者不小于其左右孩子節(jié)點(diǎn)的關(guān)鍵字。堆分為大頂堆和小頂堆，滿足Key[i]>=Key[2i+1]&&key>=key[2i+2]稱為大頂堆，滿足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]稱為小頂堆。由上述性質(zhì)可知大頂堆的堆頂?shù)年P(guān)鍵字肯定是所有關(guān)鍵字中最大的，小頂堆的堆頂?shù)年P(guān)鍵字是所有關(guān)鍵字中最小的。

堆排序思想：

利用大頂堆(小頂堆)堆頂記錄的是最大關(guān)鍵字(最小關(guān)鍵字)這一特性，使得每次從無序中選擇最大記錄(最小記錄)變得簡單。其基本思想為(大頂堆)： 1)將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無序區(qū)； 2)將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2...n-1]<=R[n]; 3)由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對當(dāng)前無序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個(gè)元素交換，得到新的無序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過程完成。操作過程如下： 1)初始化堆：將R[1..n]構(gòu)造為堆； 2)將當(dāng)前無序區(qū)的堆頂元素R[1]同該區(qū)間的最后一個(gè)記錄交換，然后將新的無序區(qū)調(diào)整為新的堆。因此對于堆排序，最重要的兩個(gè)操作就是構(gòu)造初始堆和調(diào)整堆，其實(shí)構(gòu)造初始堆事實(shí)上也是調(diào)整堆的過程，只不過構(gòu)造初始堆是對所有的非葉節(jié)點(diǎn)都進(jìn)行調(diào)整。

一個(gè)圖示實(shí)例

給定一個(gè)整形數(shù)組a[]={16,7,3,20,17,8}，對其進(jìn)行堆排序。首先根據(jù)該數(shù)組元素構(gòu)建一個(gè)完全二叉樹，得到

然后需要構(gòu)造初始堆，則從最后一個(gè)非葉節(jié)點(diǎn)開始調(diào)整，調(diào)整過程如下：

20和16交換后導(dǎo)致16不滿足堆的性質(zhì)，因此需重新調(diào)整

這樣就得到了初始堆。

先進(jìn)行一次調(diào)整時(shí)其成為大頂堆，

即每次調(diào)整都是從父節(jié)點(diǎn)、左孩子節(jié)點(diǎn)、右孩子節(jié)點(diǎn)三者中選擇最大者跟父節(jié)點(diǎn)進(jìn)行交換(交換之后可能造成被交換的孩子節(jié)點(diǎn)不滿足堆的性質(zhì)，因此每次交換之后要重新對被交換的孩子節(jié)點(diǎn)進(jìn)行調(diào)整)。有了初始堆之后就可以進(jìn)行排序了。

此時(shí)3位于堆頂不滿堆的性質(zhì)，則需調(diào)整繼續(xù)調(diào)整

這樣整個(gè)區(qū)間便已經(jīng)有序了。從上述過程可知，堆排序其實(shí)也是一種選擇排序，是一種樹形選擇排序。只不過直接選擇排序中，為了從R[1...n]中選擇最大記錄，需比較n-1次，然后從R[1...n-2]中選擇最大記錄需比較n-2次。事實(shí)上這n-2次比較中有很多已經(jīng)在前面的n-1次比較中已經(jīng)做過，而樹形選擇排序恰好利用樹形的特點(diǎn)保存了部分前面的比較結(jié)果，因此可以減少比較次數(shù)。對于n個(gè)關(guān)鍵字序列，最壞情況下每個(gè)節(jié)點(diǎn)需比較log2(n)次，因此其最壞情況下時(shí)間復(fù)雜度為nlogn。堆排序?yàn)椴环€(wěn)定排序，不適合記錄較少的排序。上面描述了這么多，簡而言之,堆排序的基本做法是:首先，用原始數(shù)據(jù)構(gòu)建成一個(gè)大(小)堆作為原始無序區(qū)，然后，每次取出堆頂元素，放入有序區(qū)。由于堆頂元素被取出來了，我們用堆中最后一個(gè)元素放入堆頂，如此，堆的性質(zhì)就被破壞了。我們需要重新對堆進(jìn)行調(diào)整，如此繼續(xù)N次，那么無序區(qū)的N個(gè)元素都被放入有序區(qū)了，也就完成了排序過程。
（建堆是自底向上）

實(shí)際應(yīng)用：

實(shí)際中我們進(jìn)行堆排序是為了取得一定條件下的最大值或最小值，例如：需要在100個(gè)數(shù)中找到10個(gè)最大值，因此我們定義一個(gè)大小為10的堆，把100中的前十個(gè)數(shù)據(jù)建立成小頂堆（堆頂最?。?，然后從100個(gè)數(shù)據(jù)中的第11個(gè)數(shù)據(jù)開始與堆頂比較，若堆頂小于當(dāng)前數(shù)據(jù)，則把堆頂彈出，把當(dāng)前數(shù)據(jù)壓入堆頂，然后把數(shù)據(jù)從堆頂下移到一定位置即可，

代碼：

public class Test0 {
	static int[] arr;//堆數(shù)組，有效數(shù)組
	 public Test0(int m){
		arr= new int[m];
	}
	
	 static int m=0;
	static int size=0;//用來標(biāo)記堆中有效的數(shù)據(jù)
	public void addToSmall(int v){
		//int[] a = {16,4,5,9,1,10,11,12,13,14,15,2,3,6,7,8,111,222,333,555,66,67,54};
		//堆的大小為10
		//arr = new int[10];
		if(size<arr.length){
			arr[size]=v;
			add_sort(size);
			//add_sort1(size);
			size++;
		}else{
			arr[0]=v;
			add_sort1(0);								
		}

		
	}
	public void printSmall(){
		for(int i=0;i<size;i++){
			System.out.println(arr[i]);
		}
	}
	public void del(){ 
		size--;
		arr[0]=arr[9];
		add_sort1(0);
	}
	public void Small(int index){
		if(m<arr.length){
			add_sort(index);
			m++;
		}else{
			add_sort1(index);
			m++;
		}
	}
	public void add_sort( int index){//小頂堆，建堆
		/*
	  * 父節(jié)點(diǎn)坐標(biāo)：index
	  * 左孩子節(jié)點(diǎn)：index*2
	  * 右孩子節(jié)點(diǎn)：index*2+1
	  *若數(shù)組中最后一個(gè)為奇數(shù)則為 左孩子
	  *若數(shù)組中最后一個(gè)為偶數(shù)則為 右孩子
	      若孩子節(jié)點(diǎn)比父節(jié)點(diǎn)的值大，則進(jìn)行值交換，若右孩子比左孩子大則進(jìn)行值交換
		 * 
		 */
			int par;
			if(index!=0){
				if(index%2==0){
					par=(index-1)/2;
					if(arr[index]<arr[par]){
						swap(arr,index,par);
						add_sort(par);
					}
					if(arr[index]>arr[par*2]){
						swap(arr,index,par*2);
					if(arr[index]<arr[par]){
						swap(arr,index,par);
					}
					add_sort(par);
					}
					
				}else{
					par=index/2;
					if(arr[index]<arr[par]){
						swap(arr,index,par);
						add_sort(par);
					}
					if(arr[index]<arr[par*2+1]){
						swap(arr, index, par*2+1);
					if(arr[index]<arr[par]){
						swap(arr,index,par);
					}
					add_sort(par);
					}
				}
	
			}
		
		
	}
	public void add_sort1(int index){//調(diào)整小頂堆
		/*調(diào)整自頂向下
		 * 只要孩子節(jié)點(diǎn)比父節(jié)點(diǎn)的值大，就進(jìn)行值交換，
		 */
		int left=index*2;
		int right=index*2+1;
		int max=0;
		if(left<10&&arr[left]<arr[index]){
			max=left;
		}else{
			max=index;
		}
		if(right<10&&arr[right]<arr[max]){
			max=right;
		}
		if(max!=index){
			swap(arr,max,index);
			add_sort1(max);
		}
	}

}

測試代碼：
package 大頂堆;

import java.util.Scanner;

public class Main_test0 {
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
		System.out.println("(小頂堆)請輸入堆大?。?);
		int m=scan.nextInt();
		Test0 test = new Test0(m);
		int[] a = {16,4,5,9,1,10,11,12,13,14,15,2,3,6,7,8};
		for(int i=0;i<a.length;i++){
			test.addToSmall(a[i]);
		}
		test.printSmall();				
		test.del();
		test.printSmall();	
	
		scan.close();
	}
}

以上這篇Java 堆排序?qū)嵗?大頂堆、小頂堆)就是小編分享給大家的全部內(nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: