/**
 * 基于整形最大堆實(shí)現(xiàn)
 * 時(shí)根節(jié)點(diǎn)從0開始編號,若此時(shí)節(jié)點(diǎn)編號為k
 * 左孩子為2k+1
 * 右孩子為2k+2
 * 父節(jié)點(diǎn)為（k-1）/2
 */
 
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
 
public class MaxHeap {
    // 使用JDK的動(dòng)態(tài)數(shù)組(ArrayList)來存儲一個(gè)最大堆
    List<Integer> data;
 
    // 構(gòu)造方法的this調(diào)用
    public MaxHeap(){
        this(10);
    }
    
    // 初始化的堆大小
    public MaxHeap(int size){
        data = new ArrayList<>(size);
    }
 
    /**
     * 將任意數(shù)組堆化
     * @param arr
     */
    public MaxHeap(int[] arr){
        data = new ArrayList<>(arr.length);
        // 1.先將arr的所有元素復(fù)制到data數(shù)組中
        for(int i : arr){
            data.add(i);
        }
        // 2.從最后一個(gè)非葉子結(jié)點(diǎn)開始進(jìn)行siftDown
        for (int i = parent(data.size()-1); i >=0 ; i--) {
            siftDown(i);
        }
    }
 
    /**
     * 向最大堆中增加值為Value的元素
     * @param value
     */
    public void add(int value){
        //1.先直接加到堆的末尾
        data.add(value);
        //2.元素上浮操作
        siftUp(data.size()-1);
    }
 
    /**
     * 只找到堆頂元素值
     * @return
     */
    public int peekMax (){
        if(isEmpty()){
            throw new NoSuchElementException("heap is empty!connot peek");
        }
        return data.get(0);
    }
 
    /**
     * 取出當(dāng)前最大堆的最大值
     */
    public int extractMax(){
        // 取值一定注意判空
        if(isEmpty()){
            throw new NoSuchElementException("heap is empty!connot extract");
        }
        int max = data.get(0);
        // 1.將數(shù)組末尾元素頂?shù)蕉秧?
        int lastValue =data.get(data.size()-1);
        data.set(0,lastValue);
        // 2.將數(shù)組末尾的元素刪除
        data.remove(data.size()-1);
        // 3.進(jìn)行元素的下沉操作
        siftDown(0);
        return max;
    }
 
    /**
     * 下沉操作
     */
    public void siftDown(int k){
        //還存在子樹
        while (leftChild(k) < data.size()){
            int j = leftChild(k);
            //判斷是否存在右子樹且大于左子樹的值
            if(j+1 < data.size() && data.get(j+1) > data.get(j)){
                j=j+1;
            }
            //此時(shí)j為左右子樹最大值
            //和當(dāng)前節(jié)點(diǎn)比較大小
            if(data.get(j) <= data.get(k)){
                break;
            }else {
                swap(k,j);
                k=j;
            }
        }
    }
 
    /**
     * 上浮操作
     */
    // 上浮操作的終止條件: 已經(jīng)走到根節(jié)點(diǎn) || 當(dāng)前節(jié)點(diǎn)值 <= 父節(jié)點(diǎn)值
    // 循環(huán)的迭代條件 : 還存在父節(jié)點(diǎn)并且當(dāng)前節(jié)點(diǎn)值 > 父節(jié)點(diǎn)值
    private void siftUp(int k) {
        while (k>0 && data.get(k)>data.get(parent(k))){
            swap(k,parent(k));
            k=parent(k);
        }
    }
 
    //交換三連
    private void swap(int i,int j) {
        int temp = data.get(j);
        data.set(j,data.get(i));
        data.set(i,temp);
    }
 
    //判讀堆為空
    public boolean isEmpty(){
        return data.size() == 0;
    }
    //根據(jù)索引找父節(jié)點(diǎn)
    public int parent(int k){
        return (k-1)>>1;
    }
    //根據(jù)索引找左孩子
    public int leftChild(int k){
        return k<<2+1;
    }
    //根據(jù)索引找右孩子
    public int rightChild(int k){
        return k<<2+2;
    }
 
    @Override
    public String toString() {
        return data.toString();
    }
}

        int[] data=new int[10000];
        //隨機(jī)數(shù)
        ThreadLocalRandom random = ThreadLocalRandom.current();
        for (int i = 0; i < data.length; i++) {
            data[i] = random.nextInt();
        }