大小堆及常用堆算法

大小堆

概念上

• 大顶堆:父节点的值大于等于子节点的值

• 小顶堆:父节点的值小于等于子节点的值

结构上

1. 都是完全二叉树结构
2. 获取最值都是O(1),插入删除都是O(log(n))

使用场景

• 大顶堆:用于快速获取最大值的场景.比如堆排序的升序排序
• 小顶堆:比如优先级队列处理优先级高(权值小)的任务

常用算法

维护堆结构涉及两个个主要方法

• heapify() 建堆,用于堆结构的初始化,采用弗洛伊德算法,从最后一个非叶子节点开始,向前遍历做down
• down() 下潜节点,新增/删除节点后维护堆结构,和左右孩子比较,找到大的做交换,然后递归下潜(大顶堆)

  public static void heapify(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {//最后一个非叶子节点索引为 len*2-1
            down(arr, i);
        }
    }
    
    public static void down(int[] arr, int parent) {
        //1.求出左右孩子索引值
        int lef = 2 * parent + 1;
        int rig = lef + 1;

        //2.比较出最大值
        int max = parent;
        if (lef < arr.length && arr[lef] > arr[max]) {
            max = lef;
        }
        if (rig < arr.length && arr[rig] > arr[max]) {
            max = rig;
        }
        
        //3.交换,递归下潜
        if (max!=parent){
            swap(arr,parent,max);
            down(arr,max);//注意递归位置是满足交换后,此句作为递归的终止条件
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }