A priority queue: the binary heap - Data Structures and Problem Solving Using Java - page 812

1 package weiss.util;
2
3 /**
4 * PriorityQueue class implemented via the binary heap.
5 */
6 public class PriorityQueue<AnyType> extends AbstractCollection<AnyType>
7 implements Queue<AnyType>
8 {
9 public PriorityQueue( )
10 { /* Figure 21.5 */ }
11 public PriorityQueue( Comparator<? super AnyType> c )
12 { /* Figure 21.5 */ }
13 public PriorityQueue( Collection<? extends AnyType> coll )
14 { /* Figure 21.5 */ }
15
16 public int size( )
17 { return currentSize; }
18 public void clear( )
19 { currentSize = 0; }
20 public Iterator<AnyType> iterator( )
21 { /* See online code */ }
22
23 public AnyType element( )
24 { /* Figure 21.6 */ }
25 public boolean add( AnyType x )
26 { /* Figure 21.9 */ }
27 public AnyType remove( )
28 { /* Figure 21.13 */ }
29
30 private void percolateDown( int hole )
31 { /* Figure 21.14 */ }
32 private void buildHeap( )
33 { /* Figure 21.16 */ }
34
35 private int currentSize; // Number of elements in heap
36 private AnyType [ ] array; // The heap array
37 private Comparator<? super AnyType> cmp;
38
39 private void doubleArray( )
40 { /* See online code */ }
41 private int compare( AnyType lhs, AnyType rhs )
42 { /* Same code as in TreeSet; see Figure 19.70 */ }
43 }
figure 21.4
The PriorityQueue class skeleton