Java：如何逐级打印存储为数组的堆

Question

我有一个代表最大堆的数组。例如

84 81 41 79 17 38 33 15 61 6

所以根是最大的。索引 i 处的每个中间层节点最多可以有两个子节点。它们将在 2*i+1 和 2*i+2 处。

如何以逐级方式打印此堆？喜欢

                             84(0)

                 81(1)                  41(2)

            79(3)        17(4)     38(5)       33(6) 

       15(7)    61(8)         6(9)

数组中每个元素的索引显示在括号中以供澄清。我不必打印索引。我认为这类似于按级别顺序打印 BST，但在这里，堆存储在数组中而不是列表中，这使得它有点棘手！

Answer 1

试试这个代码：

public class NewClass56 {
public static void main(String args[]){

    int a[] = new int[] {84 ,81 ,41 ,79 ,17 ,38 ,33 ,15 ,61 ,6};

    for(int i=0;i<10;i++){
        for(int j=0;j<Math.pow(2,i)&&j+Math.pow(2,i)<10;j++){
            System.out.print(a[j+(int)Math.pow(2,i)-1]+" ");

        }
        System.out.println();
    }



    }
}

如果您有n多个数字，则替换10为n.

并且你想要空格然后试试这个代码：

public class NewClass56 {
public static void main(String args[]){

    int a[] = new int[] {84 ,81 ,41 ,79 ,17 ,38 ,33 ,15 ,61 ,6};
    StringBuilder sb = new StringBuilder();
    int max=0;
    for(int i=0;i<10;i++){
        for(int j=0;j<Math.pow(2,i)&&j+Math.pow(2,i)<10;j++){

            if(j>max){
                max=j;
            }
        }

    }

    for(int i=0;i<10;i++){
        for(int j=0;j<Math.pow(2,i)&&j+Math.pow(2,i)<10;j++){

            for(int k=0;(k<max/((int)Math.pow(2, i)));k++){
                sb.append(" ");
            }
            sb.append(a[j+(int)Math.pow(2,i)-1]+" ");

        }
        sb.append("\n");

    }



    System.out.println(sb.toString());

}
}

Answer 2

还有另一种打印堆的方法。想象一下，您的结构具有以下索引（索引0是守护者，等于Integer.MIN_VALUE，此处未显示）：

          1
      /      \
    2          3
  /    \       / \
 4     5      6   7
/ \    /\     /\  /\
8 9  10 11 12 13 14 15 

它由数字数组表示。你在这里看到什么？对，1, 3, 7, 15。如果将其增加 1，它将是2, 4, 8, 16.

这些数字是什么？这只是2^level。level从 1 到 4 的级别在哪里。

我们如何计算这个水平？它是以 2 为底的索引的对数。

这是实现此方法的代码（请参阅dump函数）：

package org.solutions;
import java.util.ArrayList;
import java.util.Arrays;

class Heap {
    public ArrayList<Integer> arr;
    public Heap() {
        this.arr = new ArrayList<>();
        arr.add(Integer.MIN_VALUE); // add guardian
    }

    public void add(int x) {
        int i = arr.size();
        arr.add(x);
        while(arr.get(i) < arr.get(i / 2)) {
            swap(i, i/2);
            i = i / 2;
        }
    }

    private void swap(int i, int j) {
        int tmp = arr.get(i);
        arr.set(i, arr.get(j));
        arr.set(j, tmp);
    }

    public void dump() {
        int height = log2(arr.size()) + 1;

        for (int i = 1, len = arr.size(); i < len; i++) {
            int x = arr.get(i);
            int level = log2(i) + 1;
            int spaces = (height - level + 1) * 2;

            System.out.print(stringOfSize(spaces, ' '));
            System.out.print(x);

            if((int)Math.pow(2, level) - 1 == i) System.out.println();
        }
    }

    private String stringOfSize(int size, char ch) {
        char[] a = new char[size];
        Arrays.fill(a, ch);
        return new String(a);
    }

    // log with base 2
    private int log2(int x) {
        return (int)(Math.log(x) / Math.log(2)); // = log(x) with base 10 / log(2) with base 10
    }
}

public class Main {

    public static void main(String[] args) {
        Heap heap = new Heap();
        heap.add(30);
        heap.add(2);
        heap.add(15);
        heap.add(10);
        heap.add(31);
        heap.dump();
    }
}