Repository navigation
Expand file tree
/
Copy pathMaxHeap.java
More file actions
144 lines (126 loc) · 3.3 KB
/
Copy pathMaxHeap.java
File metadata and controls
144 lines (126 loc) · 3.3 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
package PriorityQueue;
import Utilities.ChangeArrayLength;
public class MaxHeap implements MaxPriorityQueue {
// data members
Comparable[] heap; // array for complete binary tree
// number of elements in heap
int size;
/**
* create a heap with the given initial capacity
*
* @throws IllegalArgumentException
* when initialCapacity < 1
*/
public MaxHeap(int initialCapacity) {
if (initialCapacity < 1) {
throw new IllegalArgumentException("initialCapacity must be >= 1");
}
heap = new Comparable[initialCapacity + 1];
size = 0;
}
/**
* create a heap with initial capacity 10
*/
public MaxHeap() {
this(10);
}
public boolean isEmpty() {
return size == 0;
}
public Comparable getMax() {
return heap[1];
}
public int size() {
return size;
}
public String toString() {
StringBuffer s = new StringBuffer("[");
// put elements into the buffer
for (int i = 1; i <= size; i++)
if (heap[i] == null)
s.append("null, ");
else
s.append(heap[i].toString() + ", ");
if (size > 0)
s.delete(s.length() - 2, s.length());
s.append("]");
// create equivalent String
return new String(s);
}
/**
* put theElement into the heap
*/
public void put(Comparable theElement) {
// increase array size if necessary
if (size == heap.length - 1) {
heap = (Comparable[]) ChangeArrayLength.changeLength1D(heap,
2 * heap.length);
}
// find place for theElement
// currentNode starts at new leaf and moves up tree
int currentNode = ++size;
while (currentNode != 1
&& heap[currentNode / 2].compareTo(theElement) < 0) {
// cannot put theElement in heap[currentNode]
heap[currentNode] = heap[currentNode / 2];
currentNode /= 2; // move to parent
}
heap[currentNode] = theElement;
}
/**
* remove max element and return it
*/
public Comparable removeMax() {
if (size == 0) {
return null;
}
Comparable maxElement = heap[1];
Comparable lastElement = heap[size--];
// find place for lastElement starting at root
int currentNode = 1,
// child of currentNode
child = 2;
while (child <= size) {
// heap[child] should be larger child of currentNode
if (child < size && heap[child].compareTo(heap[child + 1]) < 0) {
child++;
}
// can we put lastElement in heap[currentNode]?
if (lastElement.compareTo(heap[child]) >= 0) {
break; // yes
}// no
heap[currentNode] = heap[child]; // move child up
currentNode = child;
// move down a level
child *= 2;
}
heap[currentNode] = lastElement;
return maxElement;
}
/**
* initialize max heap to element array theHeap
*/
public void initialize(Comparable[] theHeap, int theSize) {
heap = theHeap;
size = theSize;
for (int root = size / 2; root >= 1; root--) {
Comparable rootElement = heap[root];
// find place to put rootElement
int child = 2 * root; // parent of child is target
// location for rootElement
while (child <= size) {
// heap[child] should be larger sibling
if (child < size && heap[child].compareTo(heap[child + 1]) < 0) {
child++;
}
// can we put rootElement in heap[child/2]?
if (rootElement.compareTo(heap[child]) >= 0) {
break; // yes
}// no
heap[child / 2] = heap[child]; // move child up
child *= 2; // move down a level
}
heap[child / 2] = rootElement;
}
}
}