import java.util.ArrayList;
import java.util.List;
public class MinHeap<E extends Comparable<E>> {
List<E> h = new ArrayList<E>();
public MinHeap(E[] keys) {
for (E key : keys) {
h.add(key);
}
for (int k = h.size() / 2 - 1; k >= 0; k--) {
percolateDown(k, h.get(k));
}
}
public void add(E node) {
h.add(null);
int k = h.size() - 1;
while (k > 0) {
int parent = (k - 1) / 2;
E p = h.get(parent);
if (node.compareTo(p) >= 0) {
break;
}
h.set(k, p);
k = parent;
}
h.set(k, node);
}
public E remove() {
E removedNode = h.get(0);
E lastNode = h.remove(h.size() - 1);
percolateDown(0, lastNode);
return removedNode;
}
public E min() {
return h.get(0);
}
public boolean isEmpty() {
return h.isEmpty();
}
void percolateDown(int k, E node) {
if (h.isEmpty()) {
return;
}
while (k < h.size() / 2) {
int child = 2 * k + 1;
if (child < h.size() - 1
&& h.get(child).compareTo(h.get(child + 1)) > 0) {
child++;
}
if (node.compareTo(h.get(child)) <= 0) {
break;
}
h.set(k, h.get(child));
k = child;
}
h.set(k, node);
}
// Usage example
public static void main(String[] args) {
MinHeap<Integer> heap = new MinHeap<Integer>(
new Integer[] { 2, 5, 1, 3 });
// print keys in sorted order
while (!heap.isEmpty()) {
System.out.println(heap.remove());
}
}
}
Popular Posts
-
Given the sequence S1 = {a,b,c,d,…,x,y,z,aa,ab,ac…. } and given that this sequence corresponds (term for term) to the sequence S2 = {0,1...
-
Given a binary matrix, find out the maximum size square sub-matrix with all 1s. Algorithm: Let the given binary matrix be M[R][C]. The idea ...
-
The bustling town of Siruseri has just one sports stadium. There are a number of schools, colleges, sports associations, etc. that use this ...
-
Refer : http://education.cdacmumbai.in/education/pgdst/dsalfac/notes/ShellSort.pdf Shellsort works by comparing elements that are distant r...
-
Many of you might not be knowing that if you have 1 gmail id … you have infinte gmail ids… Seems to be a joke.. It’s not actually… for e.g ...
-
How to find kth smallest element in BST . you cannot use static/global variable and you cannot pass value of k to any function ? Solution ...
-
Find the maximum rectangle (in terms of area) under a histogram in linear time. I mean the area of largest rectangle that fits entirely in t...
-
There is an integer array consisting positive and negative integers. Find maximum positive difference S defined as: O(N) solution S = a[i] ...
-
Q: Given an integer x and an unsorted array of integers, describe an algorithm to determine whether two of the numbers add up to x. If we ha...
-
http://effprog.blogspot.com/2011/02/duplicate-removal-in-binary-search-tree.html http://shashank7s.blogspot.com/2011/03/write-program-to-rem...
Sunday, March 27, 2011
Min Heap implementation in java
Labels:
Arrays
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment