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
* Blog java2blogs.blogspot.com
* 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: |