日期:2014-05-20 浏览次数:20783 次
public class StaticHeap implements Cloneable{
/*
This heap has a root at the INDEX_1, which refers to the minimum.
And this heap is STATIC, as means that its volume is limited.
*/
private final int MAX_VOLUME = 250000;
private int heapSize = 0;
private int[] heap = new int[MAX_VOLUME];
public StaticHeap(){
heap[0] = Integer.MIN_VALUE;
}
public StaticHeap(int[] input){
heap[0] = Integer.MIN_VALUE;
for (int i = 0; i < input.length; i++)
this.insert(input[i]);
}
private int parent(int i){
return i/2;
}
private int leftSon(int i){
return i*2;
}
private int rightSon(int i){
return i*2+1;
}
private void swap(int i, int j){
int tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
}
private void update(int i){
while (heap[i] < heap[parent(i)]){
swap(i, parent(i));
i = parent(i);
}
}
private void heapify(int i){
int l = leftSon(i);
int r = rightSon(i);
if (l <= heapSize && heap[l] < heap[i] && heap[l] <= heap[r]){
swap(i, l);
heapify(l);
}
if (r <= heapSize && heap[r] < heap[i] && heap[l] > heap[r]){
swap(i, r);
heapify(r);
}
}
public void insert(int x){
heap[++heapSize] = x;
update(heapSize);
}
public boolean deleteMin(){
if (heapSize == 0) return false;
heap[1] = heap[heapSize--];
if (heapSize > 0) heapify(1);
return true;
}
public int getSize(){
return heapSize;
}
public int getMin(){
return heap[1];
}
public Object clone() throws CloneNotSupportedException{
return super.clone();
}
public int[] sortedArray() throws CloneNotSupportedException{
StaticHeap newHeap = (StaticHeap)this.clone();
int[] result = new int[newHeap.heapSize];
int n = 0;
while (newHeap.heapSize > 0){
result[n++] = newHeap.getMin();
newHeap.deleteMin();
}
return result;
}
}