/*
 * DownHeap.java
 *
 */

import net.datastructures.*;

public class DownHeap {
    private int capacity;
    private int tree[];
    /* create a DownHeap with default capacity */
    public DownHeap () {
        capacity = 16;
        tree = new int[capacity];
    }

    public void insertNewNode (int rank, int e) {
        int parent, left ,right, tmp;
        /* insert new node */
        tree[rank]=e;
        /* switch the nodes to satisfy the heap order property */
        parent = e;
        while (rank*2 + 1 <= capacity) {
            left = tree[rank*2];
            right = tree[rank*2+1];
            if (left <= right && left < parent) {
                tree[rank*2] = parent;
                tree[rank] = left;
                rank = rank * 2;
                parent = left;
            }
            else  if (right < left && right < parent) {
                tree[rank*2+1] = parent;
                tree[rank] = right;
                parent = right;
                rank = rank * 2 + 1;
            }
            else
                break;
   
        }
    }
  /** print out the tree, assume each node contains an integer  */
  public void printTree() {

        int i, j;
        int space = 32;
        int intSpace;
        int nodeOneLine = 1;
        int nodeNum = 0;
        int cursor = 0;
        
        // edgeLine is initialized as a string of 64 spaces.
        char[] edgeLine = new char[64];
        for (j=0;j < 64; j++)
            edgeLine[j] =' ';
        
        // print the nodes
        for (i = 1; i < 16; i++) {
            if (i < 10)
                intSpace = 1;
            else 
                intSpace = 2;
            if (nodeNum == 0) {
                for (j=0; j < space - intSpace; j++)
                    System.out.print(' ');
                cursor += space;
            }
            else {
                for (j=0; j < space*2 - intSpace; j++)
                    System.out.print(' ');
                cursor += space *2;
            }
            
            System.out.print( tree[i] );
            if (i*2 +1 <= capacity) {
                edgeLine[cursor - 1 - space / 4] ='/';
            }
            if ( i*2 +1 <=capacity) {
                edgeLine[cursor -1 + space / 4] ='\\';
            }
             
            nodeNum ++;
            if (nodeNum==nodeOneLine) {
                System.out.print("\n");
                System.out.println(edgeLine);
                for (j=0;j < 64; j++)
                    edgeLine[j] =' ';
                space /= 2;
                nodeOneLine *=2;
                nodeNum = 0;
                cursor = 0;
            }
        }
    } 
    public static void main(String[] args) {
        int[]  data = {1, 3, 4, 5, 8, 20, 25, 7, 6, 21, 18, 17, 11, 24, 2};
        DownHeap heap = new DownHeap();
        int i;
        for (i=14; i >= 0; i--) {
            heap.insertNewNode(i+1, data[i]);
        }
        heap.printTree();
        
        System.out.println("Finished");
 
    }
}