Java語言如何實現(xiàn)二叉堆的打印

這篇文章將為大家詳細(xì)講解有關(guān)Java語言如何實現(xiàn)二叉堆的打印，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

十載專注成都網(wǎng)站制作，成都定制網(wǎng)頁設(shè)計，個人網(wǎng)站制作服務(wù)，為大家分享網(wǎng)站制作知識、方案，網(wǎng)站設(shè)計流程、步驟,成功服務(wù)上千家企業(yè)。為您提供網(wǎng)站建設(shè),網(wǎng)站制作,網(wǎng)頁設(shè)計及定制高端網(wǎng)站建設(shè)服務(wù),專注于成都定制網(wǎng)頁設(shè)計,高端網(wǎng)頁制作,對成都假山制作等多個行業(yè)，擁有豐富的網(wǎng)站營銷經(jīng)驗。

二叉堆是一種特殊的堆，二叉堆是完全二元樹（二叉樹）或者是近似完全二元樹（二叉樹）。二叉堆有兩種：最大堆和最小堆。最大堆：父結(jié)點的鍵值總是大于或等于任何一個子節(jié)點的鍵值；最小堆：父結(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值。

打印二叉堆：利用層級關(guān)系

Java語言如何實現(xiàn)二叉堆的打印

我這里是先將堆排序，然后在sort里執(zhí)行了打印堆的方法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,數(shù)組建堆
    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數(shù)組中某個元素的下角標(biāo)
   * @param b data數(shù)組中某個元素的下角標(biāo)
   * @return 哪個元素大就返回哪個的下角標(biāo)
   */
  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數(shù)組中某個元素的下角標(biāo)
   * @param b data數(shù)組中某個元素的下角標(biāo)
   * @param c data數(shù)組中某個元素的下角標(biāo)
   * @return 哪個元素大就返回哪個的下角標(biāo)
   */
  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) {//如果原父結(jié)點就是三者最大，則不用繼續(xù)整理堆了
        return;
      } else {//父節(jié)點不是最大，則把大的孩子交換上來，然后繼續(xù)往下堆調(diào)整，直到滿足大根堆為止
        swap(newFather, father);
        father = newFather;//相當(dāng)于繼續(xù)shiftDown(newFather)。假如newFather原來是father的左孩子，那就相當(dāng)于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是堆的層數(shù)
    int spaceNum = (int) (Math.pow(2, lines) - 1);
    for (int i = 1; i <= size; ) { //因為在[1...size]左閉右閉區(qū)間存數(shù)據(jù)，data[0]不存數(shù)據(jù)
       
      //每層都是打印這個區(qū)間[2^(層數(shù)-1) ... (2^層數(shù))-1]。如果堆里的數(shù)不夠(2^層數(shù))-1個，那就打印到size。所以取min((2^層數(shù))-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]);//打印數(shù)據(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);
  }
}

執(zhí)行結(jié)果：

Java語言如何實現(xiàn)二叉堆的打印

關(guān)于“Java語言如何實現(xiàn)二叉堆的打印”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。

網(wǎng)頁名稱：Java語言如何實現(xiàn)二叉堆的打印
網(wǎng)頁地址：http://muchs.cn/article6/ihiiig.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站內(nèi)鏈、軟件開發(fā)、關(guān)鍵詞優(yōu)化、小程序開發(fā)、手機(jī)網(wǎng)站建設(shè)、ChatGPT

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

網(wǎng)站優(yōu)化排名