最大堆的特點(diǎn)是父元素比子元素大，并且是一棵完全二叉樹。
data[1]開始存，data[0]空著不用。也可以把data[0]當(dāng)成size來(lái)用。
|
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對(duì)比) */ 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對(duì)比) */ public T popMax() { swap(1, size--); shiftDown(1); return data[size + 1]; } /** * @param child 孩子節(jié)點(diǎn)下角標(biāo)是child，父節(jié)點(diǎn)下角表是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數(shù)組中某個(gè)元素的下角標(biāo) * @param b data數(shù)組中某個(gè)元素的下角標(biāo) * @return 哪個(gè)元素大就返回哪個(gè)的下角標(biāo) */ 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數(shù)組中某個(gè)元素的下角標(biāo) * @param b data數(shù)組中某個(gè)元素的下角標(biāo) * @param c data數(shù)組中某個(gè)元素的下角標(biāo) * @return 哪個(gè)元素大就返回哪個(gè)的下角標(biāo) */ private int max(int a, int b, int c) { int biggest = max(a, b); biggest = max(biggest, c); return biggest; } /** * @param father 父節(jié)點(diǎn)下角標(biāo)是father,左右兩個(gè)孩子節(jié)點(diǎn)的下角表分別是：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即將更新，父、左、右三個(gè)結(jié)點(diǎn)誰(shuí)大，newFather就是誰(shuí)的下角標(biāo) if (lchild > size) { //如果該father結(jié)點(diǎn)既沒有左孩子，也沒有右孩子 return; } else if (rchild > size) { //如果該father結(jié)點(diǎn)只有左孩子，沒有右孩子 newFather = max(father, lchild); } else { //如果該father結(jié)點(diǎn)既有左孩子，又有右孩子 newFather = max(father, lchild, rchild); } if (newFather == father) { //說(shuō)明father比兩個(gè)子結(jié)點(diǎn)都要大，表名已經(jīng)是大根堆，不用繼續(xù)調(diào)整了 return; } else { //否則，還需要繼續(xù)調(diào)整堆，直到滿足大根堆條件為止 swap(father, newFather); //值進(jìn)行交換 father = newFather; //更新father的值，相當(dāng)于繼續(xù)調(diào)整shiftDown(newFather) } } } public static void main(String[] args) { //創(chuàng)建大根堆 MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100); //向堆里存 for (int i = 0; i < 100; i++) { maxHeap.insert((int) (Math.random() * 100)); } //創(chuàng)建數(shù)組 Integer[] arr = new Integer[100]; //從堆里取，放進(jìn)數(shù)組里 for (int i = 0; i < 100; i++) { arr[i] = maxHeap.popMax(); System.out.print(arr[i] + " "); } System.out.println(); }} |
最大堆：shiftDown()函數(shù)與上面不一樣
|
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對(duì)比) */ public T popMax() { T ret = data[1]; swap(1, size); size--; shiftDown(1); return ret; } /** * @return 查看最大根(只看不刪, 與popMax對(duì)比) */ 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]兩者取大的那個(gè) newFather = newFather + 1; } if (data[father].compareTo(data[newFather]) >= 0) { break; } else { swap(father, newFather); //值進(jìn)行交換 father = newFather; //newFather是(2*father)或者是(2*father+1),也就是繼續(xù)shiftDown(newFather); } } } public static void main(String[] args) { //創(chuàng)建大根堆 MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100); //向堆里存 for (int i = 0; i < 100; i++) { maxHeap.insert((int) (Math.random() * 100)); } //創(chuàng)建數(shù)組 Integer[] arr = new Integer[100]; //從堆里取，放進(jìn)數(shù)組里 for (int i = 0; i < 100; i++) { arr[i] = maxHeap.popMax(); System.out.print(arr[i] + " "); } System.out.println(); }} |
總結(jié)
以上就是本文關(guān)于Java語(yǔ)言實(shí)現(xiàn)最大堆代碼示例的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！
原文鏈接：http://www.cnblogs.com/noKing/p/7954898.html
