• API
• FAQ
• Tools
• Archive
daily pastebin goal
0%
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.      */
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
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.

Top