题解 | #【模板】堆#

总结：
1.堆插入元素时，从下往上调整，由于相邻子树已经是大根堆，只需要不断与父节点比较大小，将大的节点和父节点互换，直到到达根节点或小于父节点即可结束。
2.堆删除元素时，为避免破坏ArrayList中堆的结构，可以将堆顶元素替换为最后一个元素，然后删除掉最后一个元素。堆删除元素后从上往下调整堆结构，将左右子节点中较大的节点与根节点互换，之后再递归调整该节点所在子树即可。由于堆结构未破坏，故其他结构不需要改变，节约了时间。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n =Integer.parseInt(sc.nextLine());
        MaxHeap maxHeap = new MaxHeap();
        for(int i=0;i<n;i++){
            String[] line = sc.nextLine().split(" ");
            if(line[0].equals("push"))
                maxHeap.push(Integer.parseInt(line[1]));
            else if(line[0].equals("top"))
                maxHeap.top();
            else if(line[0].equals("pop"))
                maxHeap.pop();
        }
    }
}
class MaxHeap{
    private ArrayList<Integer> list = new ArrayList<>();
    public MaxHeap(){
        list.add(0);
    }
    public void push(int val){
        list.add(val);
        int len = list.size()-1;
        while(list.get(len)>list.get(len/2)){
            if(len==1)
                break;
            swap(len,len/2);
            len = len/2;
        }
    }
    public void top(){
        int len = list.size()-1;
        if(len==0)
            System.out.println("empty");
        else
            System.out.println(list.get(1));
    }
    public void pop(){
        int len = list.size()-1;
        if(len==0)
            System.out.println("empty");
        else{
            System.out.println(list.get(1));
            list.set(1,list.get(len));
            list.remove(len);
            HeapAdjust(1,len-1);
        }

    }
    public void HeapAdjust(int index,int len){
        int left = index*2;
        int maxIndex = 0;
        while(left<=len){
            if(left+1<=len)
               maxIndex = list.get(left)>list.get(left+1)?left:left+1;
            else
                maxIndex=left;
            if(list.get(index)>list.get(maxIndex))
                break;
            swap(index,maxIndex);
            index = maxIndex;
            left = 2*index;
        }

    }
    public void swap(int l1,int l2){
        int tmp = list.get(l1);
        list.set(l1,list.get(l2));
        list.set(l2,tmp);
    }

}