打印二叉堆(Java实现)

打印二叉堆:利用层级关系

我这里是先将堆排序，然后在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]不存数据   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); }}

　　执行结果：

海外公司注册、海外银行开户、跨境平台代入驻、VAT、EPR等知识和在线办理：https://www.xlkjsw.com

原标题：打印二叉堆(Java实现)

关键词：JAVA