Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A min heap implementation in java.
import java.util.ArrayList;
public class MinHeap {
private ArrayList<Integer> list;
public MinHeap() {
this.list = new ArrayList<Integer>();
}
public MinHeap(ArrayList<Integer> items) {
this.list = items;
buildHeap();
}
public void insert(int item) {
list.add(item);
int i = list.size() - 1;
int parent = parent(i);
while (parent != i && list.get(i) < list.get(parent)) {
swap(i, parent);
i = parent;
parent = parent(i);
}
}
public void buildHeap() {
for (int i = list.size() / 2; i >= 0; i--) {
minHeapify(i);
}
}
public int extractMin() {
if (list.size() == 0) {
throw new IllegalStateException("MinHeap is EMPTY");
} else if (list.size() == 1) {
int min = list.remove(0);
return min;
}
// remove the last item ,and set it as new root
int min = list.get(0);
int lastItem = list.remove(list.size() - 1);
list.set(0, lastItem);
// bubble-down until heap property is maintained
minHeapify(0);
// return min key
return min;
}
public void decreaseKey(int i, int key) {
if (list.get(i) < key) {
throw new IllegalArgumentException("Key is larger than the original key");
}
list.set(i, key);
int parent = parent(i);
// bubble-up until heap property is maintained
while (i > 0 && list.get(parent) > list.get(i)) {
swap(i, parent);
i = parent;
parent = parent(parent);
}
}
private void minHeapify(int i) {
int left = left(i);
int right = right(i);
int smallest = -1;
// find the smallest key between current node and its children.
if (left <= list.size() - 1 && list.get(left) < list.get(i)) {
smallest = left;
} else {
smallest = i;
}
if (right <= list.size() - 1 && list.get(right) < list.get(smallest)) {
smallest = right;
}
// if the smallest key is not the current key then bubble-down it.
if (smallest != i) {
swap(i, smallest);
minHeapify(smallest);
}
}
public int getMin() {
return list.get(0);
}
public boolean isEmpty() {
return list.size() == 0;
}
private int right(int i) {
return 2 * i + 2;
}
private int left(int i) {
return 2 * i + 1;
}
private int parent(int i) {
if (i % 2 == 1) {
return i / 2;
}
return (i - 1) / 2;
}
private void swap(int i, int parent) {
int temp = list.get(parent);
list.set(parent, list.get(i));
list.set(i, temp);
}
}
@tatarize

This comment has been minimized.

Copy link

tatarize commented Aug 6, 2017

private int parent(int i) { return (i-1) / 2; }

@psvilela

This comment has been minimized.

Copy link

psvilela commented Jan 7, 2019

Muito bom!

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.