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

Question

I have an array that represents a Max Heap. For example

84 81 41 79 17 38 33 15 61 6

so the root is max. Each mid tier node at index i can have at most two children. They would be at 2*i+1 and 2*i+2.

How can i print this heap out in a level by level fashion? like

                             84(0)

                 81(1)                  41(2)

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

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

the index of each element in the array is shown in paranthesis for clarification. i dont have to print the index. I was thinking it would be similar to printing a BST in level order but here, the heap is stored in an array not a list which makes it a bit tricky!

Gotama

Have you tried something before? – Hornbill

(10) would be a child of 17 – Gotama

i tried to use a list of lists to store each level, but could not figure out how to populate it – Gotama

Answer 1

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

}
}

Deepsea

thanks, thats it. i should have thought about powers of two ! – Gotama

you need <= in the for loops, if number of elements in the array is 10. Otherwise last element, 6 will not be printed. :) – Bergquist

^^ Just spent 20 minutes trying to figure out why it wouldn't print the last element. The correction should be: j+Math.pow(2,i)<10; -> j+Math.pow(2,i)<=10; Otherwise everything works perfectly. – Vibes

Answer 2

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

Toul

Answer 3

The existing solutions didn't work for me so here's slightly different way of doing it that I think is also more human readable. Additionally, this doesn't use any external libraries. Note that this assumes that the first spot of the array is null, because often array-based heaps skip the array[0]. This will automatically determine the number of levels based on the input size which should be the number of nodes in the heap. It will add -- in every spot that is empty (e.g. if you have a 13-node heap the last two nodes will show up as empty).

private void printHeap(int[] heap, size) {
    int maxDepth = (int) (Math.log(size) / Math.log(2));  // log base 2 of n

    StringBuilder hs = new StringBuilder();  // heap string builder
    for(int d = maxDepth; d >= 0; d--) {  // number of layers, we build this backwards
        int layerLength = (int) Math.pow(2, d);  // numbers per layer

        StringBuilder line = new StringBuilder();  // line string builder
        for(int i = layerLength; i < (int) Math.pow(2, d + 1); i++) {
            // before spaces only on not-last layer
            if(d != maxDepth) {
                line.append(" ".repeat((int) Math.pow(2, maxDepth - d)));
            }
            // extra spaces for long lines
            int loops = maxDepth - d;
            if(loops >= 2) {
                loops -= 2;
                while(loops >= 0) {
                    line.append(" ".repeat((int) Math.pow(2, loops)));
                    loops--;
                }
            }

            // add in the number
            if(i <= size) {
                line.append(String.format("%-2s", heap[i]));  // add leading zeros
            } else {
                line.append("--");
            }

            line.append(" ".repeat((int) Math.pow(2, maxDepth - d)));  // after spaces
            // extra spaces for long lines
            loops = maxDepth - d;
            if(loops >= 2) {
                loops -= 2;
                while(loops >= 0) {
                    line.append(" ".repeat((int) Math.pow(2, loops)));
                    loops--;
                }
            }
        }
        hs.insert(0, line.toString() + "\n");  // prepend line
    }
    System.out.println(hs.toString());
}

Example input:

int[] heap = new int[]{0, 84, 81, 41, 79, 17, 38, 33, 15, 61, 6};
int size = heap.length-1 = 10

Example output:

           84           
     81          41     
  79    17    38    33  
15 61 6  -- -- -- -- -- 

---

You should be able to fairly easily change this to work as a toString method instead if necessary. The spacing will have to be modified if you want to use 3-digit numbers, if someone requests it I can edit with modified code for that.

Alec

Brillant! This worked for me, the other solution did not work . – Gomes

Answer 4

Divide & Conquer. Create the line lists of the subtrees, concatenate the lines and prepend the String for the root node of the subtree. Also make sure the lines have the same length and all are centered:

static String pad(String s, int lengthRigth, int length) {
    StringBuilder sb = new StringBuilder();

    for (int i = length - lengthRigth - s.length(); i > 0; i--) {
        sb.append(' ');
    }

    sb.append(s);

    for (int i = 0; i < lengthRigth; i++) {
        sb.append(' ');
    }

    return sb.toString();
}

static StringBuilder withSpacesAppended(String s, int spaceCount) {
    StringBuilder sb = new StringBuilder(s.length()+spaceCount).append(s);
    for (int i = 0; i < spaceCount; i++) {
        sb.append(' ');
    }
    return sb;
}

static void joinLists(List<String> list1, List<String> list2) {
    int i;
    final int size = list2.size();
    for (i = 0; i < size; i++) {
        list1.set(i, withSpacesAppended(list1.get(i), 2).append(list2.get(i)).toString());
    }
}

static List<String> createTreeStrings(int index, int[] array) {
    int child1 = 2 * index + 1;
    int child2 = 2 * index + 2;
    if (child1 >= array.length) {
        return new ArrayList<>(Collections.singletonList(toText(index, array)));
    } else {
        List<String> childList1 = createTreeStrings(child1, array);
        if (child2 < array.length) {
            joinLists(childList1, createTreeStrings(child2, array));
        }
        String text = toText(index, array);
        int currentLength = childList1.get(0).length();

        if (currentLength >= text.length()) {
            text = pad(text, (currentLength - text.length()) / 2, currentLength);
        } else {
            for (int i = 0, size = childList1.size(); i < size; i++) {
                childList1.set(i, pad(childList1.get(i), (currentLength - text.length()) / 2, currentLength));
            }
        }

        childList1.add(0, text);
        return childList1;
    }
}

static String toText(int index, int[] array) {
    return Integer.toString(array[index]) + '(' + index + ')';
}

