Created
May 22, 2012 19:49
-
-
Save roman/2771216 to your computer and use it in GitHub Desktop.
Heap Implementation in Java [shivers]...
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
// This is a min heap | |
public class Heap { | |
protected int[] data = new int[1000]; | |
public Heap() { | |
this.data[0] = 0; | |
} | |
public Heap insert(int value) { | |
++this.data[0]; | |
this.data[this.data[0]] = value; | |
this.bubbleUp(this.data[0]); | |
return this; | |
} | |
protected void bubbleUp(int index) { | |
// TASK: Find the parent index | |
int parentIndex = index / 2; | |
// TASK: check halt condition, if parent is less than children | |
// or current is the root, we need to do nothing | |
if (index == 1 || | |
this.data[parentIndex] < this.data[index]) return; | |
// TASK: Swap children and parent | |
int parentValue = this.data[parentIndex]; | |
this.data[parentIndex] = this.data[index]; | |
this.data[index] = parentValue; | |
// TASK: Recursively do the same thing with new parent | |
bubbleUp(parentIndex); | |
} | |
public int remove() { | |
int minValue = this.data[1]; | |
int lastValue = this.data[this.data[0]--]; | |
this.data[1] = lastValue; | |
this.sinkDown(1); | |
return minValue; | |
} | |
protected boolean isLeaf(int index) { | |
return (index * 2) > this.data[0]; | |
} | |
protected void sinkDown(int index) { | |
// TASK: Check if leaf, if that's the case do nothing | |
if (this.isLeaf(index)) return; | |
// TASK: Initialize children variables | |
int leftChildIndex = index * 2; | |
int rightChildIndex = (index * 2) + 1; | |
int minChildIndex; | |
// TASK: Check if rightChildren doesn't exist, in that case | |
// the minChildIndex is the left, otherwise, find the min children | |
if (rightChildIndex > this.length()) { | |
minChildIndex = leftChildIndex; | |
} | |
else { | |
minChildIndex = (this.data[leftChildIndex] < | |
this.data[rightChildIndex]) ? leftChildIndex : rightChildIndex; | |
} | |
// TASK: stop in case the parent is already smaller than the children | |
if (this.data[index] < this.data[minChildIndex]) return; | |
int childValue = this.data[minChildIndex]; | |
this.data[minChildIndex] = this.data[index]; | |
this.data[index] = childValue; | |
// TASK: apply the same algorithm recursively | |
sinkDown(minChildIndex); | |
} | |
public int minValue() { | |
return this.data[1]; | |
} | |
public int length() { | |
return this.data[0]; | |
} | |
public void printHeapList() { | |
for(int i = 0; i < this.data[0]; i++) { | |
System.out.printf("%d, ", this.data[i]); | |
} | |
System.out.printf("%d\n", this.data[this.data[0]]); | |
} | |
public static void main(String[] args) { | |
Heap h = new Heap(); | |
h.insert(2); | |
h.insert(4); | |
h.insert(1); | |
h.insert(-10); | |
h.printHeapList(); | |
h.remove(); | |
h.printHeapList(); | |
//System.out.printf("%d\n", h.minValue()); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment