最大堆的特点是父元素比子元素大，并且是一棵完全二叉树。
data[1]开始存，data[0]空着不用。也可以把data[0]当成size来用。
|
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
|
public class MaxHeap<T extends Comparable<? super T>> { private T[] data; private int size; private int capacity; public MaxHeap(int capacity) { this.data = (T[]) new Comparable[capacity + 1]; size = 0; this.capacity = capacity; } public int size() { return this.size; } public Boolean isEmpty() { return size == 0; } public int getCapacity() { return this.capacity; } /** * @return 查看最大根(只看不删, 与popMax对比) */ public T seekMax() { return data[1]; } public void swap(int i, int j) { if (i != j) { T temp = data[i]; data[i] = data[j]; data[j] = temp; } } public void insert(T item) { size++; data[size] = item; shiftUp(size); } /** * @return 弹出最大根(弹出意味着删除, 与seekMax对比) */ public T popMax() { swap(1, size--); shiftDown(1); return data[size + 1]; } /** * @param child 孩子节点下角标是child，父节点下角表是child/2 */ public void shiftUp(int child) { while (child > 1 && data[child].compareTo(data[child / 2]) > 0) { swap(child, child / 2); child = child / 2; } } /** * @param a data数组中某个元素的下角标 * @param b data数组中某个元素的下角标 * @return 哪个元素大就返回哪个的下角标 */ private int max(int a, int b) { if (data[a].compareTo(data[b]) < 0) { //如果data[b]大 return b; //返回b } else { //如果data[a]大 return a; //返回a } } /** * @param a data数组中某个元素的下角标 * @param b data数组中某个元素的下角标 * @param c data数组中某个元素的下角标 * @return 哪个元素大就返回哪个的下角标 */ private int max(int a, int b, int c) { int biggest = max(a, b); biggest = max(biggest, c); return biggest; } /** * @param father 父节点下角标是father,左右两个孩子节点的下角表分别是：father*2 和 father*2+1 */ public void shiftDown(int father) { while (true) { int lchild = father * 2; //左孩子 int rchild = father * 2 + 1; //右孩子 int newFather = father; //newFather即将更新，父、左、右三个结点谁大，newFather就是谁的下角标 if (lchild > size) { //如果该father结点既没有左孩子，也没有右孩子 return; } else if (rchild > size) { //如果该father结点只有左孩子，没有右孩子 newFather = max(father, lchild); } else { //如果该father结点既有左孩子，又有右孩子 newFather = max(father, lchild, rchild); } if (newFather == father) { //说明father比两个子结点都要大，表名已经是大根堆，不用继续调整了 return; } else { //否则，还需要继续调整堆，直到满足大根堆条件为止 swap(father, newFather); //值进行交换 father = newFather; //更新father的值，相当于继续调整shiftDown(newFather) } } } public static void main(String[] args) { //创建大根堆 MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100); //向堆里存 for (int i = 0; i < 100; i++) { maxHeap.insert((int) (Math.random() * 100)); } //创建数组 Integer[] arr = new Integer[100]; //从堆里取，放进数组里 for (int i = 0; i < 100; i++) { arr[i] = maxHeap.popMax(); System.out.print(arr[i] + " "); } System.out.println(); }} |
最大堆：shiftDown()函数与上面不一样
|
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
|
public class MaxHeap<T extends Comparable<? super T>> { private T[] data; private int size; private int capacity; public MaxHeap(int capacity) { data = (T[]) new Comparable[capacity + 1]; this.capacity = capacity; size = 0; } public int size() { return size; } public Boolean isEmpty() { return size == 0; } public void insert(T item) { data[size + 1] = item; size++; shiftUp(size); } /** * @return 弹出最大根(弹出意味着删除, 与seekMax对比) */ public T popMax() { T ret = data[1]; swap(1, size); size--; shiftDown(1); return ret; } /** * @return 查看最大根(只看不删, 与popMax对比) */ public T seekMax() { return data[1]; } public void swap(int i, int j) { if (i != j) { T temp = data[i]; data[i] = data[j]; data[j] = temp; } } public void shiftUp(int k) { while (k > 1 && data[k / 2].compareTo(data[k]) < 0) { swap(k, k / 2); k /= 2; } } public void shiftDown(int father) { while (2 * father <= size) { int newFather = 2 * father; if (newFather + 1 <= size && data[newFather + 1].compareTo(data[newFather]) > 0) { //data[j] data[j+1]两者取大的那个 newFather = newFather + 1; } if (data[father].compareTo(data[newFather]) >= 0) { break; } else { swap(father, newFather); //值进行交换 father = newFather; //newFather是(2*father)或者是(2*father+1),也就是继续shiftDown(newFather); } } } public static void main(String[] args) { //创建大根堆 MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100); //向堆里存 for (int i = 0; i < 100; i++) { maxHeap.insert((int) (Math.random() * 100)); } //创建数组 Integer[] arr = new Integer[100]; //从堆里取，放进数组里 for (int i = 0; i < 100; i++) { arr[i] = maxHeap.popMax(); System.out.print(arr[i] + " "); } System.out.println(); }} |
总结
以上就是本文关于Java语言实现最大堆代码示例的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！
原文链接：http://www.cnblogs.com/noKing/p/7954898.html
