二插堆的性质

image.png

完全二叉树的节点数量为n，节点编号为[0,n-1]，则：

1. 节点i的父节点是 floor((i-1)/2)
2. 节点i的左子节点是2i+1，左子节点是2i+2
3. 则最后一个非叶子节点的编号为floor(n/2)-1

批量建堆

参考恋上数据结构与算法

public class Solution {
    public static void main(String[] args) {
        Solution obj = new Solution();
        int[] nums = {30,34,73,60,68,43};
        obj.buildMaxHeap(nums);

    }

    public void buildMaxHeap(int[] nums){
        int n = nums.length;
        //自下而上的下滤
//        for(int i=n/2-1;i>=0;i--){
//            siftDown(nums, i);
//        }
        //自上而下的上滤
        for(int i=1;i<n;i++){
            siftUp(nums, i);
        }
    }

    public void siftUp(int[] nums, int index){
        int n = nums.length;
        int element = nums[index];

        while(index > 0){
            int parentIdx = (index-1)/2;
            int parent = nums[parentIdx];
            if(parent<element){
                nums[index] = parent;
                index = parentIdx;
            }else{
                break;
            }
        }
        nums[index] = element;
    }

    public void siftDown(int[] nums, int index){
        int n = nums.length;
        int element = nums[index];

        while(2*index+1<n){
            int childIdx = 2*index+1;
            int child = nums[childIdx];
            if(2*index+2<n){
                int rightIdx = 2*index+2;
                int right = nums[rightIdx];
                if(right>child){
                    child=right;
                    childIdx=rightIdx;
                }
            }
            if(child>element){
                nums[index] = child;
                index = childIdx;
            }else{
                break;
            }
        }
        nums[index] = element;
    }
}

添加

新节点添加在最后，然后对这个节点做上滤。

删除

二叉堆只能删除第一个节点（下标为0的节点），把最后一个节点移到第一个节点的位置，然后对第一个节点做下滤。