1 import java.util.*;
2
3 /**
4 This class implements a heap.
5 */
6 public class MinHeap
7 {
8 private ArrayList<Comparable> elements;
9
10 /**
11 Constructs an empty heap.
12 */
13 public MinHeap()
14 {
15 elements = new ArrayList<Comparable>();
16 elements.add(null);
17 }
18
19 /**
20 Adds a new element to this heap.
21 @param newElement the element to add
22 */
23 public void add(Comparable newElement)
24 {
25 // Add a new leaf
26 elements.add(null);
27 int index = elements.size() - 1;
28
29 // Demote parents that are larger than the new element
30 while (index > 1
31 && getParent(index).compareTo(newElement) > 0)
32 {
33 elements.set(index, getParent(index));
34 index = getParentIndex(index);
35 }
36
37 // Store the new element into the vacant slot
38 elements.set(index, newElement);
39 }
40
41 /**
42 Gets the minimum element stored in this heap.
43 @return the minimum element
44 */
45 public Comparable peek()
46 {
47 return elements.get(1);
48 }
49
50 /**
51 Removes the minimum element from this heap.
52 @return the minimum element
53 */
54 public Comparable remove()
55 {
56 Comparable minimum = elements.get(1);
57
58 // Remove last element
59 int lastIndex = elements.size() - 1;
60 Comparable last = elements.remove(lastIndex);
61
62 if (lastIndex > 1)
63 {
64 elements.set(1, last);
65 fixHeap();
66 }
67
68 return minimum;
69 }
70
71 /**
72 Turns the tree back into a heap, provided only the root
73 node violates the heap condition.
74 */
75 private void fixHeap()
76 {
77 Comparable root = elements.get(1);
78
79 int lastIndex = elements.size() - 1;
80 // Promote children of removed root while they are smaller than last
81
82 int index = 1;
83 boolean more = true;
84 while (more)
85 {
86 int childIndex = getLeftChildIndex(index);
87 if (childIndex <= lastIndex)
88 {
89 // Get smaller child
90
91 // Get left child first
92 Comparable child = getLeftChild(index);
93
94 // Use right child instead if it is smaller
95 if (getRightChildIndex(index) <= lastIndex
96 && getRightChild(index).compareTo(child) < 0)
97 {
98 childIndex = getRightChildIndex(index);
99 child = getRightChild(index);
100 }
101
102 // Check if larger child is smaller than root
103 if (child.compareTo(root) < 0)
104 {
105 // Promote child
106 elements.set(index, child);
107 index = childIndex;
108 }
109 else
110 {
111 // Root is smaller than both children
112 more = false;
113 }
114 }
115 else
116 {
117 // No children
118 more = false;
119 }
120 }
121
122 // Store root element in vacant slot
123 elements.set(index, root);
124 }
125
126 /**
127 Checks whether this heap is empty.
128 */
129 public boolean empty()
130 {
131 return elements.size() == 1;
132 }
133
134 /**
135 Returns the index of the left child.
136 @param index the index of a node in this heap
137 @return the index of the left child of the given node
138 */
139 private static int getLeftChildIndex(int index)
140 {
141 return 2 * index;
142 }
143
144 /**
145 Returns the index of the right child.
146 @param index the index of a node in this heap
147 @return the index of the right child of the given node
148 */
149 private static int getRightChildIndex(int index)
150 {
151 return 2 * index + 1;
152 }
153
154 /**
155 Returns the index of the parent.
156 @param index the index of a node in this heap
157 @return the index of the parent of the given node
158 */
159 private static int getParentIndex(int index)
160 {
161 return index / 2;
162 }
163
164 /**
165 Returns the value of the left child.
166 @param index the index of a node in this heap
167 @return the value of the left child of the given node
168 */
169 private Comparable getLeftChild(int index)
170 {
171 return elements.get(2 * index);
172 }
173
174 /**
175 Returns the value of the right child.
176 @param index the index of a node in this heap
177 @return the value of the right child of the given node
178 */
179 private Comparable getRightChild(int index)
180 {
181 return elements.get(2 * index + 1);
182 }
183
184 /**
185 Returns the value of the parent.
186 @param index the index of a node in this heap
187 @return the value of the parent of the given node
188 */
189 private Comparable getParent(int index)
190 {
191 return elements.get(index / 2);
192 }
193 }