CPSC331_A3/MinHeap.java at master · Matt4890/CPSC331_A3 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package cpsc331.collections;

import java.util.NoSuchElementException;

/**
*
* Provides an interface for an unbounded binary MinHeap<br><br>
*
* MinHeap Invariant: A finite multiset of values of ordered type T is stored
* in a binary MinHeap
* <br><br>
*
* @author Wayne Eberly
*
*/

public interface MinHeap<T extends Comparable<T>> {

  /**
  *
  * @param v the value to be inserted into this binary MinHeap
  * <br><br>
  *
  * Precondition:<br>
  * <ol style="list-style-type: lower-alpha">
  * <li> The MinHeap Invariant is satisfied.</li>
  * <li> A value v with type T has been given as input. </li>
  * </ol>
  * Postcondition:<br>
  * <ol style="List-style-type: lower-alpha">
  * <li> The MinHeap Invariant is satisfied. </li>
  * <li> A copy of the value v has been inserted into the multiset represented
  *      by this binary MinHeap. No other changes have been made. </li>
  * </ol>
  *
  */

  public void insert (T v);

  /**
  *
  * @return the value that was deleted from this MinHeap
  * @throws NoSuchElementException if this MinHeap was already empty
  * <br><br>
  *
  * Precondition:<br>
  * <ol style="list-style-type: lower-alpha">
  * <li> The MinHeap Invariant is satisfied. </li>
  * </ol>
  * Postcondition:<br>
  * <ol style="list-style-type: lower-alpha">
  * <li> The MinHeap Invariant is satisfied. </li>
  * <li> If this MinHeap was not empty then a copy of the smallest element is removed
  *      from the multiset represented by this MinHeap and returned as output, and no
  *      other changes to this multiset have been made. A NoSuChElementException is
  *      thrown if this heap was already empty, an it is not changed. </li>
  * </ol>
  *
  */

  public T deleteMin () throws NoSuchElementException;

  /**
  *
  * @return the current size of this MinHeap
  * <br><br>
  *
  * Precondition:<br>
  * <ol style="list-style-type: lower-alpha">
  * <li> The MinHeap Invariant is satisfied. </li>
  * </ol>
  * Postcondition:<br>
  * <ol style="list-style-type: lower-alpha">
  * <li> This MinHeap has not changed, so the MinHeap Invariant is still satisfied. </li>
  * <li> The size of this MinHeap has been returned as output. </li>
  * </ol>
  *
  */

  public int getSize();

}