daily pastebin goal
54%
SHARE
TWEET

Untitled

a guest Oct 12th, 2017 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. class ListNode<T> {
  3.     T data;
  4.     ListNode<T> next;
  5.     ListNode(T d, ListNode<T> nxt) {
  6.         data = d; next = nxt;
  7.     }
  8.  
  9.     public String toString() {
  10.         if (next == null)
  11.             return data.toString();
  12.         else
  13.             return data.toString() + " " + next.toString();
  14.     }
  15. }
  16.  
  17. class BinomialHeap<K extends Comparable<K>> {
  18.     K key;
  19.     int height;
  20.     ListNode<BinomialHeap<K>> children;
  21.  
  22.     BinomialHeap(K k, int h, ListNode<BinomialHeap<K>> kids)
  23.     {
  24.         this.key = k;
  25.         this.height = h;
  26.         this.children = kids;
  27.     }
  28.  
  29.     /*
  30.     * @precondition this.height == other.height
  31.      */
  32.     BinomialHeap<K> link(BinomialHeap<K> other) {
  33.         if (this.key.compareTo(other.key) < 0) {
  34.             ListNode<BinomialHeap<K>> kids = new ListNode<>(other, this.children);
  35.             return new BinomialHeap<>(this.key, this.height + 1, kids);
  36.         } else {
  37.             ListNode<BinomialHeap<K>> kids = new ListNode<>(this, other.children);
  38.             return new BinomialHeap<>(other.key, other.height + 1, kids);
  39.         }
  40.     }
  41.  
  42.     /**
  43.      * TODO
  44.      *
  45.      * The isHeap method checks whether or not the subtree of this node
  46.      * satisfies the heap property.
  47.      */
  48.     boolean isHeap() {
  49.         //THIS DOES NOT WORK
  50. //Within BinomialHeap
  51.         //Check and make sure roots are greater as we traverse the tree.
  52.         //Definition of a heap is that the children are ALWAYS bigger no matter what.  If there
  53.            //is an intance where a child is smaller than the parent, then it is NOT a heap.  - by definition of the heap property.
  54.         if(this.key.compareTo(this.children.next.data.key) < 0){
  55.             return false;
  56.         }
  57.         else if(this.key.compareTo(this.children.next.data.key) > 0){
  58.             //traverse further
  59.             this.children.next.data.isHeap();
  60.         }
  61.         return true;
  62.     }
  63.  
  64.     public String toString() {
  65.         String ret = "(" + key.toString();
  66.         if (children != null)
  67.             ret = ret + " " + children.toString();
  68.         return ret + ")";
  69.     }
  70.  
  71. }
  72.  
  73. public class BinomialQueue<K extends Comparable<K>> {
  74.     ListNode<BinomialHeap<K>> forest;
  75.  
  76.     public BinomialQueue() {
  77.  
  78.         forest = null;
  79.     }
  80.  
  81.     public void push(K key) {
  82.         this.forest = insert(new BinomialHeap<>(key,0,null), this.forest);
  83.     }
  84.  
  85.     public K extract_min() {
  86.         BinomialHeap<K> min = find_min(this.forest);
  87.         this.forest = remove(min, this.forest);
  88.         ListNode<BinomialHeap<K>> kids = reverse(min.children, null);
  89.         this.forest = merge(this.forest, kids);
  90.         return min.key;
  91.     }
  92.  
  93.     public boolean isEmpty() {
  94.         return forest == null;
  95.     }
  96.  
  97.     /**
  98.      * The isHeap method returns whether or not the Binomial Queue (a forest of Binomial Trees)
  99.      * satisfies the heap property.
  100.      */
  101.     public boolean isHeap() {
  102.         ListNode<BinomialHeap<K>> curr = this.forest;
  103.         boolean ret = true;
  104.         while (curr != null) {
  105.             ret = ret && curr.data.isHeap();
  106.             curr = curr.next;
  107.         }
  108.         return ret;
  109.     }
  110.  
  111.     public String toString() {
  112.         if (this.forest == null)
  113.             return "";
  114.         else
  115.             return this.forest.toString(); }
  116.  
  117.     /**********************************
  118.      * Helper functions
  119.      */
  120.  
  121.     BinomialHeap<K> find_min(ListNode<BinomialHeap<K>> ns) {
  122.         if (ns == null)
  123.             return null;
  124.         else
  125.             return find_min_helper(ns.next, ns.data);
  126.     }
  127.  
  128.     BinomialHeap<K> find_min_helper(ListNode<BinomialHeap<K>> ns, BinomialHeap<K> best) {
  129.         if (ns == null)
  130.             return best;
  131.         else if (ns.data.key.compareTo(best.key) < 0)
  132.                 return find_min_helper(ns.next, ns.data);
  133.         else
  134.             return find_min_helper(ns.next, best);
  135.     }
  136.  
  137.     ListNode<BinomialHeap<K>> remove(BinomialHeap<K> n, ListNode<BinomialHeap<K>> ns) {
  138.         if (ns == null)
  139.             return null;
  140.         else {
  141.             if (ns.data == n)
  142.                 return remove(n, ns.next);
  143.             else
  144.                 return new ListNode<>(ns.data, remove(n, ns.next));
  145.         }
  146.     }
  147.  
  148.     ListNode<BinomialHeap<K>> reverse(ListNode<BinomialHeap<K>> ns, ListNode<BinomialHeap<K>> out) {
  149.         if (ns == null)
  150.             return out;
  151.         else {
  152.            return reverse(ns.next, new ListNode<>(ns.data, out));
  153.         }
  154.     }
  155.  
  156.     /**
  157.      * TODO
  158.      * The insert method is analogous to binary addition. That is,
  159.      * it inserts the node n into the list ns to produce a new list
  160.      * that is still sorted by height.
  161.      *
  162.      * @param n     The node to insert.
  163.      * @param ns    The binomial forest into which to insert, ordered by height.
  164.      * @param <K>   The type of the keys.
  165.      * @return      A new binomial forest that includes the new node.
  166.      */
  167.     static <K extends Comparable<K>> ListNode<BinomialHeap<K>>
  168.     insert(BinomialHeap<K> n, ListNode<BinomialHeap<K>> ns) {
  169.  
  170.         throw new UnsupportedOperationException();
  171.     }
  172.  
  173.     /**
  174.      * TODO
  175.      * The merge method is analogous to the merge part of merge sort. That is,
  176.      * it takes two lists that are sorted (by height) and returns a new list that
  177.      * contains the elements of both lists, and the new list is sorted by height.
  178.      * @param ns1
  179.      * @param ns2
  180.      * @return A list that is sorted and contains all and only the elements in ns1 and ns2.
  181.      */
  182.     ListNode<BinomialHeap<K>> merge(ListNode<BinomialHeap<K>> ns1, ListNode<BinomialHeap<K>> ns2) {
  183.  
  184.         //Textbook solution, page 247
  185.         if(ns1 == null)
  186.             return ns2;
  187.         if(ns2 == null)
  188.             return ns1;
  189.         if(ns1.data.key.compareTo(ns2.data.key) < 0){
  190.             return merge(ns1,ns2);
  191.         }
  192.         else{
  193.             return merge(ns2,ns1);
  194.         }
  195.     }
  196.  
  197. }
RAW Paste Data
Top