Example use:

createTreeStrings(0, new int[]{84, 81, 41, 79, 17, 38, 33, 15, 61, 6}).forEach(System.out::println);
createTreeStrings(0, new int[]{Integer.MAX_VALUE, 6}).forEach(System.out::println);

La

Answer 5

The accepted answer created many new lines and ignores last element while displaying. Hence sharing optimised code,

public void display() {
        // n is number of elements in the heap
        // It can be further optimised by calculating height of the heap
        // and looping i only till height of the tree
        for (int i = 0; i <= n / 2; i++) {
            for (int j = 0; j < Math.pow(2, i) && j + Math.pow(2, i) <= n; j++) { // Each row has 2^n nodes
                System.out.print(heap[j + (int) Math.pow(2, i) - 1] + " ");
            }
            System.out.println();
        }
    }

Bergquist

Answer 6

If you want to store it in a list of lists (level order) , just split it once for every power of 2, like 1,2,4,8,16 ..

    private ArrayList<ArrayList<Integer>> heapParse(int[] arr) {

    ArrayList<ArrayList<Integer>> heap = new ArrayList<ArrayList<Integer>>();
    int j=-1;
    for (int i=0; i< arr.length;i++){
        if(isPowerOfTwo(i+1)){                
            heap.add(new ArrayList<>());
            j++;
        }
        heap.get(j).add(arr[i]);
    }       
    return heap;
    }

    private boolean isPowerOfTwo(int i){
       return (i&(i-1))==0;
    }

Parakeet

It is not about storing as a list of lists but how to print it. – Generally

He mentioned that in a comment he need to populate it into a list – Parakeet

Answer 7

• The following algorithm will print value as defined grid length.
• For example, the max element equals 100, mean each digits sit in placeholder that has length == 3. If max length is even, for ex: 4. Then the placeholder value will be 5. Always odds for center alignment.

• Result:

  [placeholder == 3] && [maxWidthLine == 31]

                  100               // [rear == 14] && [between == 29 -> Not Use]
          15-             17-       // [rear == 6] && [between == 13]
      -9-     -6-     13-     10-   // [rear == 2] && [between == 5]
    -4- -8- -3- -1- -5- --- --- --- // [rear == 0] && [between == 1]

• Result:

  [placeholder == 5] && [maxWidthLine == 5 * 2^3 + 2 ^ 3 - 1 == 47]
  

                     1000-                      // [Level == 0]
         -17--                   -13--          // [Level == 1]
   --9--       -15--       --5--       -10--    // [Level == 2]
--4-- --8-- --3-- --6-- --1-- ----- ----- ----- // [Level == 3]

• TypeScript source code:

/** @example
 ** > format(10, 3) -> "10-"
 ** > format(10, 4) -> "-10-"
 ** > format(100, 3) -> "100"
 ** > format(100, 4) -> "100-"
 **/
const format = <T extends string | number>(value: T, placeholder: number): string => {
    if (!value && value !== 0) {
        return "-".repeat(placeholder);
    }
    const number = Number.call(null, value).toString();
    const size = number.length;
    if (size > placeholder) {
        throw new EvalError(">>> Place-Holder is smaller than Number Length <<<");
    }
    const pads = (placeholder - size) >> 1;
    return "-".repeat(pads) + number + "-".repeat(placeholder - size - pads);
};

public print(): void {
    const size = this.heap.length;
    const maxDigit = Math.max(...this.heap as Array<number>);
    /** Place holder must be odds [1, 3, 5, 7, 9, 11, ...] ~!*/
    const placeholder = (Number.call(null, maxDigit).toString().length & ~1) + 1;
    /** Max Depth of Binary Search Tree from [0] to [N] ~!*/
    const maxDepth = Math.floor(Math.log(size) / Math.log(2)); // Min Depth = 0; [Root Level]
    /** Total Spaces of Line == <The Amount of placeholders> && <The Amount of Space-1 between Placeholders> ~!*/
    const totalLineSpaces = placeholder * (2 ** maxDepth) + (2 ** maxDepth - 1);
    /** Calculate the spaces need to pad to the Rear-Side and Between each Placeholders ~!*/
    const calculateSpace = (level: number): [number, number] => {
        /** @equation: ${TotalSpaces} - ${placeholder} * (2 ^ level) == 2x + (2 ^ level - 1)(2x + 1) ~!*/
        /** @constraint: ${BetweenSpaces} == (2x + 1) <- Space between each placeholders ~!*/
        const rear = (totalLineSpaces - (placeholder + 1) * (2 ** level) + 1) / Math.pow(2, level + 1);
        return [rear, 2 * rear + 1];
    };
    console.log("------------------------------------------");
    console.log(">>> Array representation of Heap Array <<<");
    console.log("------------------------------------------\n");

    let str = ''; /** Heap string builder ~!*/
    for (let level = 0; level <= maxDepth; level++) {
        const [rear, middle] = calculateSpace(level);
        if (level === 0) {
            str += " ".repeat(rear) + this.format(this.heap[0], placeholder) + " ".repeat(rear) + "\n";
            continue;
        }
        const elements: Array<string> = [];
        /** @description: Looping through each Tree-Layer. Ranged from [2^level - 1] to [2^(level+1) - 2] ~!*/
        for (let i = Math.pow(2, level) - 1; i <= Math.pow(2, level + 1) - 2; i++) {
            elements.push(this.format(this.heap[i], placeholder));
        }
        str += " ".repeat(rear) + elements.join(" ".repeat(middle)) + " ".repeat(rear) + "\n";
    }
    str += "\n" + "------------------------------------------";
    return console.log(str);
};

Discredit