heapify
public class Heap{
int cap;
int count;
int [] data;
public Heap(int cap){
this.cap = cap;
this.count = 0;
data = new int[cap + 1];
}
private void swap(int [] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private void shiftUp(int k){
while( k > 1 && data[k/2] < data[k]){
swap(data,k/2,k);
k = k/2;
}
}
public void insert(int num){
data[++count] = num;
shiftUp(count);
}
public int delete(){
int res = data[1];
swap(data,1,count);
count--;
shiftDown(1);
return res;
}
private void shiftDown(int k){
while( 2*k <= count){
int j = 2 * k;
if(2 * k + 1 <= count && data[2 * k + 1] > data[2 * k]){
j = 2 * k + 1;
}
if(data[k] >= data[j]) break;
swap(data,k,j);
k = j;
}
}
// 1
// 2 3
// 4 5
public void heapify(){
int i = count / 2; // first not leaf node
while (i >= 1){
shiftDown(i--);
}
}
public static void main(String[] args) {
Heap heap = new Heap(20);
for (int i = 0; i < 20; i++){
heap.data[i+1] =new Random().nextInt(100);
}
heap.count = 20;
heap.heapify();
for (int i = 0; i < 20;i++ ){
System.out.println(heap.delete());
}
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。