重温《数据结构与算法》之堆与堆排序

末蓝、 2021-08-29 12:02 324阅读 0赞

时间复杂度：[https://blog.csdn.net/fugitive1/article/details/92656373][https_blog.csdn.net_fugitive1_article_details_92656373]

[https://blog.csdn.net/YuZhiHui\_No1/article/details/44258297][https_blog.csdn.net_YuZhiHui_No1_article_details_44258297]

### 1. 堆 ###

二叉树可以被细分为普通二叉树、满二叉树、完全二叉树，而今天所分享的堆这种数据结构就是一种完全二叉树。

堆中的每个结点的值要么都大于左右子结点的值，要么都小于左右子结点的值。前者形成的是大顶堆，即堆顶元素是最大的；后者形成的是小顶堆，即堆顶元素是最小的。如下图所示，分表是一个大顶堆和小顶堆。

![format_png][]

堆

> ❝
> 
> 完全二叉树的特点是：最后一层的叶子结点靠左排列，从根结点到倒数第二层结点，是一颗满二叉树。通常储存二叉树这种数据结构的方法有链式存储和顺序存储，链式存储就是通过指针来维护左右子结点的关系，而顺序存储就是利用数组来存储。完全二叉树最适合用数组来存储，即堆这种数据结构适合用数组来存储。
> 
> ❞

当用数组来存放堆元素时，如果堆顶的元素存放在索引为 1 的地方（不从 0 开始），那么左节点的索引为 2，右结点的索引为 3。也就是是说，如果父结点存放在数组索引为 i 的地方，那么左结点存放的位置为 2\*i，右结点存放的位置为 2\*i+1。

下面看下堆的常用操作：插入数据和删除堆顶数据

1.1 插入数据

以大顶堆为例，当向堆中插入数据时，新插入的数据首先放在数组的最后面，由于是大顶堆，而新插入的数据可能比父结点的值大，因此会出现不满足大顶堆性质的情况，这个时候需要调整数据的位置，这个过程，叫做堆化（heapify）。（堆化分两种：**「向下堆化和向上堆化」**，此时是向上堆化）

![format_png 1][]

下面看下代码实现。

public class Heap {
    
        private int[] heap; // 存放数据
        private int capacity;   // 堆的最大容量
        private int count;  // 堆中目前存放的数据个数
    
        public Heap(int capacity) {
            this.heap = new int[capacity + 1];    // 数组下标为0的地方不存放元素（这样计算左右子结点的位置的时候，方便表示）
            this.capacity = capacity;
            this.count = 0;
        }
    
        public void insert(int data) {
            if (count >= capacity) return; // 堆满了
            count++;
            heap[count] = data;
            int i = count;
            while (i / 2 > 0 && heap[i] > heap[i / 2]) {    // 如果子结点的数据比父结点大，就堆化，交换位置
                swap(heap, i, i / 2);    // 交换数据
                i = i / 2;
            }
        }
    
        // 交换下标a1和下标a2的数据
        private static void swap(int[] heap, int a1, int a2) {
            // 不借助额外的内存空间，来交换两个数
            heap[a1] = heap[a1] ^ heap[a2];
            heap[a2] = heap[a1] ^ heap[a2];
            heap[a1] = heap[a1] ^ heap[a2];
            /**
             * 上面三行代码等价于这几行代码
             * int tmp = heap[a2];
             * heap[a2] = heap[a1];
             * heap[a1] = tmp
             */
        }
    
    }

1.2 删除堆顶数据

还是以大顶堆为例，当要删除堆中最大的元素时，其实就是删除堆顶元素。删除完堆顶元素后，需要从堆中找出一个最大的元素放到堆顶。这个时候，通常是将数组中最后一个数据放到堆顶，由于这个数据可能不是最大的，因此也需要进行堆化，此时通常采用向下堆化的手段。代码实现如下：

// 删除最大元素
    public void deleteMax() {
        if (count == 0) return; // 空堆
        heap[1] = heap[count];
        count--;
        heapify(heap, 1, count);   // 从上往下堆化
    }
    
    // 堆化
    private static void heapify(int[] heap, int i, int count) {
        while (2 * i <= count) {
            int maxIndex = i;
            if (heap[i] < heap[2 * i]) maxIndex = 2 * i;     // 和左结点比较
            if ((2 * i + 1) <= count && heap[2 * i + 1] > heap[2 * i]) maxIndex = 2 * i + 1;    // 如果右结点更大，则和右结点交换
            if (maxIndex == i) return;  // 如果左右子结点均小于当前结点，就表示不需要堆化了，直接返回
            swap(heap, i, maxIndex);    // 交换数据
            i = maxIndex;
        }
    }

### 2. 堆排序 ###

堆顶的元素要么是最大的，要么是最小的，如果我们每次从堆顶取一个元素，那么每次取到的数据就是最大或者最小，依次取完，那么取出来的数据就是有序的了。

使用堆排序有一个优点，就是**「不需要额外的内存空间」**，直接基于原数组，就可以完成排序操作。

堆排序大概分为两个步骤：**「建堆和排序」**。建堆是指根据指定的数组，将其变为满足堆这种数据结构的数据。建堆的思路有两种，一种是从下往上建堆（前面的插入数据过程就是从下往上建堆），一种是从上往下建堆。下面以从上往下建堆为例，构建一个大顶堆，示例代码如下。

// 建堆（从上往下建堆）
    public static int[] buildHeap(int[] a) {
        int length = a.length;
        // 数组a的下标为0的地方不存放元素
        for (int i = length / 2; i >= 1; i--) {  // 叶子结点不需要堆化，因为叶子结点下面是没有左右子结点的，无法向下堆化
            heapify(a, i, length - 1);
        }
        return a;
    }

在从上往下建堆的过程中，叶子结点是不需要堆化，因为叶子结点下面是没有左右子结点的，无法向下堆化。

接下来是排序过程，排序过程中，由于是大顶堆，所以将堆顶元素与数组最后的元素交换，然后刨去数组最后一个元素，将剩余元素进行堆化，循环遍历，这样数组就是变成从小到大排列的有序数组了。示例代码如下：

// 排序
    public static void sort(int[] a) {
        a = buildHeap(a);   // 先建堆
        int i = a.length - 1;
        while (i > 1) {
            swap(a, 1, i);  // 将第一个数放到数组后面
            i--;
            heapify(a, 1, i);  // 堆化
        }
    }

### 3. 能用堆解决的问题 ###

堆的应用十分广泛，例如 Top K 这一系类的问题，都能用堆来解决。假如现在有 10 亿数据，要取其中最大的 10 个数据，如果我们对这 10 亿个数据都进行排序，肯定能得到结果，但是数据量太大，如果都进行排序就会非常耗 CPU，而且我们只需要其中的 10 个数据，对所有数据排序，显然有点太浪费了。如果用堆来解决，我们可以建立一个可以存放 10 个数据的**「小顶堆」**，在初始时，可以先一次放入 10 个数据，后面在遍历剩下的数据时，判断是不是比堆顶的元素大，如果大，就将现在的堆顶元素删除，然后将当前数据放入到堆中；如果小于或者等于，则不做任何操作，这样最终就能得到这 10 亿个数据中最大的 10 个数据了。

另外，定时任务也可以用堆来实现。每个任务会在指定的时间来执行，这个时候，可以将任务达到时间最小的任务放到小顶堆的堆顶，那么每次执行时，就取堆顶的任务执行即可。

堆还可以用来实现优先级队列。在优先级队列中，每次从队列中取出的元素肯定是优先级最低或者最高的元素，这恰好与堆中的小顶堆和大顶堆对应。在 Java 中提供了工具类 PriorityQueue 来实现优先级队列，下一篇文章将结合 PriorityQueue 的源码来分析一下堆在 Java 中的应用。

### 4. 总结 ###

总结一下，堆是一棵完全二叉树，它适合采用数组来存储数据。大顶堆的堆顶元素是堆中最大的元素，小顶堆中的堆顶元素是堆中最小的元素。

采用堆这种数据结构，对数据进行排序时，不需要占用额外的存储空间，效率也很高，时间复杂度为 O(nlogn)。

在文中的例子中，在使用数组存储堆的数据时，将数组下标为 0 的位置，没有存储元素，这是为了方便计算左右子结点的位置。实际上，下标为 0 的位置也可以用来存放元素，不同的是，计算左右子结点的位置的公式变了。

[https_blog.csdn.net_fugitive1_article_details_92656373]: https://blog.csdn.net/fugitive1/article/details/92656373
[https_blog.csdn.net_YuZhiHui_No1_article_details_44258297]: https://blog.csdn.net/YuZhiHui_No1/article/details/44258297
[format_png]: /images/20210527/aa4e8177e7bc4fcdaffc6e14c2b341b1.png
[format_png 1]: /images/20210527/fe99757f987d4e1891aaf758a6b34c5c.png