Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An implementation of a minheap
import java.util.ArrayList;
import java.util.Random;
public class MinHeap<T extends Comparable<T>> {
private ArrayList<T> values;
public MinHeap() {
values = new ArrayList<T>();
}
public void push(T value) {
int index = values.size();
values.add(value);
while (index != 0) {
int parentIndex = (index - 1) / 2;
if (value.compareTo(values.get(parentIndex)) >= 0) {
break;
}
values.set(index, values.get(parentIndex));
values.set(parentIndex, value);
index = parentIndex;
}
}
public T peek() {
return values.get(0);
}
public T pop() {
T value = peek();
int lastIndex = values.size() - 1;
T insertedValue = values.get(lastIndex);
values.set(0, insertedValue);
values.remove(lastIndex);
int index = 0;
int leftChildIndex = 1;
int rightChildIndex = 2;
while (leftChildIndex < lastIndex) {
if (rightChildIndex >= lastIndex) {
if (insertedValue.compareTo(values.get(leftChildIndex)) > 0) {
values.set(index, values.get(leftChildIndex));
values.set(leftChildIndex, insertedValue);
}
break;
}
if (insertedValue.compareTo(values.get(leftChildIndex)) <= 0 &&
insertedValue.compareTo(values.get(rightChildIndex)) <= 0) {
break;
}
if (values.get(leftChildIndex).compareTo(values.get(rightChildIndex)) <= 0) {
values.set(index, values.get(leftChildIndex));
values.set(leftChildIndex, insertedValue);
index = leftChildIndex;
} else {
values.set(index, values.get(rightChildIndex));
values.set(rightChildIndex, insertedValue);
index = rightChildIndex;
}
leftChildIndex = (index * 2) + 1;
rightChildIndex = leftChildIndex + 1;
}
return value;
}
public boolean isEmpty() {
return values.isEmpty();
}
public String toString() {
return values.toString();
}
public static void main(String[] args) {
Random random = new Random();
MinHeap<Integer> heap = new MinHeap<>();
for (int i = 0; i < 15; i++) {
int value = random.nextInt(100);
System.out.println("push " + value);
heap.push(value);
System.out.println("=> " + heap);
}
while (!heap.isEmpty()) {
System.out.println("pop " + heap.pop());
System.out.println("=> " + heap);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.