//删除堆顶元素操作
public int[] deleteMax(int[] array){
//将堆的最后一个元素与堆顶元素交换,堆底元素值设为-99999
array[0] = array[array.length-1];
array[array.length-1] = -99999;
//对此时的根节点进行向下调整
adjustDownToUp(array, 0, array.length);
return array;
}
对堆的插入操作:先将新节点放在堆的末端,再对这个新节点执行向上调整操作。
假设数组的最后一个元素array[array.length-1]为空,新插入的结点初始时放置在此处。
//插入操作:向大根堆array中插入数据data
public int[] insertData(int[] array, int data){
array[array.length-1] = data; //将新节点放在堆的末端
int k = array.length-1; //需要调整的节点
int parent = (k-1)/2; //双亲节点
while(parent >=0 && data>array[parent]){
array[k] = array[parent]; //双亲节点下调
k = parent;
if(parent != 0){
parent = (parent-1)/2; //继续向上比较
}else{ //根节点已调整完毕,跳出循环
break;
}
}
array[k] = data; //将插入的结点放到正确的位置
return array;
}
测试:
public void toString(int[] array){
for(int i:array){
System.out.print(i+" ");
}
}
public static void main(String args[]){
HeapSort hs = new HeapSort();
int[] array = {87,45,78,32,17,65,53,9,122};
System.out.print("构建大根堆:");
hs.toString(hs.buildMaxHeap(array));
System.out.print("\n"+"删除堆顶元素:");
hs.toString(hs.deleteMax(array));
System.out.print("\n"+"插入元素63:");
hs.toString(hs.insertData(array, 63));
System.out.print("\n"+"大根堆排序:");
hs.toString(hs.heapSort(array));
}
1 构建大根堆:122 87 78 45 17 65 53 9 32
2 删除堆顶元素:87 45 78 32 17 65 53 9 -99999
3 插入元素63:87 63 78 45 17 65 53 9 32
4 大根堆排序:9 17 32 45 53 63 65 78 87