-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathLeftistHeap.java
More file actions
173 lines (153 loc) · 5.08 KB
/
Copy pathLeftistHeap.java
File metadata and controls
173 lines (153 loc) · 5.08 KB
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
package DataStructures.Heap;
import DataStructures.Comparable;
import DataStructures.MyInteger;
// LeftistHeap class
//
// CONSTRUCTION: with a negative infinity sentinel
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// Comparable deleteMin( )--> Return and remove smallest item
// Comparable findMin( ) --> Return smallest item
// boolean isEmpty( ) --> Return true if empty; else false
// boolean isFull( ) --> Return false in this implementation
// void makeEmpty( ) --> Remove all items
// void merge( rhs ) --> Absorb rhs into this heap
/**
* Implements a leftist heap.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
public class LeftistHeap
{
/**
* Construct the leftist heap.
*/
public LeftistHeap( )
{
root = null;
}
/**
* Merge rhs into the priority queue.
* rhs becomes empty. rhs must be different from this.
* @param rhs the other leftist heap.
*/
public void merge( LeftistHeap rhs )
{
if( this == rhs ) // Avoid aliasing problems
return;
root = merge( root, rhs.root );
rhs.root = null;
}
/**
* Internal static method to merge two roots.
* Deals with deviant cases and calls recursive merge1.
*/
private static LeftHeapNode merge( LeftHeapNode h1, LeftHeapNode h2 )
{
if( h1 == null )
return h2;
if( h2 == null )
return h1;
if( h1.element.compareTo( h2.element ) < 0 )
return merge1( h1, h2 );
else
return merge1( h2, h1 );
}
/**
* Internal static method to merge two roots.
* Assumes trees are not empty, and h1's root contains smallest item.
*/
private static LeftHeapNode merge1( LeftHeapNode h1, LeftHeapNode h2 )
{
if( h1.left == null ) // Single node
h1.left = h2; // Other fields in h1 already accurate
else
{
h1.right = merge( h1.right, h2 );
if( h1.left.npl < h1.right.npl )
swapChildren( h1 );
h1.npl = h1.right.npl + 1;
}
return h1;
}
/**
* Swaps t's two children.
*/
private static void swapChildren( LeftHeapNode t )
{
LeftHeapNode tmp = t.left;
t.left = t.right;
t.right = tmp;
}
/**
* Insert into the priority queue, maintaining heap order.
* @param x the item to insert.
*/
public void insert( Comparable x )
{
root = merge( new LeftHeapNode( x ), root );
}
/**
* Find the smallest item in the priority queue.
* @return the smallest item, or null, if empty.
*/
public Comparable findMin( )
{
if( isEmpty( ) )
return null;
return root.element;
}
/**
* Remove the smallest item from the priority queue.
* @return the smallest item, or null, if empty.
*/
public Comparable deleteMin( )
{
if( isEmpty( ) )
return null;
Comparable minItem = root.element;
root = merge( root.left, root.right );
return minItem;
}
/**
* Test if the priority queue is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}
/**
* Test if the priority queue is logically full.
* @return false in this implementation.
*/
public boolean isFull( )
{
return false;
}
/**
* Make the priority queue logically empty.
*/
public void makeEmpty( )
{
root = null;
}
private LeftHeapNode root; // root
public static void main( String [ ] args )
{
int numItems = 100;
LeftistHeap h = new LeftistHeap( );
LeftistHeap h1 = new LeftistHeap( );
int i = 37;
for( i = 37; i != 0; i = ( i + 37 ) % numItems )
if( i % 2 == 0 )
h1.insert( new MyInteger( i ) );
else
h.insert( new MyInteger( i ) );
h.merge( h1 );
for( i = 1; i < numItems; i++ )
if( ((MyInteger)( h.deleteMin( ) )).intValue( ) != i )
System.out.println( "Oops! " + i );
}
}