(二叉)堆(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实现的简单的最大堆
