1   package kiasan.examples.leftistheap;
2   
3   import kiasan.examples.common.LinkedList;
4   import kiasan.examples.common.Underflow;
5   
6   // LeftistHeap class
7   //
8   // CONSTRUCTION: with a negative infinity sentinel
9   //
10  // ******************PUBLIC OPERATIONS*********************
11  // void insert( x )       --> Insert x
12  // Comparable deleteMin( )--> Return and remove smallest item
13  // Comparable findMin( )  --> Return smallest item
14  // boolean isEmpty( )     --> Return true if empty; else false
15  // void makeEmpty( )      --> Remove all items
16  // void merge( rhs )      --> Absorb rhs into this heap
17  // ******************ERRORS********************************
18  // Throws UnderflowException as appropriate
19  
20  /**
21   * Implements a leftist heap. Note that all "matching" is based on the compareTo
22   * method.
23   * 
24   * @author Mark Allen Weiss
25   */
26  public class LeftistHeap {
27    private static class LeftistNode {
28      int element; // The data in the node
29  
30      LeftistNode left; // Left child
31  
32      LeftistNode right; // Right child
33      int npl; // null path length
34  
35      // Constructors
36      LeftistNode(final int theElement) {
37        this(theElement, null, null);
38      }
39  
40      LeftistNode(final int theElement, final LeftistNode lt, final LeftistNode rt) {
41        this.element = theElement;
42        this.left = lt;
43        this.right = rt;
44        this.npl = 0;
45      }
46    }
47  
48    public static void main(final String[] args) {
49      final int numItems = 100;
50      final LeftistHeap h = new LeftistHeap();
51      final LeftistHeap h1 = new LeftistHeap();
52      int i = 37;
53  
54      for (i = 37; i != 0; i = (i + 37) % numItems) {
55        if (i % 2 == 0) {
56          h1.insert(i);
57        } else {
58          h.insert(i);
59        }
60      }
61      assert h.wellFormed();
62      h.merge(h1);
63      assert h.wellFormed();
64      for (i = 1; i < numItems; i++) {
65        if (h.deleteMin() != i) {
66          System.out.println("Oops! " + i);
67        }
68      }
69    }
70  
71    /**
72     * Swaps t's two children.
73     */
74    private static void swapChildren(final LeftistNode t) {
79  
80    private LeftistNode root; // root
81  
82    /**
83     * Construct the leftist heap.
84     */
85    public LeftistHeap() {
86      this.root = null;
87    }
88  
89    /**
90     * Remove the smallest item from the priority queue.
91     * 
92     * @return the smallest item, or throw UnderflowException if empty.
93     */
94    //@ requires this.wellFormed();
95    //@ ensures this.wellFormed();
96    public int deleteMin() {
99      }
100 
103 
105   }
106 
107   /**
108    * Find the smallest item in the priority queue.
109    * 
110    * @return the smallest item, or throw UnderflowException if empty.
111    */
112   //@ requires this.wellFormed();
113   //@ ensures this.wellFormed();
114   public int findMin() {
117     }
119   }
120 
121   /**
122    * Insert into the priority queue, maintaining heap order.
123    * 
124    * @param x
125    *          the item to insert.
126    */
127   //@ requires this.wellFormed();
128   //@ ensures (this.root != null) && this.wellFormed();
129   public void insert(final int x) {
132 
133   private boolean isAcyclic(final LeftistNode start,
134       final LinkedList<LeftistNode> seen) {
138       }
142       }
143     }
147       }
151       }
152     }
154   }
155 
156   /**
157    * Test if the priority queue is logically empty.
158    * 
159    * @return true if empty, false otherwise.
160    */
161   public boolean isEmpty() {
163   }
164 
165   private boolean isLeftist(final LeftistNode ln) {
168     }
172     }
176     }
179     }
181   }
182 
183   /**
184    * Make the priority queue logically empty.
185    */
186   public void makeEmpty() {
187     this.root = null;
188   }
189 
190   /**
191    * Merge rhs into the priority queue. rhs becomes empty. rhs must be different
192    * from this.
193    * 
194    * @param rhs
195    *          the other leftist heap.
196    */
197   //@ requires this.merge_preCondition(rhs);
198   //@ ensures this.wellFormed();
199   public void merge(final LeftistHeap rhs) {
202     }
203 
207 
208   /**
209    * Internal method to merge two roots. Deals with deviant cases and calls
210    * recursive merge1.
211    */
212   private LeftistNode merge(final LeftistNode h1, final LeftistNode h2) {
215     }
218     }
221     } else {
223     }
224   }
225 
226   boolean merge_preCondition(final LeftistHeap rhs) {
229     }
237       }
238     }
242       }
246     }
248   }
249 
250   /**
251    * Internal method to merge two roots. Assumes trees are not empty, and h1's
252    * root contains smallest item.
253    */
254   private LeftistNode merge1(final LeftistNode h1, final LeftistNode h2) {
257     } else {
261       }
263     }
265   }
266 
267   private boolean ordered(final LeftistNode ln) {
270     }
273     }
276     }
278   }
279 
280   private boolean wellFormed() {
283     }
288   }
289 }