Merging priority queues - Data Structures and Problem Solving Using Java - page 880

1 package weiss.nonstandard;
2
3 // PairingHeap class
4 //
5 // CONSTRUCTION: with no initializer
6 //
7 // ******************PUBLIC OPERATIONS*********************
8 // General methods for priority queues and also:
9 // void decreaseKey( Position p, newVal )
10 // --> Decrease value in node p
11 // ******************ERRORS********************************
12 // Exceptions thrown as warranted
13
14 public class PairingHeap<AnyType extends Comparable<? super AnyType>>
15 {
16 public interface Position<AnyType>
17 { AnyType getValue( ); }
18
19 private static class PairNode<AnyType> implements Position<AnyType>
20 { /* Figure 23.8 */ }
21
22 private PairNode<AnyType> root;
23 private int theSize;
24
25 public PairingHeap( )
26 { root = null; theSize = 0; }
27
28 public boolean isEmpty( )
29 { return root == null; }
30 public int size( )
31 { return theSize; }
32 public void makeEmpty( )
33 { root = null; theSize = 0; }
34
35 public Position<AnyType> insert( AnyType x )
36 { /* Figure 23.10 */ }
37 public AnyType findMin( )
38 { /* Figure 23.9 */ }
39 public AnyType deleteMin( )
40 { /* Figure 23.11 */ }
41 public void decreaseKey( Position<AnyType> pos, AnyType newVal )
42 { /* Figure 23.12 */ }
43
44 private PairNode<AnyType> compareAndLink( PairNode<AnyType> first,
45 PairNode<AnyType> second )
46 { /* Figure 23.14 */ }
47 private PairNode [ ] doubleIfFull( PairNode [ ] array, int index )
48 { /* Implementation is as usual; see online code */ }
49 private PairNode<AnyType> combineSiblings( PairNode<AnyType> firstSibling )
50 { /* Figure 23.15 */ }
51 }
figure 23.7
The PairingHeap class skeleton