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]不存数据

//每层都是打印这个区间[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