堆

堆是一种特殊的完全二叉树结构, 堆分为大顶堆和小顶堆

大顶堆和小顶堆

大顶堆和小顶堆都是指在堆排序中定义的一种数据结构。它们都是一种特殊的完全二叉树.

大顶堆要求每个节点的值都大于等于它的子节点的值，也就是说堆顶元素是整个堆中最大的元素.

而小顶堆要求每一个节点的值都要小于等于它的子节点的值, 也就是说堆顶元素时整个对重最小的元素.

建堆算法

完全二叉树通常使用数组实现. 每一层的结点按照顺序排列在数组中. 因为堆是一种完全二叉树, 因此也存储在数组中.

我们建堆算法就是对数组进行操作, 建堆算法我目前知道两种.

• 一个是威廉.. 发明的, 主要思路是 将数组元素一个个的插入到大(小)顶堆中, 当元素添加完毕时,堆就建立完毕.时间复杂度为,元素个数 乘以 每个元素其交换的次数(上浮), 时间复杂度为:O(N * logN)

• 另一种是 弗洛伊德的算法在数组中直接进行修改,先找到最后一个非叶子结点, 之后堆每个叶子结点进行 下浮(如果是大顶堆,比较两个子元素中是否右更大的, 有更大的则上浮.) 时间复杂度是, 所有非叶子结点中下浮中 节点交换的次数, 经过计算时间复杂度为: O(N), 相比第一种方式时间复杂度更优.

弗洛伊德建队算法.

/**
     * 初始化堆, 将数组组成一个堆.
     * 算法: 1.找到第一个非叶子结点 2. 对每个叶子结点进行下沉
     * 如果二叉树的根节点从数组0开始, 则第一个非叶子结点为: size/2 -1.
     */
    public void initHeap(){
        int firstParent = size / 2 - 1;
        for(int i = firstParent; i >= 0; i--){
            down(i);
        }
    }

    /**
     * 算法, 建立大顶堆, 比较父节点与两个孩子, 谁更大, 更大的上浮,当前结点下沉
     * @param parent 父节点索引
     */
    public void down(int parent){
        //1. 计算出左右孩子的索引
        int left = parent * 2 +1;
        int right = left + 1;
        int max = parent;
        if(left < size && array[left] > array[max]){
            max = left;
        }
        if(right < size && array[right] > array[max]){
            max = right;
        }
        if(parent != max){
            swap(parent,max);
            down(max);
        }
    }

相关算法

堆排序

如果是升序则使用大顶堆, 降序使用小顶堆. 算法思想:

• 首先根据待排序数组, 建堆,
• 然后设置循环, 不断交换栈顶元素到size-1的位置, 每交换一次size减1, 之后对交换来的元素进行下沉(down函数),来重新跳转堆结构.
• 当size 为1 时, 算法结束

        MaxHeap2 maxHeap2 = new MaxHeap2(nums);
        while(maxHeap2.getSize() > 1){
            maxHeap2.swap(0,maxHeap2.getSize() -1);
            maxHeap2.setSize(maxHeap2.getSize() - 1);
            //下沉
            maxHeap2.down(0);
        }

求数组中第k大的元素

算法思想: 利用小顶堆, 设置小顶堆的容量为k, 这样最多容纳k个元素, 然后栈顶元素就是这k个元素中最小的, 如果我们保证这k个元素就是数组中最大的k个元素, 则堆顶元素就是第k大的元素.

算法步骤:

1. 遍历数组k个元素, 这k个元素之间添加到堆中.
2. 遍历剩余元素.
   • 如果当前元素大于堆顶元素,则替换堆顶元素, 之后对堆顶元素进行下沉(down函数),保持堆的结构
   • 不大于, 则跳过.
3. 取出堆顶元素, 堆顶元素就是第k大的元素

public static int findKthLargest(int[] nums, int k) {
    MinHeap2 heap = new MinHeap2(k);
    //1. 放入前k个元素
    for(int i=0;i<k;i++){
        heap.offer(nums[i]);
    }
    //2. 遍历剩余元素
    for(int i=k;i<nums.length;i++){
        //如果当前元素大于堆顶元素,则replace
        if(nums[i] > heap.peek()){
            heap.replace(nums[i]);
        }
    }
    //3. 返回堆顶元素
    return heap.peek();
}