SHARE
TWEET

Untitled

a guest Oct 21st, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package dataStructures;
  2.  
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * @author myleslamb char min heap to be used for the construction of a huffman
  7.  *         tree
  8.  */
  9.  
  10. public class Heap<T extends Comparable<T>> {
  11.  
  12.     private T[] arr;
  13.     private int size;
  14.     private Order order;
  15.  
  16.     public Heap(Order type, int initsize, T[] arg) {
  17.  
  18.         this.order = type;
  19.         this.arr = arg;
  20.         this.arr = Arrays.copyOf(arg, initsize); // dont leak reference
  21.  
  22.         for (int i = 0; i < arg.length; i++)
  23.             arr[i] = arg[i];
  24.  
  25.         size = arg.length;
  26.         System.out.println(size);
  27.         this.buildHeap();
  28.     }
  29.  
  30.     public Heap(Order type, T[] arg) {
  31.         this(type, arg.length, arg);
  32.     }
  33.  
  34.     /**
  35.      * O(n) build method using sift down approach
  36.      */
  37.     public void buildHeap() {
  38.  
  39.         // from first node with child to root push down
  40.         for (int i = (size - 1) / 2; i >= 0; i--) {
  41.             impose(i);
  42.         }
  43.  
  44.     }
  45.  
  46.     /**
  47.      * return the index of the max child given teh index of teh input node
  48.      *
  49.      * returns -1 if the node is a leaf (no children)
  50.      *
  51.      * @param i index of the node
  52.      * @return the index of the greatest child
  53.      */
  54.     private int getMaxChild(int i) {
  55.         int lchild = (2 * i) + 1;
  56.         int rchild = lchild + 1;
  57.  
  58.         // we dont have any children
  59.         if (lchild > this.size - 1)
  60.             return -1;
  61.  
  62.         //we only have a left child
  63.         if (rchild > this.size - 1)
  64.             return lchild;
  65.        
  66.         //we have both
  67.         return (arr[lchild].compareTo(arr[rchild]) * this.order.ordinal > 0) ? lchild : rchild;
  68.  
  69.     }
  70.  
  71.     private void realloc(int newSize) {
  72.  
  73.         this.arr = Arrays.copyOf(this.arr, newSize);
  74.  
  75.     }
  76.  
  77.     public void insert(T val) {
  78.  
  79.         if (size == arr.length) {
  80.             realloc(2 * size);
  81.         }
  82.  
  83.         int insert = size++;
  84.         int parent = (insert - 1) / 2;
  85.         // push up till no longer greater than parent
  86.  
  87.         while (parent >= 0) {
  88.  
  89.             if (val.compareTo(arr[parent]) * this.order.ordinal > 0) {
  90.                 arr[insert] = arr[parent];
  91.                 insert = parent;
  92.  
  93.             } else {
  94.  
  95.                 break;
  96.  
  97.             }
  98.  
  99.             parent = (insert - 1) / 2;
  100.  
  101.         }
  102.  
  103.         arr[insert] = val;
  104.  
  105.     }
  106.  
  107.     /**
  108.      * swaps with the largest child until the heap property is satisfied
  109.      *
  110.      * @param i the index of the node to impose the heap property on
  111.      */
  112.     private void impose(int i) {
  113.  
  114.         T cursor = arr[i];
  115.         int index = i;
  116.  
  117.         while (true) {
  118.  
  119.             int maxChild = getMaxChild(index);
  120.  
  121.             // we dont have any children
  122.             if (maxChild == -1)
  123.                 break;
  124.  
  125.             // if the max child is greater we should swap and continue
  126.             if (cursor.compareTo(arr[maxChild]) * this.order.ordinal < 0) {
  127.                 arr[index] = arr[maxChild];
  128.                 index = maxChild;
  129.             } else
  130.                 break;
  131.         }
  132.  
  133.         arr[index] = cursor;
  134.  
  135.     }
  136.  
  137.     public T getMax() {
  138.         T ret = arr[0];
  139.         arr[0] = arr[--size];
  140.         impose(0);
  141.         return ret;
  142.  
  143.     }
  144.  
  145.     // assistant classes from here
  146.  
  147.     /*
  148.      * order enum used to allow for both min and max heaps from teh same class by
  149.      * multiplying with post compareTo we can
  150.      */
  151.     public static enum Order {
  152.         MIN(-1), MAX(1);
  153.  
  154.         int ordinal;
  155.  
  156.         private Order(int arg) {
  157.  
  158.             this.ordinal = arg;
  159.  
  160.         }
  161.  
  162.     };
  163.  
  164.     public String toString() {
  165.         return Arrays.toString(Arrays.copyOfRange(arr, 0, size));
  166.  
  167.     }
  168.  
  169. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top