Java语言实现二叉堆的打印代码分享
作者:GoldArowana 时间:2021-11-27 23:00:15
二叉堆是一种特殊的堆,二叉堆是完全二元树(二叉树)或者是近似完全二元树(二叉树)。二叉堆有两种:最大堆和最小堆。最大堆:父结点的键值总是大于或等于任何一个子节点的键值;最小堆:父结点的键值总是小于或等于任何一个子节点的键值。
打印二叉堆:利用层级关系
我这里是先将堆排序,然后在sort里执行了打印堆的方法printAsTree()
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);
}
}
执行结果:
来源:http://www.cnblogs.com/noKing/p/7966272.html
标签:java,二叉
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
JAVASE系统实现抽卡功能
2023-11-19 19:49:41
![](https://img.aspxhome.com/file/2023/0/58700_0s.jpg)
Android编程开发之TextView单击链接弹出Activity的方法
2023-08-06 18:27:11
![](https://img.aspxhome.com/file/2023/4/83544_0s.png)
Mybatis 复杂对象resultMap的使用
2023-10-12 22:56:44
![](https://img.aspxhome.com/file/2023/7/58557_0s.png)
Java 异常的栈轨迹(Stack Trace)详解及实例代码
2023-12-13 12:19:02
C语言根据协议分割获取字符串单元的实现代码
2023-06-21 08:20:27
![](https://img.aspxhome.com/file/2023/6/87146_0s.png)
opencv利用鼠标滑动画出多彩的形状
2023-11-03 05:20:57
![](https://img.aspxhome.com/file/2023/6/94046_0s.jpg)
java寻找迷宫路径的简单实现示例
2021-07-06 13:17:50
Java Socket实现单线程通信的方法示例
2022-04-22 15:43:02
Kotlin中的惰性操作容器Sequence序列使用原理详解
2023-10-01 14:21:55
![](https://img.aspxhome.com/file/2023/7/84717_0s.jpg)
Android实现图片设置圆角形式
2023-07-29 16:37:32
![](https://img.aspxhome.com/file/2023/6/85456_0s.jpg)
C语言预处理预编译命令及宏定义详解
2023-06-18 16:28:06
![](https://img.aspxhome.com/file/2023/3/83503_0s.png)
Java8内存模型PermGen Metaspace实例解析
2023-11-25 10:53:36
![](https://img.aspxhome.com/file/2023/8/59968_0s.jpg)
Java多线程工具CompletableFuture的使用教程
2023-07-30 20:31:45
![](https://img.aspxhome.com/file/2023/1/57711_0s.jpg)
SpringBoot整合Zookeeper详细教程
2022-07-24 11:33:09
![](https://img.aspxhome.com/file/2023/2/63392_0s.png)
java8学习教程之函数引用的使用方法
2023-08-28 12:03:19
Java面试synchronized偏向锁后hashcode存址
2023-08-09 09:15:06
![](https://img.aspxhome.com/file/2023/0/57920_0s.png)
详解java中String、StringBuilder、StringBuffer的区别
2023-06-17 06:03:23
Java web访问localhost报404错误问题的解决方法
2023-07-27 05:28:55
![](https://img.aspxhome.com/file/2023/3/57913_0s.png)
JavaWeb开发之使用jQuery与Ajax实现动态联级菜单效果
2023-11-28 19:46:08
![](https://img.aspxhome.com/file/2023/6/60466_0s.png)
Spring Boot Redis 集成配置详解
2022-12-05 20:57:59