【数据结构与算法】堆

╰+哭是因爲堅強的太久メ 2022-11-30 04:18 238阅读 0赞

#### 一：如何理解“堆” ####

**1，堆是一个完全二叉树；**  
完全二叉树要求除了最后一层，其他层的节点都是满的，最后一层的节点都靠左排列。  
2，堆中每个节点都必须大于等于（或小于等于）其子树中每个节点的值。  
堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。  
3，对于每个节点的值都大于等于子树中每个节点值的堆，叫作“**大顶堆**”。对于每个节点的值都小于等于子树中每个节点值的堆，叫“**小顶堆**”。

### 二：如何实现“堆” ###

要实现一个堆，要先知道堆都支持哪些操作，已及如何存储一个堆。  
**1，如何存储一个堆**：  
完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

**2，往堆中插入一个元素**  
往堆中插入一个元素后，需要继续满足堆的两个特性  
（1）如果把新插入的元素放到堆的最后，则不符合堆的特性了，于是需要进行调整，让其重新满足堆的特性，这个过程叫做 **堆化（heapify）**  
（2）堆化实际上有两种，从下往上和从上往下  
（3）从下往上的堆化方法：  
堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

public class Heap { 
      private int[] a; // 数组，从下标1开始存储数据
      private int n;  // 堆可以存储的最大数据个数
      private int count; // 堆中已经存储的数据个数
    
      public Heap(int capacity) { 
        a = new int[capacity + 1];
        n = capacity;
        count = 0;
      }
    
      public void insert(int data) { 
        if (count >= n) return; // 堆满了
        ++count;
        a[count] = data;
        int i = count;
        while (i/2 > 0 && a[i] > a[i/2]) {  // 自下往上堆化
          swap(a, i, i/2); // swap()函数作用：交换下标为i和i/2的两个元素
          i = i/2;
        }
      }
     }

**3，删除堆顶元素 从上往下**

（1）从堆的定义的第二条中，任何节点的值都大于等于（或小于等于）子树节点的值，则堆顶元素存储的就是堆中数据的最大值或最小值。  
（2）假设是大顶堆，堆堆顶元素就是最大的元素，但删除堆顶元素之后，就需要把第二大元素放到堆顶，那第二大元素肯定会出现在左右子节点中。然后在迭代地删除第二大节点，以此类推，直到叶子节点被删除。  
但这种方式会使堆化出来的堆不满足完全二叉树的特性  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]

（3）可以把最后一个节点放到堆顶，然后利用同样的父子节点对比方法，对于不满足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止，这是从上往下的堆化方法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]

一个包含n个节点的完全二叉树，树的高度不会超过log2n。堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，即O(log n)。插入数据和删除堆顶元素的主要逻辑就是堆化，所以往堆中插入一个元素和删除堆顶元素的时间复杂度都是O(log n)。

### 三：如何基于堆实现排序 ###

排序方法有时间复杂度是O(n^2)的冒泡排序，插入排序，选择排序，有时间复杂度是O（nlogn）的归并排序，快速排序，线性排序。

借助堆这种数据结构实现的排序算法就叫作堆排序，这种排序方法的时间复杂度非常稳定，是**O(nlogn)**，并且它还是**原地排序算法**。  
堆排序的过程大致分解为两大步骤：建堆和排序

#### 1. 建堆： ####

1，首先将数组原地建成一个堆。“原地”：是指不借助另一个数组，就在原地数组上操作。  
2，建堆有两种思路：  
**第一种**：在堆中插入一个元素的思路。第一种建堆思路的处理过程是从前往后处理数组数据，并且每个数据插入堆中时，都是从下往上堆化。  
尽管数组中包含n个数据，但是可以假设起初堆中只包含一个数据，就是下标为1的数据。然后，调用插入方法，将将下标从2到n的数据依次插入到堆中，这样就将包含n个数据的数组，组织成了堆  
**第二种**：是从后往前处理数组，并且每个数据都是从上往下堆化。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]

对下标从n/2开始到1的数据进行堆化，下标是n/2 + 1到n的节点，是叶子节点，不需堆化

private static void buildHeap(int[] a, int n) { 
      for (int i = n/2; i >= 1; --i) { 
        heapify(a, n, i);
      }
    }
    
    private static void heapify(int[] a, int n, int i) { 
      while (true) { 
        int maxPos = i;
        if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
        if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
        if (maxPos == i) break;
        swap(a, i, maxPos);
        i = maxPos;
      }
    }

