1   package kiasan.examples.binaryheap;
2   
3   import kiasan.examples.common.Overflow;
4   
5   // BinaryHeap class
6   //
7   // CONSTRUCTION: with optional capacity (that defaults to 100)
8   //
9   // ******************PUBLIC OPERATIONS*********************
10  // void insert( x )       --> Insert x
11  // int deleteMin( )--> Return and remove smallest item
12  // int findMin( )  --> Return smallest item
13  // boolean isEmpty( )     --> Return true if empty; else false
14  // boolean isFull( )      --> Return true if full; else false
15  // void makeEmpty( )      --> Remove all items
16  // ******************ERRORS********************************
17  // Throws Overflow if capacity exceeded
18  
19  /**
20   * Implements a binary heap. Note that all "matching" is based on the compareTo
21   * method.
22   * 
23   * @author Mark Allen Weiss
24   */
25  public class BinaryHeap {
26    private static final int DEFAULT_CAPACITY = 100;
27  
28    // Test program
29    public static void main(final String[] args) {
30      final int numItems = 10000;
31      final BinaryHeap h = new BinaryHeap(numItems);
32      int i = 37;
33  
34      try {
35        for (i = 37; i != 0; i = (i + 37) % numItems) {
36          h.insert(i);
37        }
38        for (i = 1; i < numItems; i++) {
39          if ((h.deleteMin()) != i) {
40            System.out.println("Oops! " + i);
41          }
42        }
43  
44        for (i = 37; i != 0; i = (i + 37) % numItems) {
45          h.insert(i);
46        }
47        h.insert(0);
48        i = 9999999;
49        h.insert(i);
50        for (i = 1; i <= numItems; i++) {
51          if (h.deleteMin() != i) {
52            System.out.println("Oops! " + i + " ");
53          }
54        }
55      } catch (final Overflow e) {
56        System.out.println("Overflow (expected)! " + i);
57      }
58    }
59  
60    private int currentSize; // Number of elements in heap
61  
62    private final int[] array; // The heap array
63  
64    /**
65     * Construct the binary heap.
66     */
67    public BinaryHeap() {
68      this(BinaryHeap.DEFAULT_CAPACITY);
69    }
70  
71    /**
72     * Construct the binary heap.
73     * 
74     * @param capacity
75     *          the capacity of the binary heap.
76     */
77    public BinaryHeap(final int capacity) {
78      this.currentSize = 0;
79      this.array = new int[capacity + 1];
80    }
81  
82    /**
83     * Establish heap order property from an arbitrary arrangement of items. Runs
84     * in linear time.
85     */
86    void buildHeap() {
87      for (int i = this.currentSize / 2; i > 0; i--) {
88        percolateDown(i);
89      }
90    }
91  
92    /**
93     * Remove the smallest item from the priority queue.
94     * 
95     * @return the smallest item, or null, if empty.
96     */
97    //@ requires wellFormed();
98    //@ ensures wellFormed();
99    public int deleteMin() {
102     }
103 
107 
109   }
110 
111   /**
112    * Find the smallest item in the priority queue.
113    * 
114    * @return the smallest item, or null, if empty.
115    */
116   //@ requires wellFormed();
117   //@ ensures wellFormed();
118   public int findMin() {
121     }
123   }
124 
125   /**
126    * Insert into the priority queue, maintaining heap order. Duplicates are
127    * allowed.
128    * 
129    * @param x
130    *          the item to insert.
131    * @exception Overflow
132    *              if container is full.
133    */
134   //@ requires wellFormed();
135   //@ ensures wellFormed();
136   public void insert(final int x) throws Overflow {
139     }
140 
141     // Percolate up
145     }
148 
149   /**
150    * Test if the priority queue is logically empty.
151    * 
152    * @return true if empty, false otherwise.
153    */
154   public boolean isEmpty() {
156   }
157 
158   /**
159    * Test if the priority queue is logically full.
160    * 
161    * @return true if full, false otherwise.
162    */
163   public boolean isFull() {
165   }
166 
167   /**
168    * Make the priority queue logically empty.
169    */
170   public void makeEmpty() {
171     this.currentSize = 0;
172   }
173 
174   /**
175    * Internal method to percolate down in the heap.
176    * 
177    * @param hole
178    *          the index at which the percolate begins.
179    */
180   private void percolateDown(int hole) {
181     /* 1 */int child;
183 
187           && (/* 6 */this.array[child + 1] < this.array[child])) {
188         /* 7 */child++;
189       }
192       } else {
193         /* 10 */break;
194       }
195     }
198 
199   boolean wellFormed() {
202     }
204       // >=
205       // 0
206       // ;
207       // currentSize<array.length;
209     }
213       }
217       }
218     }
220   }
221 }