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