3，建堆的时间复杂度  
每个节点堆化的时间复杂度是**O(logn)**，则n/2+1个节点堆化的总时间复杂度是O(n)。  
①：因为叶子节点不需要堆化，所以需要堆化的节点从倒数第二层开始。每个节点堆化的过程中，需要比较和交换的节点个数，跟这个节点高度k成正比。

#### 2. 排序： ####

建堆结束后，数组中的数据已是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，也就是最大的元素。  
将它和最后一个元素交换，最大元素就放到了下标为n的位置  
这个过程有点类似“删除堆顶元素”的操作，当堆顶元素移除后，把下标为n的元素放到堆顶，然后在通过堆化的方法，将剩下的n-1个元素重新构建成堆。堆化完成之后，在取堆顶元素，放到下标是n-1的位置，一直重复这个过程，直到最后堆中只剩下标为1的一个元素，排序工作就完成了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 6]

// n表示数据的个数，数组a中的数据从下标1到n的位置。
    public static void sort(int[] a, int n) { 
      buildHeap(a, n);
      int k = n;
      while (k > 1) { 
        swap(a, 1, k);
        --k;
        heapify(a, k, 1);
      }
    }

**时间，空间复杂度，以及稳定性分析**  
①：整个堆排序的过程，都只需要极个别临时存储空间，所以堆排序是**原地排序算法**。  
②：堆排序包括建堆和排序两个操作，**建堆过程的时间复杂度是O(n)**，\*\*排序过程的时间复杂度是O(nlogn),\*\*所以堆排序的时间复杂度是O(nlogn)  
③：堆排序不是稳定的排序算法，可能改变值相等的数据原始相对顺序。

### 四：堆的应用 ###

### 应用一： ###

**<1>：优先级队列**  
1，优先级队列，数据的出队顺序不是先进先出，而是而是按照优先级来，优先级最高的，最先出队。  
2，实现一个优先级队列方法很多，但是用堆来实现是最直接，最高效的，这是因为堆和优先级队列非常相似。一个堆可以看作一个优先级队列，很多时候，他们只是概念上的区分。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。  
3，优先级队列的应用广泛，如赫夫曼编码，图的最短路径，做小生成树的算法等等

**<2>：优先级队列应用一：合并有序小文件**  
假设：有100个小文件，每个文件大小为100MB，每个文件中储存的都是有序的字符串。现需要将这100个小文件合并成一个有序的大文件。  
思路：

**数组**  
1，整体思路有点像归并排序中的合并函数，从100个文件中，各取第一个字符串，放入数组中，然后比较大小，把最小的那个字符串合并后的大文件中，并从数组中删除。  
2，假设，最小的字符串来自于13.txt这个文件，就再次从这个文件找那个取下一个字符串，放到数组中，重新比较大小，并且选择最小的放入合并后的大文件，将它从数组中删除。依次类推，直到所有的文件中的数据都放入到大文件为止。  
3，使用数组来存储从小文件中取出来的字符串，每次从数组中取最小字符串，都需要循环遍历整个数组，效率不高。

**优先队列**  
4，可以用到优先级队列，也可以说是堆。将从小文件中取出的字符串放入到小顶堆中，堆顶的元素就是优先级队列队首的元素，就是最小的字符串。  
5，依次从小文件中取出下一个字符串，放入到堆中，循环这过程。  
删除堆顶数据和往堆中插入数据的时间复杂度都是O(logn)，n表示堆中的数据个数，这里就是100

**<3>：优先队列应用二：高性能定时器**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 7]

假设：有一个定时器，定时器中维护了很多定时任务  
1，每过1秒就扫描一遍任务列表做法太低效。原因1：任务的约定执行时间离当前时间可能还有很久，大量的扫描徒劳无功。原因2：每次都要扫描整个任务列表，若列表较大，会比较耗时。  
2，针对这种文件，可用优先队列来解决。按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（最小顶堆）存储的是最先执行的任务。  
3，这样定时器就不用每隔一秒就扫描一遍任务列表了。它拿队首任务的执行时间点，与当前时间点相减，即可得到一个时间间隔T。  
4，当T秒时间过去后，定时器取优先级队列中队首的任务执行，然后在计算新的队首任务的执行时间点和当前时间点的差值。  
5，这样定时器就不用间隔1秒就轮询一次，也不用遍历整个任务列表，性能就提高了。

