堆排序（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ù)從堆頂下移到一定位置即可，
代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
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è)參考，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://blog.csdn.net/Sun_Ru/article/details/52004044
