How to draw a Tree from array of integer That will describe by Max heap per iteration

How to draw a Tree from array of integer That will describe by Max heap per iteration

04:11:00


Description:
This is the dynamic draw tree with heap sort algorithms.


Code 1:
?
package com.kartik.sorting.tree;
/**
 *
 * @author MandalKC
 *
 * @param <T>
 */
public class Node<T extends Comparable<?>> {
    public Node<T> left;
 public Node<T> right;
    T data;
    public Node(T data) {
        this.data = data;
    }
}

Code 2:
?
package com.kartik.sorting.tree;
/**
 * 
 * @author kartik 
 * This is dynamic heap sort tree printer
 */
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
 *
 * @author MandalKC
 *
 */
public class BTreePrinter {
 /**
  *
  * @param root
  */
 public static <T extends Comparable<?>> void printNode(Node<T> root) {
  int maxLevel = BTreePrinter.maxLevel(root);
  printNodeInternal(Collections.singletonList(root), 1, maxLevel);
 }
 /**
  *
  * @param nodes
  * @param level
  * @param maxLevel
  */
 private static <T extends Comparable<?>> void printNodeInternal(
   List<Node<T>> nodes, int level, int maxLevel) {
  if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
   return;
  int floor = maxLevel - level;
  int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
  int firstSpaces = (int) Math.pow(2, (floor)) - 1;
  int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;
  BTreePrinter.printWhitespaces(firstSpaces);
  List<Node<T>> newNodes = new ArrayList<Node<T>>();
  for (Node<T> node : nodes) {
   if (node != null) {
    System.out.print(node.data);
    newNodes.add(node.left);
    newNodes.add(node.right);
   } else {
    newNodes.add(null);
    newNodes.add(null);
    System.out.print(" ");
   }
   BTreePrinter.printWhitespaces(betweenSpaces);
  }
  System.out.println("");
  for (int i = 1; i <= endgeLines; i++) {
   for (int j = 0; j < nodes.size(); j++) {
    BTreePrinter.printWhitespaces(firstSpaces - i);
    if (nodes.get(j) == null) {
     BTreePrinter.printWhitespaces(endgeLines + endgeLines + i
       + 1);
     continue;
    }
    if (nodes.get(j).left != null)
     System.out.print("/");
    else
     BTreePrinter.printWhitespaces(1);
    BTreePrinter.printWhitespaces(i + i - 1);
    if (nodes.get(j).right != null)
     System.out.print("\\");
    else
     BTreePrinter.printWhitespaces(1);
    BTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
   }
   System.out.println("");
  }
  printNodeInternal(newNodes, level + 1, maxLevel);
 }
 /**
  *
  * @param count
  */
 private static void printWhitespaces(int count) {
  for (int i = 0; i < count; i++)
   System.out.print(" ");
 }
 /**
  *
  * @param node
  * @return
  */
 private static <T extends Comparable<?>> int maxLevel(Node<T> node) {
  if (node == null)
   return 0;
  return Math.max(BTreePrinter.maxLevel(node.left),
    BTreePrinter.maxLevel(node.right)) + 1;
 }
 /**
  *
  * @param list
  * @return
  */
 private static <T> boolean isAllElementsNull(List<T> list) {
  for (Object object : list) {
   if (object != null)
    return false;
  }
  return true;
 }
}

Code 3:
?
package com.kartik.sorting;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
import com.kartik.sorting.tree.BTreePrinter;
import com.kartik.sorting.tree.Node;
/**
 *
 * @author MandalKC
 *
 */
