- 首页 > it技术 > >
public class MinHeap { private int[] heap;
private int length;
public MinHeap(int[] arr){
if(arr.length<=0){
throw new IllegalArgumentException("array length illegal");
}
heap = new int[arr.length];
System.arraycopy(arr, 0, heap, 0, arr.length);
length = arr.length;
createHeap();
} private void createHeap(){
//从倒数第一个非叶节点的节点开始，向下调整，构建小根堆
for(int i=length/2-1;
i>=0;
i--){
fixDown(i);
}
System.out.println(Arrays.toString(heap));
} private void fixUp(int index){
int c = index;
int p = (index-1)/2;
int tmp = heap[index];
while(p>=0){
if(heap[p]<=tmp){
break;
}else{
heap[c] = heap[p];
c=p;
p = (p-1)>>1;
}
}
heap[c] =tmp;
} private void fixDown(int index){
int p =index;
int c = index*2+1;
int tmp =heap[index];
while(c heap[c+1]){
c++;
}if(heap[c]>=tmp&&heap[c]>=tmp){
break;
}else{
heap[p] = heap[c];
p = c;
c = 2*c+1;
}
}
heap[p] = tmp;
}
//用最后一个节点覆盖要删除的节点，从删除节点的位置向下调整
public int delete(int index){
if(index>=length){
throw new IllegalArgumentException("index out of bound");
}
int ret = heap[index];
heap[index] = heap[length-1];
length--;
fixDown(index);
return ret;
} //添加到最后的位置，然后从最后的位置向上调整
public void add(int value){
if(length==heap.length){
int[]tmp = new int[length+16];
System.arraycopy(heap, 0, tmp, 0,length);
this.heap = tmp;
}
heap[length]=value;
fixUp(length);
length++;
} //删除第一个几点，每删除一次，从头开始向下调整
public int pop(){
int ret=heap[0];
heap[0] = heap[length-1];
length--;
fixDown(0);
return ret;
}
public static void main(String[] args) {
MinHeap heap = new MinHeap(new int[]{10,2,62,85,2,4,23,222,3,1});
heap.delete(0);
int l=heap.length;
for(int i=0;
i
推荐阅读
