堆(heap)是一棵具有以下属性的二叉树:

  • 它是一棵完全二叉树;

    对于位置在CurrentIndex处的节点,其父亲的位置ParentIndex = (CurrentIndex – 1)/ 2;其左孩子的位置LeftChildIndex = CurrentIndex * 2 + 1;其右孩子的位置RightChildIndex = CurrentIndex * 2 + 2。

  • 每个节点大于或等于它的任意一个孩子。

堆的Java实现:

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
public class Heap<E extends Comparable>{
private java.util.ArrayList<E> list = new java.util.ArrayList<E>();
public Heap(){
}
public int getSize(){
return list.size();
}
/**添加一个新节点*/
public void add(E e){
//将新节点添加到堆的末尾
list.add(e);
int currentIndex = list.size() - 1;
while(currentIndex > 0){
int parentIndex = (currentIndex - 1) / 2;
if(list.get(currentIndex).compareTo(list.get(parentIndex)) > 0){
E temp = list.get(parentIndex);
list.set(parentIndex, list.get(currentIndex));
list.set(currentIndex, temp);
currentIndex = parentIndex;
}
else
break;
}
}
/**删除根节点*/
public E remove(){
if(list.size() == 0)
return null;
E root = list.get(0);
//将堆末尾的节点移至根节点处
list.set(0, list.get(list.size() - 1));
list.remove(list.size() - 1);
int currentIndex = 0;
int leftChildIndex = currentIndex * 2 + 1;
int rightChildIndex = currentIndex * 2 + 2;
int maxIndex = leftChildIndex;
while(leftChildIndex <= list.size() - 1){
//存在右孩子,再比较左右孩子的大小关系
if(rightChildIndex <= list.size() - 1 ){
if(list.get(leftChildIndex).compareTo(list.get(rightChildIndex)) < 0)
maxIndex = rightChildIndex;
}
if(list.get(currentIndex).compareTo(list.get(maxIndex)) < 0){
E temp = list.get(maxIndex);
list.set(maxIndex, list.get(currentIndex));
list.set(currentIndex, temp);
currentIndex = maxIndex;
leftChildIndex = currentIndex * 2 + 1;
rightChildIndex = currentIndex * 2 + 2;
}
else
break;
}
return root;
}
}

remove()返回的根节点总是当前堆中节点的最大值,所以可以利用Heap类对元素进行排序。

这里给出一个堆排序的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class TestHeap{
public static void main(String[] args){
Heap<Integer> heap = new Heap<Integer>();
//将元素逐一添加到堆
heap.add(14);
heap.add(25);
heap.add(7);
heap.add(-13);
heap.add(46);
int size = heap.getSize();
for(int i = 0; i < size; i++)
System.out.print(heap.remove() + " ");
}
}
输出结果为:
1
46 25 14 7 -13

堆排序的时间复杂度为:O(nlogn) ,空间复杂度为:O(0)