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);
  }
}

执行结果：

总结

以上就是本文关于java语言实现二叉堆的打印代码分享的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

原文链接：http://www.cnblogs.com/noKing/p/7966272.html