二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：最大堆和最小堆。最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。
打印二叉堆：利用层级关系
我这里是先将堆排序，然后在sort里执行了打印堆的方法printastree()
|
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
public class maxheap<t extends comparable<? super t>> { private t[] data; private int size; private int capacity; public maxheap(int capacity) { this.capacity = capacity; this.size = 0; this.data = (t[]) new comparable[capacity + 1]; } public maxheap(t[] arr) {//heapify,数组建堆 capacity = arr.length; data = (t[]) new comparable[capacity + 1]; system.arraycopy(arr, 0, data, 1, arr.length); size = arr.length; for (int i = size / 2; i >= 1; i--) { shiftdown(i); } } public int size() { return this.size; } public int getcapacity() { return this.capacity; } public boolean isempty() { return size == 0; } 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); } public t popmax() { swap(1, size--); shiftdown(1); return data[size + 1]; } public void shiftup(int child) { while (child > 1 && data[child].compareto(data[child / 2]) > 0) { swap(child, child / 2); 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; } public void shiftdown(int father) { while (true) { int lchild = father * 2; int rchild = father * 2 + 1; int newfather = father;//这里赋不赋值无所谓，如果把下面这个return改成break,那就必须赋值了 if (lchild > size) {//如果没有左、右孩子 return; } else if (rchild > size) {//如果没有右孩子 newfather = max(father, lchild); } else {//如果有左、右孩子 newfather = max(father, lchild, rchild); } if (newfather == father) {//如果原父结点就是三者最大，则不用继续整理堆了 return; } else {//父节点不是最大，则把大的孩子交换上来，然后继续往下堆调整，直到满足大根堆为止 swap(newfather, father); father = newfather;//相当于继续shiftdown(newfather)。假如newfather原来是father的左孩子，那就相当于shiftdown(2*father) } } } public static <t extends comparable<? super t>> void sort(t[] arr) { int len = arr.length; maxheap<t> maxheap = new maxheap<>(arr); maxheap.printastree(); for (int i = len - 1; i >= 0; i--) { arr[i] = maxheap.popmax(); } } public static void printarr(object[] arr) { for (object o : arr) { system.out.print(o); system.out.print("\t"); } system.out.println(); } public void printspace(int n) {//打印n个空格(在这里用‘\t'来代替) for (int i = 0; i < n; i++) { system.out.printf("%3s", ""); } } public void printastree() { int linenum = 1;//首先遍历第一行 int lines = (int) (math.log(size) / math.log(2)) + 1;//lines是堆的层数 int spacenum = (int) (math.pow(2, lines) - 1); for (int i = 1; i <= size; ) { //因为在[1...size]左闭右闭区间存数据，data[0]不存数据 //每层都是打印这个区间[2^(层数-1) ... (2^层数)-1]。如果堆里的数不够(2^层数)-1个，那就打印到size。所以取min((2^层数)-1,size). for (int j = (int) math.pow(2, linenum - 1); j <= math.min(size, (int) math.pow(2, linenum) - 1); j++) { printspace(spacenum); //打印spacenum个空格 system.out.printf("%3s", data[j]);//打印数据 system.out.printf("%3s", "");//图片中绿色方框 printspace(spacenum);//打印spacenum个空格 i++;//每打印一个元素就 + 1 } linenum++; spacenum = spacenum / 2; system.out.println(); } } public static void main(string args[]) { integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6, 1, 3, 6, 1, 1}; sort(arr); }} |
执行结果：
总结
以上就是本文关于java语言实现二叉堆的打印代码分享的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！
原文链接：http://www.cnblogs.com/noKing/p/7966272.html
