算法-堆结构和堆排序

本节大纲

1. 堆结构

堆结构是为集合类里面的优先级队列来服务的
优先级队列其实就是顺序存储的二叉树结构, 我们的底层的源码里面是没有链式存储的二叉树的,二叉树的实现的细节是通过我们的数组来模拟实现的
底层的实现细节 :
数组加上一个usedSize就可以实现一个顺序存储的二叉树结构

堆的调整
堆的调整分为向上调整与向下调整, 请注意, 堆的每次调整都是基于其中
的某一个元素破坏了堆的结构, 但是其他的堆的性质没有发生改变的情况下,所以请注意, 一定是一个元素

堆的向上调整 : 该调整不用传入终止条件, 因为根节点的下标就是天然的终止条件, 从下面的条件里面我们可以发现, 根节点的父亲节点就是其本身

代码实现如下:

 /**
     * 堆的调正是整个堆操作的最重要的步骤(这里我们默认实现的是大根堆)
     * --> 根据之前我们学习堆结构时期的困惑, 不管是向上调整还是向下调整,都是因为只有某个位置的元素破坏了堆的结构, 切记是一个! ! !
     *
     * @param nums : 传入的需要调整的数组
     * @param i    : 待调整元素的下标
     *             向上调整不需要设置终点位置, 因为就是根节点自己 当 i == 0是时, (i - 1) / 2 == 0,自动跳出循环
     */
    private void heapInsert(int[] nums, int i) {
        while (nums[i] > nums[(i - 1) / 2]) {
            swap(nums, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

堆的向下调整 : 这个就跟向上调整不一样了, 这个没有天然的终止条件, 可以认为的传入终止条件…

代码实现如下

/**
     * 这里跟上面的向上调整的类似的,我们都是只有其中的一个元素破坏了堆的结构(默认实现大根堆)
     *     之前我们没有理解向上调整跟向下调整的原因就是,我们忽略了只有一个元素破坏了堆结构这一条件
     * @param nums : 待调整的数组
     * @param i    : 待调整的元素的下标
     * @param end  : 结束位置
     */
    private void heapify(int[] nums, int i, int end) {
        int l = 2 * i + 1; //先把孩子下标打到左孩子的位置;
        while (l < end) {
            //下面这句话的代码逻辑是 --> 找到最大孩子的孩子下标
            int best = l + 1 < end && nums[l + 1] > nums[l] ? l + 1 : l;
            //下面这句话的代码逻辑是 --> 比较最大的孩子跟父节点
            best = nums[i] < nums[best] ? best : i;
            if (best == i) {
                break;
            }
            swap(nums, best, i);
            i = best;
            l = 2 * i + 1;
        }
    }

堆的调整的时间复杂度分析 --> 堆的调整的时间复杂度是O(LogN), 依据的是二叉树的树的高度

2. 堆排序

堆排序其实就是堆结构的应用, 原理就是(这里按照升序分析) :
传入一个数组然后建堆(可以从顶部到底部建堆, 也可以反着来)
两种建堆的时间复杂度是不一样的, 等一下详细的说明一下
堆建立完毕之后, 我们将顶部元素跟最后一个元素进行交换,
控制最后一个范围的位置, 然后向下调整, 循环下去…

堆排序的原理就是上面所说的那样, 实现的逻辑见下
从顶部向下建堆

 //堆排序的从上往下建堆的实现方式
    public void heapSort(int[] nums){
        //首先需要的是建堆
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            heapInsert(nums,i);
        }

        //建堆完毕之后, 进行堆排序的过程
        while(len > 0){
            swap(nums,0,--len);
            heapify(nums,0,len);
        }
    }

上面的从上往下建堆的时间复杂度是O(NLogN)
这个数学证明我们就不说了
大概原理就是 : log1 + log2 + log3 +…+ logN 收敛于NLogN
但是下面进行交换排序的时间复杂度是一定是O(N*LogN)

堆排序的从底部向上建堆的代码实现

  //从顶部向下建堆的方式
    public void heapSort1(int[] nums) {
        //建堆成功
        for (int pra = (nums.length - 1 - 1) / 2; pra >= 0; pra--) {
            heapify(nums,pra,nums.length);
        }

        //建堆完毕之后, 进行堆排序的过程
        int len = nums.length;
        while (len > 0) {
            swap(nums, 0, --len);
            heapify(nums, 0, len);
        }
    }

为什么说从底部向上建堆的时间复杂度更好
每一层累加起来其实是一个差比数列求和公式
下图左边的是看的节点的规模, 右侧的是向下调整的层数

本节的代码实现合集

/**
 * 下面我们自己实现一个堆
 */
class Heap {
    int[] elem;
    int usedSize;
    private static final int DEFAULT_CAPACITY = 11;//底层默认是11

    //提供两个构造方法
    public Heap() {
        this(DEFAULT_CAPACITY);
    }

    public Heap(int initCapacity) {
        elem = new int[initCapacity];
    }

    /**
     * 建堆的时候, 我们尝试直接用数组来模拟实现大根堆
     * 之前我们一直不理解, 为什么建堆要从后往前逐一的向下调整,
     * 现在明白了,因为这样才能保证每次调整完毕之后下一次调整的时候只有一个顶部元素是不确定的
     *
     * @param nums
     */
    public Heap(int[] nums) {
        //空间不够就进行扩容(我们现在实现的这个只是简单的版本,可能会因为空间不足的bug)
        this(DEFAULT_CAPACITY);
        if (elem.length <= nums.length) {
            this.elem = Arrays.copyOf(elem, elem.length * 2);
        }

        //进行拷贝元素
        for (int i = 0; i < nums.length; ++i) {
            elem[i] = nums[i];
        }
        usedSize = nums.length;

        //下面就进行建堆的过程
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; --parent) {
            heapify(elem, parent, usedSize);
        }
    }

    /**
     * 堆的调正是整个堆操作的最重要的步骤(这里我们默认实现的是大根堆)
     * --> 根据之前我们学习堆结构时期的困惑, 不管是向上调整还是向下调整,都是因为只有某个位置的元素破坏了堆的结构, 切记是一个! ! !
     *
     * @param nums : 传入的需要调整的数组
     * @param i    : 待调整元素的下标
     *             向上调整不需要设置终点位置, 因为就是根节点自己 当 i == 0是时, (i - 1) / 2 == 0,自动跳出循环
     */
    private void heapInsert(int[] nums, int i) {
        while (nums[i] > nums[(i - 1) / 2]) {
            swap(nums, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }


    /**
     * 这里跟上面的向上调整的类似的,我们都是只有其中的一个元素破坏了堆的结构(默认实现大根堆)
     * 之前我们没有理解向上调整跟向下调整的原因就是,我们忽略了只有一个元素破坏了堆结构这一条件
     *
     * @param nums : 待调整的数组
     * @param i    : 待调整的元素的下标
     * @param end  : 结束位置
     */
    private void heapify(int[] nums, int i, int end) {
        int l = 2 * i + 1; //先把孩子下标打到左孩子的位置;
        while (l < end) {
            //下面这句话的代码逻辑是 --> 找到最大孩子的孩子下标
            int best = l + 1 < end && nums[l + 1] > nums[l] ? l + 1 : l;
            //下面这句话的代码逻辑是 --> 比较最大的孩子跟父节点
            best = nums[i] < nums[best] ? best : i;
            if (best == i) {
                break;
            }
            swap(nums, best, i);
            i = best;
            l = 2 * i + 1;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


    /**
     * 下面是简单的删除操作
     */
    public void poll() {
        swap(elem, 0, usedSize - 1);
        usedSize--;
        heapify(elem, 0, usedSize);
    }

    /**
     * 一些其他的操作
     */
    public int peek() {
        return elem[0];
    }

    //展示的操作
    public void show() {
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();
    }

    //堆排序的从上往下建堆的实现方式
    public void heapSort(int[] nums) {
        //首先需要的是建堆
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            heapInsert(nums, i);
        }

        //建堆完毕之后, 进行堆排序的过程
        while (len > 0) {
            swap(nums, 0, --len);
            heapify(nums, 0, len);
        }
    }

    //从顶部向下建堆的方式
    public void heapSort1(int[] nums) {
        //建堆成功
        for (int pra = (nums.length - 1 - 1) / 2; pra >= 0; pra--) {
            heapify(nums,pra,nums.length);
        }

        //建堆完毕之后, 进行堆排序的过程
        int len = nums.length;
        while (len > 0) {
            swap(nums, 0, --len);
            heapify(nums, 0, len);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5, 8, 6, 7, 3, 1, 9, 2, 7, 1, 4, 6};
        Heap heap = new Heap(nums);
        heap.heapSort1(nums);
        System.out.println(Arrays.toString(nums));
    }
}