public static void main(String[] args){
Scanner in =new Scanner(System.in);
int len = in.nextInt();
ArrayList maxHeap =new ArrayList();
// 初始的数据
for(int i=1;i<=len;i++){
maxHeap.add(in.nextInt());
}
// 过程1(调整法)：调整使其成为一个大顶堆，从最后一个非叶节点开始调整
for(int i= maxHeap.size() /2;i>=1;i--){// 注意边界
heapDown(maxHeap,i,maxHeap.size());
}
// 输出大顶堆
System.out.print("大顶堆为：");
for(int i=0;i
System.out.print(maxHeap.get(i)+" ");
}
// 过程2：在大顶堆中插入数字
insert(maxHeap,10);
System.out.print("插入数字后大顶堆为：");
for(int i=0;i
System.out.print(maxHeap.get(i)+" ");
}
// 过程3：从大顶堆中删除数字
delete(maxHeap,2);
System.out.print("删除数字后大顶堆为：");
for(int i=0;i
System.out.print(maxHeap.get(i)+" ");
}
// 过程4：对大顶堆进行排序
sort(maxHeap);
System.out.print("排序后数组：");
for(int i=0;i
System.out.print(maxHeap.get(i)+" ");
}
}
public static int left(int index){// 注意边界
return 2*index +1;
}
public static int right(int index){
return 2*index +2;
}
public static int parent(int index){
return (index -1) /2;
}
//过程2： 向最大堆中插入数据
public static void insert(ArrayList maxHeap,int value){
maxHeap.add(value);
heapUp(maxHeap,maxHeap.size()-1);
}
//过程2：把"插入"的元素上浮
public static void heapUp(ArrayList maxHeap,int index){
if(index >0){
// 求出其父亲节点
int parent =parent(index);
int parentValue = maxHeap.get(parent);
int indexValue = maxHeap.get(index);
// 如果父亲节点的值小于index节点的值，交换两者的位置
if(indexValue > parentValue){
Collections.swap(maxHeap, parent, index);
heapUp(maxHeap,parent);
}
}
}
//过程3：把最大堆中的某个元素删除
public static void delete(ArrayList maxHeap,int index){
// 把最后的一个叶子的数值赋值给index位置
maxHeap.set(index,maxHeap.get(maxHeap.size()-1));
maxHeap.remove(maxHeap.size()-1); // 移除
// 下沉操作
heapDown(maxHeap,index, maxHeap.size());
}
//过程3："下沉"操作
public static void heapDown(ArrayList maxHeap,int index, int size){
// 记录较大的儿子的位置
int largeChild;
int lchild =left(index);
int rchild =right(index);
if(lchild >= size){// 说明该节点没有左右儿子节点了，则返回
return;
}
if(rchild < size && maxHeap.get(lchild) < maxHeap.get(rchild)){// 右儿子在并且大
largeChild = rchild;
}else{
largeChild = lchild;
}
// 交换和递归
if(maxHeap.get(largeChild)>maxHeap.get(index)){
Collections.swap(maxHeap, largeChild, index);
heapDown(maxHeap, largeChild, size);
}
}
//程序4：对大顶堆进行排序
public static void sort(ArrayList maxHeap){
for(int i = maxHeap.size()-1;i>=0;i--){
Collections.swap(maxHeap, 0, i);
heapDown(maxHeap,0,i);
}
}