### 应用二：利用堆求Top K ###

求Topk的问题可抽象成两类：  
**1，针对静态数据**  
可以维护一个大小为k的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果堆顶元素大，就将堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前k大数据了。  
遍历数据需要O(n)的时间复杂度，一次堆化操作需要O(logk)的时间复杂度，最坏情况下，n个元素都入堆一次，时间复杂度就是O(nlogk)。

**2，针对动态数据求得Topk就是实时Topk。**  
一个数据集合有两个操作，一个是添加数据，另一个询问当前的前k大数据。  
可以维护一直都维护一个k大小的小顶堆，当有数据被添加到集合时，就那它与堆顶的元素对对比。如果比堆顶元素大，就把堆顶元素删除，并将这个元素插入到堆中，如果比堆顶元素小，这不处理。这样，无论任何时候需要查询当前的前k大数据，就都可以 立刻返回给他。

### 应用三：利用堆求中位数 ###

1，对于一组静态数据，中位数是固定的，可以先排序，第n/2个数据就是中位数。  
2，对于动态数据集合，就无法先排序了，需要借助堆这种数据结构，我们不用排序，就可以非常高效的实现求中位数操作。  
**实现思路：**  
1，**需要维护两个堆，大顶堆中存储前半部分数据，小顶堆中存储后半部分数据**，且小顶堆中的数据都大于大顶堆中的数据。  
2，即：如果有n个数据，n是偶数，从小到大排序，那前n/2个数据存储在大顶堆中，后n/2个数据存储在小顶堆中。这样，大顶堆中堆顶元素就是要找的中位数。  
3，如果新加入的数据小于等于大顶堆的堆顶元素，就将这个数据插入到大顶堆；否则就插入小顶堆  
4，当**两个堆中的数据量不服和中位数的约定时，就从一个堆中不停的将堆顶的元素移动到另一个堆**，重新让两个堆中数据满足上面的约定。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 8]

于是，可以利用两个堆实现动态数据集合中求中位数的操作，插入数据因为涉及堆化，所以时间复杂度变成了O(logn)，但求中位数只需要返回大顶堆的堆顶元素就可以了，所以时间复杂度就是O(1)。

### N 问题 ###

**假设现在我们有一个包含 10 亿个搜索关键词的日志文件，如何快速获取到 Top 10 最热门的搜索关键词呢？**  
因为用户搜索的关键词，有很多可能都是重复的，所以我们首先要统计每个搜索关键词出现的频率。我们可以通过散列表、平衡二叉查找树或者其他一些支持快速查找、插入的数据结构，来记录关键词及其出现的次数。  
假设我们选用散列表。我们就顺序扫描这 10 亿个搜索关键词。当扫描到某个关键词时，我们去散列表中查询。如果存在，我们就将对应的次数加一；如果不存在，我们就将它插入到散列表，并记录次数为 1。以此类推，等遍历完这 10 亿个搜索关键词之后，散列表中就存储了不重复的搜索关键词以及出现的次数。  
假设我们选用散列表。我们就顺序扫描这 10 亿个搜索关键词。当扫描到某个关键词时，我们去散列表中查询。如果存在，我们就将对应的次数加一；如果不存在，我们就将它插入到散列表，并记录次数为 1。以此类推，等遍历完这 10 亿个搜索关键词之后，散列表中就存储了不重复的搜索关键词以及出现的次数。  
然后，我们再根据前面讲的用堆求 Top K 的方法，建立一个大小为 10 的小顶堆，遍历散列表，依次取出每个搜索关键词及对应出现的次数，然后与堆顶的搜索关键词对比。如果出现次数比堆顶搜索关键词的次数多，那就删除堆顶的关键词，将这个出现次数更多的关键词加入到堆中。  
以此类推，当遍历完整个散列表中的搜索关键词之后，堆中的搜索关键词就是出现次数最多的 Top 10 搜索关键词了。

