? (二叉)堆(heap)數據結構是一種數組對象，可以視作一顆完全二叉樹，從該二叉樹的根開始層次遍歷這顆二叉樹就可以得到其對應的數組。樹的根節點為A[0]，對于樹中某個節點的坐標i，其左右孩子節點和父親節點的坐標可以很方便的求得：
?? LEFT(i)=2*i+1; RIGHT(i)=2*i+2; PARENT(i)=i/2 .
? 有兩種二叉堆：最大堆和最小堆。最大堆中，每個節點存儲的數值都大于等于其左右兩個孩子節點存儲的數值,亦即A[i]>=A[LEFT[i]]&&A[i]>=A[RIGHT[i]]。最小堆則正好相反。本文以最大堆為例。
? 知道了最大堆的定義之后，就要在給定的任意數組上構建最大堆，然后利用這個最大堆進行升序排序：
? (1) 構建最大堆：
? 首先我們定義一個方法Heapify(heap，i)，如果以i的左右孩子節點為根的子樹已經是最大堆，則該方法使得以i為根的子樹也成為最大堆。其偽代碼如下(摘自《算法導論》)：
1
MAX-
HEAPIFY(A,i)
2
l=
LEFT(i)
3
r=
RIGHT(i)
4
target=
i;
5
if
(l<=A.heap_size&&A[l]>
A[i])
6
target=
l;
7
if
(
if
(r<=A.heap_size&&A[r]>
A[i]))
8
target=
r;
9
if
(target!=
i)
10
exchange(A[i],A[target])
11
MAX-HEAPIFY(A,target)//遞歸
? 我們比較當前節點i的數值和其左右子節點的數值，如果i的某個子節點的數值大于i的數值，則違反了最大堆的定義，所以我們需要交換這兩個節點的位置。假設A[LEFT[i]]>A[RIGHT[i]]>A[i],則交換i節點與LEFT[i]節點。但是，被交換到左孩子節點的i節點可能會違反以左孩子結點為根的最大堆的定義，所以我們需要對這個最大堆遞歸調用MAX-HEAPIFY方法。
? 有了上面這個方法之后，我們就可以自底向上的調用MAX-HEAPIFY方法構建最大堆。因為A[A.length/2+1]及其之后的節點都是葉子節點，都可以看做只有一個節點的最大堆，所以我們可以從A[A.length/2]節點開始直到A[0]節點依次調用MAX-HEAPIFY方法，亦即從樹的層次遍歷的最后一個有孩子的節點開始，按照層次遍歷的逆序調用MAX-HEAPIFY方法：
1
BUILD-MAX-
HEAP(A)
2
for
i=A.length/
2
downto
1
3
MAX-HEAPIFY(A,i)
? (2) 堆排序
? 構造完最大堆之后，我們就可以利用其進行排序。因為最大堆只能保證A[0]存儲的是當前堆中最大的元素，我們可以把A[0]與堆的最后一個元素互換，這樣A[0]就排在了最后一個位置，也是正確的位置。這時最后一個位置已經不屬于最大堆，所以A.heap_size要減一。互換到A[0]的元素可能會破壞最大堆的性質，我們可以調用MAX-HEAPIFY方法使之重新成為最大堆，然后將A[0]交換至當前堆的最后一個位置。依次遞歸。
1
HEAPSORT(A)
2
for
i=A.length downto
2
3
exchange(A[i],A[
0
])
4
--A.heap_size
//
堆的大小減少
5
MAX-HEAPIFY(A,
0
)
? (3) 堆的JAVA實現
?
1
package
Algorithm;
2
3
import
java.util.*
;
4
/**
5
* 堆(Heap)
6
*
@author
Kemaswill
7
* 2012-10-5 Friday
8
*/
9
10
public
class
Heap {
11
12
public
static
int
[] data;
13
public
static
int
length;
14
public
static
int
heap_size;
15
16
public
Heap(){
17
this
.length=20
;
18
this
.heap_size=
length;
19
this
.data=
new
int
[length];
20
Random random=
new
Random(System.currentTimeMillis());
21
for
(
int
i=0;i<length;i++
){
22
data[i]=Math.abs(random.nextInt()%50
);
23
}
//
for
24
}
25
26
public
Heap(
int
n){
27
this
.length=
n;
28
this
.heap_size=
length;
29
this
.data=
new
int
[length];
30
Random random=
new
Random(System.currentTimeMillis());
31
for
(
int
i=0;i<length;i++
){
32
data[i]=Math.abs(random.nextInt()%50
);
33
}
//
for
34
}
35
36
public
static
void
max_heapify(Heap heap,
int
i){
37
if
(i<
heap.heap_size){
38
int
l=2*i+1
;
39
int
r=2*i+2
;
40
int
target=
i;
41
if
(l<heap.heap_size&&heap.data[l]>
heap.data[i]){
42
target=
l;
43
}
44
if
(r<heap.heap_size&&heap.data[r]>
heap.data[target]){
45
target=
r;
46
}
47
if
(target!=
i){
48
exchange(heap,i,target);
49
max_heapify(heap,target);
50
}
//
if
51
}
//
if
52
}
//
heapify
53
54
public
static
void
exchange(Heap heap,
int
x,
int
y){
55
int
tmp=
heap.data[x];
56
heap.data[x]=
heap.data[y];
57
heap.data[y]=
tmp;
58
}
59
60
public
static
void
build_heap(Heap heap){
61
//
對于所有非葉結點，依次調用max_heapify
62
for
(
int
i=heap.heap_size/2;i>=0;i--
){
63
max_heapify(heap,i);
64
}
65
}
66
67
public
static
void
heapsort(Heap heap){
68
69
for
(
int
i=heap.length-1;i>0;i--
){
70
exchange(heap,0
,i);
71
heap.heap_size--
;
72
max_heapify(heap,0
);
73
}
74
}
//
heapsotr
75
76
public
static
void
show_heap(Heap heap){
77
for
(
int
i=0;i<=(
int
)Math.log(heap.length)/Math.log(2)+2;i++
){
78
for
(
int
j=(
int
)Math.pow(2, i)-1;j<Math.pow(2, i+1)-1;j++
){
79
if
(j<
heap.length){
80
System.out.print(heap.data[j]+" "
);
81
}
82
else
break
;
83
}
84
System.out.println();
85
}
86
}
87
88
public
static
void
main(String[] args){
89
Heap heap=
new
Heap();
90
show_heap(heap);
91
build_heap(heap);
92
show_heap(heap);
93
heapsort(heap);
94
show_heap(heap);
95
96
}
//
main
97
98
}
?
? 參考文獻：
? [1] 《算法導論》 第6章 p73
? [2] 一個用Java實現的簡單的最大堆
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