public class HeapSort {
 private static int[] a;
 private static int n;
 private static int left;
 private static int right;
 private static int largest;
 /**
  *
  * @param input
  */
 private static void printNumbers(int[] input) {
  for (int i = 0; i < input.length; i++) {
   System.out.print(input[i] + ", ");
  }
  System.out.println("\n");
 }
 /**
  *
  * @param input
  * @return
  */
 public static Node<Integer> drawTree(int[] input) {
  Node<Integer> node = null;
  Map<String, Node<Integer>> mapNode = new HashMap<String, Node<Integer>>();
  int i = 0, c = 0;
  int count = 0;
  for (i = 0; i < input.length; i++) {
   if (i > 0) {
    for (c = 1; c <= square(i); c++) {
     String stringKey = "n" + i + c;
     if (count < input.length) {
      node = new Node<Integer>(input[count]);
      mapNode.put(stringKey, node);
     }
     count++;
    }
   } else {
    String stringKey = "n" + i + c;
    node = new Node<Integer>(input[count]);
    mapNode.put(stringKey, node);
    count++;
   }
  }
  Map<String, Node<Integer>> sortMapNode = new TreeMap<String, Node<Integer>>(
    mapNode);
  Node<Integer> root = null;
  Node<Integer> prent = null;
  int countVal = 1;
  int pointerCount = 0;
  for (Map.Entry<String, Node<Integer>> entry : sortMapNode.entrySet()) {
   String key = entry.getKey();
   char p = key.charAt(1);
   char q = key.charAt(2);
   int k = Integer.parseInt(String.valueOf(p));
   int k1 = Integer.parseInt(String.valueOf(p));
   int k2 = Integer.parseInt(String.valueOf(q));
   if (k > 0) {
    String newKey = null;
    if (k1 % 2 == 0) {
     if ((k1 + k2) % 2 == 0) {
      newKey = "n" + (k1 - 1) + (k2 / 2);
      prent = mapNode.get(newKey);
      prent.right = entry.getValue();
      countVal++;
      pointerCount++;
     } else {
      if (k2 % 2 == 0) {
       newKey = "n" + (k1 - 1) + (k2 / 2);
       prent = mapNode.get(newKey);
       prent.right = entry.getValue();
       countVal++;
       pointerCount++;
      } else {
       newKey = "n" + (k1 - 1) + countVal;
       prent = mapNode.get(newKey);
       prent.left = entry.getValue();
       pointerCount++;
      }
     }
    } else {
     if ((k1 + k2) % 2 == 0) {
      if (k1 == 1) {
       newKey = "n00";
       prent = mapNode.get(newKey);
       if (k2 == 1) {
        prent.left = entry.getValue();
       }
       pointerCount++;
      } else {
       newKey = "n" + (k1 - 1) + countVal;
       prent = mapNode.get(newKey);
       prent.left = entry.getValue();
       pointerCount++;
      }
     } else {
      if (k1 == 1) {
       newKey = "n00";
       prent = mapNode.get(newKey);
       if (k2 == 2) {
        prent.right = entry.getValue();
        countVal++;
       }
       pointerCount++;
      } else {
       if (k2 % 2 == 0) {
        newKey = "n" + (k1 - 1) + (k2 / 2);
        prent = mapNode.get(newKey);
        prent.right = entry.getValue();
        countVal++;
        pointerCount++;
       } else {
        newKey = "n" + (k1 - 1) + countVal;
        prent = mapNode.get(newKey);
        prent.left = entry.getValue();
        pointerCount++;
       }
      }
     }
    }
    if (pointerCount == square(k1)) {
     countVal = 1;
     pointerCount = 0;
    }
   } else {
    root = entry.getValue();
   }
  }
  return root;
 }
 /**
  *
  * @param a
  * @return
  */
 public static int square(int a) {
  int n = 1;
  for (int i = 0; i < a; i++) {
   n = n * 2;
  }
  return n;
 }
 /**
  *
  * @param a
  */
 public static void buildheap(int[] a) {
  n = a.length - 1;
  for (int i = n / 2; i >= 0; i--) {
   maxheap(a, i);
  }
 }
 /**
  *
  * @param a
  * @param i
  */
 public static void maxheap(int[] a, int i) {
  left = 2 * i;
  right = 2 * i + 1;
  BTreePrinter.printNode(drawTree(a));
  printNumbers(a);
  if (left <= n && a[left] > a[i]) {
   largest = left;
  } else {
   largest = i;
  }
  if (right <= n && a[right] > a[largest]) {
   largest = right;
  }
  if (largest != i) {
   exchange(i, largest);
   maxheap(a, largest);
  }
 }
 /**
  *
  * @param i
  * @param j
  */
 public static void exchange(int i, int j) {
  int t = a[i];
  a[i] = a[j];
  a[j] = t;
 }
 /**
  *
  * @param myarray
  */
 public static void sort(int[] myarray) {
  a = myarray;
  buildheap(a);
  for (int i = n; i > 0; i--) {
   exchange(0, i);
   n = n - 1;
   maxheap(a, 0);
  }
 }
 public static void main(String[] args) {
  int []numbers={18,55,2,93,1,23,10,66,12,7,54,45,3,43,23,56,77,99,11,88};
  //int []numbers={18,55,2,93,1,23,10,66,12,7,54,3,43,23,56,77,99,11,88};
  //int[] numbers = { 4, 14, 7, 9, 8, 23, 5, 66, 100 ,34,12,77};
  sort(numbers);
 }
}



Output:
               18                              
              / \              
             /   \             
            /     \            
           /       \           
          /         \          
         /           \         
        /             \        
       /               \       
       55               2              
      / \             / \      
     /   \           /   \     
    /     \         /     \    
   /       \       /       \   
   93       1       23       10      
  / \     / \     / \     / \  
 /   \   /   \   /   \   /   \ 
 66   12   7   54   45   3   43   23  
/ \ / \ /                      
56 77 99 11 88                      
                                                               
18, 55, 2, 93, 1, 23, 10, 66, 12, 7, 54, 45, 3, 43, 23, 56, 77, 99, 11, 88,
               18                              
              / \              
             /   \             
            /     \            
           /       \           
          /         \          
         /           \         
        /             \        
       /               \       
       55               2              
      / \             / \      
     /   \           /   \     
    /     \         /     \    
   /       \       /       \   
   93       1       23       10      
  / \     / \     / \     / \  
 /   \   /   \   /   \   /   \ 
 66   12   88   54   45   3   43   23  
/ \ / \ /                      
56 77 99 11 7                      
                                                               
18, 55, 2, 93, 1, 23, 10, 66, 12, 88, 54, 45, 3, 43, 23, 56, 77, 99, 11, 7,


many more iteration you can run and see the result



Example 1 images:

About

I am Kartik Chandra Mandal from Bangalore, India. Working as software engineer in Java technology. Have good knowledge of OWASP and CSRF in security for applications and it's implementation in Java technology.

Next
« Prev Post
Previous
Next Post »
Subscribe to: Post Comments (Atom)