**改进**  
10 亿的关键词还是很多的。我们假设 10 亿条搜索关键词中不重复的有 1 亿条，如果每个搜索关键词的平均长度是 50 个字节，那存储 1 亿个关键词起码需要 5GB 的内存空间，而散列表因为要避免频繁冲突，不会选择太大的装载因子，所以消耗的内存空间就更多了。而我们的机器只有 1GB 的可用内存空间，所以我们无法一次性将所有的搜索关键词加入到内存中。  
我们在哈希算法那一节讲过，相同数据经过哈希算法得到的哈希值是一样的。我们可以根据哈希算法的这个特点，将 10 亿条搜索关键词先通过哈希算法分片到 10 个文件中。  
具体可以这样做：我们创建 10 个空文件 00，01，02，……，09。我们遍历这 10 亿个关键词，并且通过某个哈希算法对其求哈希值，然后哈希值同 10 取模，得到的结果就是这个搜索关键词应该被分到的文件编号。  
对这 10 亿个关键词分片之后，每个文件都只有 1 亿的关键词，去除掉重复的，可能就只有 1000 万个，每个关键词平均 50 个字节，所以总的大小就是 500MB。1GB 的内存完全可以放得下。  
我们针对每个包含 1 亿条搜索关键词的文件，利用散列表和堆，分别求出 Top 10，然后把这个 10 个 Top 10 放在一块，然后取这 100 个关键词中，出现次数最多的 10 个关键词，这就是这 10 亿数据中的 Top 10 最频繁的搜索关键词了。

**有一个访问量非常大的新闻网站，我们希望将点击量排名 Top 10 的新闻摘要，滚动显示在网站首页 banner 上，并且每隔 1 小时更新一次。如果你是负责开发这个功能的工程师，你会如何来实现呢？**  
1，对每篇新闻摘要计算一个hashcode，并建立摘要与hashcode的关联关系，使用map存储，以hashCode为key，新闻摘要为值  
2，按每小时一个文件的方式记录下被点击的摘要的hashCode  
3，当一个小时结果后，上一个小时的文件被关闭，开始计算上一个小时的点击top10  
4，将hashcode分片到多个文件中，通过对hashCode取模运算，即可将相同的hashCode分片到相同的文件中  
5，针对每个文件取top10的hashCode，使用Map<hashCode,int>的方式，统计出所有的摘要点击次数，然后再使用小顶堆（大小为10）计算top10,  
6，再针对所有分片计算一个总的top10,最后合并的逻辑也是使用小顶堆，计算top10  
7，如果仅展示前一个小时的top10,计算结束  
8，如果需要展示全天，需要与上一次的计算按hashCode进行合并，然后在这合并的数据中取top10  
9，在展示时，将计算得到的top10的hashcode，转化为新闻摘要显示即可

**在实际开发中，为什么快速排序要比堆排序性能好？**  
**第一点，堆排序数据访问的方式没有快速排序友好。**  
对于快速排序来说，数据是顺序访问的。而对于堆排序来说，数据是跳着访问的。 比如，堆排序中，最重要的一个操作就是数据的堆化。比如下面这个例子，对堆顶节点进行堆化，会依次访问数组下标是 1，2，4，8 的元素，而不是像快速排序那样，局部顺序访问，所以，这样对 CPU 缓存是不友好的。  
**第二点，对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。**  
我们在讲排序的时候，提过两个概念，有序度和逆序度。对于基于比较的排序算法来说，整个排序过程就是由两个基本的操作组成的，比较和交换（或移动）。快速排序数据交换的次数不会比逆序度多。但是堆排序的第一步是建堆，建堆的过程会打乱数据原有的相对先后顺序，导致原数据的有序度降低。比如，对于一组已经有序的数据来说，经过建堆之后，数据反而变得更无序了。

[笔记整理来源： 王争 数据结构与算法之美][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/ba2920ffaae2465985c7d788038947d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/b72eeaaafa61479b94a5f09194a9700b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/19e9a5b5da6c41f59f306a01afaa36b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/6b293be00c624b069ea9b609b2d482d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221124/95a3e3323df64c2cab25efb9e9d17d64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221124/da1b35e961b14a7c957dbc605efaff54.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221124/45e0cbd595a34584bba27fc66108ced4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221124/b37c0c9567ea48feb7465030e704591b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221124/14592030b2c64cd3acce223385cdcddb.png
[Link 1]: https://s1.ax1x.com/2020/08/03/aUh2TS.png