這里主要介紹的是優(yōu)先隊列的二叉堆Java實現(xiàn)，代碼如下：
java" id="highlighter_609460">
|
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
|
package practice;import edu.princeton.cs.algs4.StdRandom;public class TestMain { public static void main(String[] args) { int[] a = new int[20]; for (int i = 0; i < a.length; i++) { int temp = (int)(StdRandom.random()*100); a[i] = temp; } for (int i : a) { System.out.print(i+" "); } System.out.println(); PQHeap pq = new PQHeap(); for (int i = 0; i < 20; i++) { pq.insert(a[i]); } System.out.println(); for (int i = 0; i < 20; i++) { System.out.print(pq.delMax()+" "); } }}/* * 優(yōu)先隊列的堆實現(xiàn) * 二叉堆，每個元素有兩個子元素，兩個子元素均比自己小 */class PQHeap{ private int[] a; private int p = 1; public PQHeap() { a = new int[2]; } /* * 插入元素 */ public void insert(int elements) { if (p == a.length) { resize(a.length*2); } a[p++] = elements; swim(p - 1); //將剛插入的元素上浮到正確位置 } /* * 返回并刪除最大元素 */ public int delMax() { if (p == a.length/4) { resize(a.length/2); } int result = a[1]; //找出最大元素 exch(1, --p); //將最后一個元素移到頂端 a[p] = 0; sink(1); //將剛移上去的元素沉下去，使堆有序 return result; } public boolean isEmpty() { return p == 0; } public int size() { return p; } public void show() { for (int i : a) { System.out.print(i+" "); } System.out.println(); } /* * 上浮元素 */ private void swim(int k) { //將元素與父元素比較，比父元素大則換位置 while (k > 1 && a[k/2] < a[k]) { exch(k/2, k); k = k/2; } } private void sink(int k) { //將元素與子元素比較，比子元素小則和兩個中較大的那個換位置 while (2*k < p && (a[k] < a[2*k + 1]) || (a[k] < a[2*k])) { if (a[2*k + 1] > a[2*k]) { exch(k, 2*k + 1); k = 2*k + 1; } else { exch(k, 2*k); k = 2*k; } } } private void resize(int length) { int[] b = new int[length]; //將數(shù)組長度改變 for (int i = 0; i < p; i++) { //將數(shù)組復制 b[i] = a[i]; } a = b; //讓a指向b的內(nèi)存空間 } /* * 交換 */ private void exch (int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }} |
總結(jié)
以上就是本文關(guān)于java編程實現(xiàn)優(yōu)先隊列的二叉堆代碼分享的全部內(nèi)容，希望對大家有所幫助。有什么問題可以隨時留言，小編會及時回復大家的。感謝朋友們對本站的支持！
原文鏈接：http://www.cnblogs.com/zhangqi66/p/7245557.html
