Java : How to print heap stored as array, level by level

Try this code:

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



    }
}

If you have n number of numbers then replace 10 by n.

and you want the spaces then try this code:

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

}
}

There is another way to print heap. Imagine you have the structure with the following indexes (index 0 is guardian and equals to Integer.MIN_VALUE, not shown here):

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

and it's represented by array of numbers. What do you see here? Right, 1, 3, 7, 15. If you increase it by 1 it will be 2, 4, 8, 16.

And what are these numbers? It's just 2^level. Where level is level from 1 to 4.

How we can calculate this level? It's logarithm of index with base 2.

Here is the code that implements this approach (see dump function):

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

Tags:

Java

Heap