Leetcode | 第5节：排序方法的设计，堆，堆排序，快速排序

学弱猹

发布于 2021-08-10 11:20:44

7440

发布于 2021-08-10 11:20:44

文章被收录于专栏：学弱猹的精品小屋学弱猹的精品小屋

大家好！

这一节我们来继续讨论排序算法所延伸出的一些题目。如果有空的话，还会说一些堆，也就是优先队列的一些比较经典的题目。

那么我们开始吧。

算法3：排序算法（下）

其实标题起名叫“排序算法”还不完全正确。对于部分题目而言，排序算法本身不重要，怎么用排序才重要。这一部分题目我们也会算在这一节里面，并且放在前面先说。

Problem 1: Leetcode 56 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

假如说intervals = [[1,3],[2,6],[8,10],[15,18]]，那么答案就应该是[[1,6],[8,10],[15,18]]，因为很明显，[1, 3]和[2, 6]是可以被合并的，变成一个[1, 6]，可以见下图。

这一个题就是大名鼎鼎的合并区间，是一道极为经典的使用排序解决的题目。如果我们手动枚举的话，最常见的方法就是一个

O(n^2)

的复杂度。但对于这一个题，事实上直接按照左端点排序，就可以一次枚举得到结果了，因为我们容易想到的是，在排序之后，只要下一个区间左边的端点，超过上一个区间的右边的端点（比方说[1, 3]碰到[4, 5]），就不会重叠。否则的话就会重叠。重叠的话，左边取最左边的端点（这一点其实也不需要，因为已经按照左端点排序了），右边取最右边的端点就可以了。

所以代码其实很好写，核心代码大概长这样

vector<vector<int>> merge(vector<vector<int>>& intervals) {
  if (intervals.size() == 0) {
    return {};
  }
  sort(intervals.begin(), intervals.end());
  vector<vector<int>> merged;
  for (int i = 0; i < intervals.size(); ++i) {
    int L = intervals[i][0], R = intervals[i][1];
    if (!merged.size() || merged.back()[1] < L) {
      merged.push_back({L, R});
    }
    else {
      merged.back()[1] = max(merged.back()[1], R);
    }
  }
  return merged;
}

这里是对C++中的vector<int>类做了一个排序，不需要额外写排序规则（这种题目也存在，后面会简单说一下），因为默认就是左端点排序的。代码中，实际上是建立了一个新的数组，然后每一次遇到一个新的区间，会和已经合并统计过的区间的最后一个做比较。

对于这一个题目，其实代码和方法都不难，但是怎么想到用左端点排序，就有点难解释了。因此我们这里补一个对于这个方法正确性的证明，大家如果可以看明白，对于这个方法就会有更深的认识。不过即使看不明白，背下来也就好了。

我们考虑反证法。假如这样之后，我们依然能够找到两个数组，它们是可以合并的，结果没有合并，如何定义这个问题？

我们要注意的是，我们的做法是按照顺序枚举，然后每一次与已经合并好的数组去比较。所以一定要注意的是，能够合并的数组一定要是连续的（换句话说，可以合并的数组必须都在一块儿，不能中间插入属于其它区间的），否则这个算法就可能出问题。因此我们要证明的就是

可以合并的区间一定是连续的。

那么它的反证法命题就是

\exists i < j < k

，

\exists a[i], a[j], a[k]

，

s.t.

，

(a[i], a[k])

可以合并，但是

(a[i], a[j]])

(a[j], a[k])

不可以合并。

这里

a[i]

指的是list中的某一个元素，也就是某一个区间。

我们用一张图表示一下这个命题到底在说什么。

在这张图中，设[1, 2, 3, 5, 6]是可以被合并的区间下标，那么中间隔了一个4，说明可以合并的区间不是连续的。那么在这个命题中，就相当于取

i = 3, k = 5

，那么意思就是“第3, 5个区间可以合并，但是第3, 4和第4, 5个区间不可以合并”。

那么现在我们按照这个算法来看，如果这个命题是对的，那我们有

a[i].end < a[j].start

a[j].end < a[k].start

a[i].end \ge a[k].start

那么只需要看前两个不等式，就有

a[i].end < a[j].start \le a[j].end < a[k].start

这与第三个式子就矛盾了。所以这样的话就变相说明了方法的正确性。

Problem 2: Leetcode 354 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。注意：不允许旋转信封。

这一个题目虽然名义上是一个hard，但是个人感觉其实思路还是很明确的，利用到的技巧也是之前接触过的。

首先我们要注意的是，不允许旋转，而且必须要求下一个信封的宽和高都要比上一个信封要大。所以排序是肯定可以想到的，但是这里很明显只能对一个维度排序，那么不妨选择宽度，那么只需要在高度中选择一些值，满足它们相互之间依然是严格的有序关系，并且数量尽可能的多。这个就是我们在第一节

Leetcode | 第一节：动态规划（上）

的Problem 3中提到的最长上升子序列（LIS）的问题。所以思路其实大家都学过了，也只是用到了一个排序而已。

但是要注意的是，这里还有一个细节，就是我们可以通过LIS控制高度这个维度，它是严格递增的。但是宽度你还是没有控制啊。换句话说，假如说我们的数据集是[[1, 1], [1,2], [1,3]]，那么给宽度排序之后，只能通过LIS选出[1, 2, 3]，但是实际上这并不是正确答案（因为宽度3个都是1，并不是严格的升序）。

怎么办呢？这里的trick就是，把高度作为第二关键字作降序排列。对于上面这个例子，这么做之后，对于相同的宽度，因为高度降序排列了，所以LIS只有可能在这些高度中选择一个加入答案（例如[1, 2, 3]排序成了[3, 2, 1]，那么LIS无论如何只能选择这个数组中的一个元素）。这样就避免了这个问题。

好的，我们来看下核心代码。

int maxEnvelopes(vector<vector<int>>& envelopes) {
  if (envelopes.empty()) {
    return 0;
  }

  int n = envelopes.size();
  sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
    return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
  });

  vector<int> f(n, 1);
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
      if (envelopes[j][1] < envelopes[i][1]) {
        f[i] = max(f[i], f[j] + 1);
      }
    }
  }
  return *max_element(f.begin(), f.end());
}

这里的新奇点就在于需要自己写排序规则（对应代码中sort那一块）。在这里大家可以观察到，其实就是一个相邻元素的比较而已。当然，代码细节还是有一些的，推荐大家自己写一遍，会更有印象。

快速排序，堆

排除它们俩衍生的Leetcode习题，快速排序（quicksort）和堆排序（heapsort）本身就是两个极为高频的考点。因此在介绍它们俩对应的题目之前，我们先简单介绍一下这两个算法。

快速排序本质上就是一个分治（Divide and Conquer）的思想，大概来说，我们会选择一个元素作为pivot，然后做一轮的循环，这一轮的循环保证的事情是，pivot左边的元素都比它小，pivot右边的元素都比它大（升序情况）。然后左边和右边的部分就会进入递归。分别再选择不同的pivot，保证这个规则成立。那么久而久之，一定可以保证最终的数组是有序的。同时因为我们pivot选择具备随机性，所以平均的时间复杂度是

O(n \log n)

，相比较上一节

Leetcode | 第4节：二分查找，归并排序

的归并排序，它的空间复杂度需求是

O(1)

（归并排序是

O(n)

）。

这里我们给一个示例结果。具体如何设置两个指针完成这个快速排序的过程，读者可以自己寻找资料，然后回头来推一推，看是否可以得到这个结果。

快速排序介绍完，我们介绍一下堆。堆排序和堆本身，都是非常重要的考点。我们先介绍堆，再介绍堆排序的过程。

堆本质上是一种树的数据结构，根据根的大小关系，我们把它区分成为大根堆和小根堆。大根堆的意思就是根的元素比它的左子树节点，右子树节点都要大，小根堆就要反过来。所以事实上关于堆的考点就在于两个：如何建堆，堆排序的时候如何调整堆。

堆排序的过程则极为简单。因为大根堆可以保证的是根的元素是数组中的最大值，所以可以把这个最大值移除之后调整堆，使得其重新成为大根堆。这样的话根元素就会变成第二大的元素。再移除，再调整，依次往下就可以得到一个有序数列。

不同于快速排序中我们要具体深入细节，修改快速排序的过程来解题（之前的归并排序也是如此），堆排序有一个专门的数据结构叫作优先队列（PriorityqQueue）。这也意味着对于堆的考察，更多是对于堆的数据结构本身的考察。因此我们更多的需要明白的是堆的使用场景，而不是堆排序本身（当然还是推荐大家仔细看一下堆排序的过程，毕竟堆排序本身如果真要考，估计也能考死一大批人……）

说完这些，我们来看一下具体的题目吧。

Problem 3: Leetcode 973 我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。（这里，平面上两点之间的距离是欧几里德距离。）你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。

这一个题目也是非常经典的题目（我也被考过……）。直观上来看，把距离算一遍之后，排个序，这个题就可以解，复杂度是

O(n \log n)

。但是问题在于，如果面试官叫你提供一个

O(n)

的解法呢？

这里的两个

O(n)

的解法都是比较常见的考点，并且分别对应快速排序和堆排序，所以我们都会介绍一下。先介绍一下堆排序的方法。很多人可能搞不清楚为什么这一个问题最好的方法是使用堆排序，而不是什么归并排序（因为它们时间复杂度看起来是一样的）。但一定要注意的是，堆排序的过程在于根节点一定是最值元素，在这里我们并不需要一个完整的有序的数组，而是只需要其中的

个。那么排序整个数组就是对资源的浪费了。

好的，那我们看一下究竟如何做堆排序会比较好。首先要注意的是，堆内部一定是可以有序的（通过堆的性质和堆排序），所以不需要建立一个大小为

的堆然后输出

个，而是只需要建立大小为

的堆，然后在堆满了之后，再加入元素就可以根据堆的性质做自动的增加和删除。这一个过程耗时是

O(\log k)

。

好的，我们来看看核心代码。

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
  priority_queue<pair<int, int>> q;
  for (int i = 0; i < k; ++i) {
    q.emplace(points[i][0] * points[i][0] + points[i][1] * points[i][1], i);
  }
  int n = points.size();
  for (int i = k; i < n; ++i) {
    int dist = points[i][0] * points[i][0] + points[i][1] * points[i][1];
    if (dist < q.top().first) {
      q.pop();
      q.emplace(dist, i);
    }
  }
  vector<vector<int>> ans;
  while (!q.empty()) {
    ans.push_back(points[q.top().second]);
    q.pop();
  }
  return ans;
}

这里要注意的是，堆的操作全过程都需要依赖priority_queue这一个类。这里建立的是一个元素为pair<int, int>，也就是有序数对的堆。不同的编程语言，类的方法可能会有所不同，因此这里我们就不多做细节的解释，读者可以在阅读代码的时候顺便通过搜索引擎，了解这个类的使用。

说完了堆的方法，我们来看看快速排序。这里的算法借用了快速排序的思想，实质上它有一个自己的新名字叫作快速选择（Quick Select）。快速排序的核心是选择一个pivot，保证pivot左边的元素都比它小，右边的元素都比它大（升序情况）。但是不同于快速排序需要再递归处理两边，我们这里因为只关注前

个，所以事实上并不需要再考虑两边，而只需要考虑一边。具体的思路是这样的：

定义函数random_select(left, right, k)，left, right分别代表左，右端点，

表示找到第

个点。

定义pivot为快速排序的枢纽点，下标为

。

如果

k < i - left + 1

，那么第

小的元素在pivot左边，这个时候调用random_select(left, i - 1, k)。

如果

k > i - left + 1

，那么第

小的元素在pivot右边，这个时候调用random_select(i + 1, right, k - (i - left + 1))。

如果

k = i - left + 1

，那么说明找到了第

小的元素，就可以结束。

这里我们再多解释几句，如果第

小的元素在pivot左边，那么说明，pivot需要往左移。换句话说，右边的元素都不是我们要找的“

个最小的“，所以可以直接忽略了。这样的话，就直接把查找范围缩小到[left, i -1]就可以了。

如果第

小的元素在pivot右边，那么pivot需要往右移，那么这个时候，说明左边的元素都是符合条件的，所以保留下来就可以了。但是我们还需要找到一些（毕竟没有找齐

个），所以这个时候需要把查找范围改成[i + 1, right]。但是因为已经找到了一些了（left左边都是，注意我们不需要对左边这些符合条件的元素再排序，因为我们只需要知道

个最小的，不需要让它们有序输出），所以只需要再找k - (i - left + 1)个元素就可以了。

好的，我们来看看核心代码。

void random_select(vector<vector<int>>& points, int left, int right, int k) {
  int pivot_id = uniform_int_distribution<int>{left, right}(gen);
  int pivot = points[pivot_id][0] * points[pivot_id][0] + points[pivot_id][1] * points[pivot_id][1];
  swap(points[right], points[pivot_id]);
  int i = left - 1;
  for (int j = left; j < right; ++j) {
    int dist = points[j][0] * points[j][0] + points[j][1] * points[j][1];
    if (dist <= pivot) {
      ++i;
      swap(points[i], points[j]);
    }
  }
  ++i;
  swap(points[i], points[right]);
  // [left, i-1] 都小于等于 pivot, [i+1, right] 都大于 pivot
  if (k < i - left + 1) {
    random_select(points, left, i - 1, k);
  }
  else if (k > i - left + 1) {
    random_select(points, i + 1, right, k - (i - left + 1));
  }
}

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
  int n = points.size();
  random_select(points, 0, n - 1, k);
  return {points.begin(), points.begin() + k};
}

这个代码还是需要熟悉一些C++的api的（例如swap和输出前

个元素的时候用到的迭代器方法）。当然快速选择方法和快排一样，代码细节也都比较多，因此建议大家自己花时间多写写会比较好～

与这个题目非常类似的题目有Leetcode 215, 347和692。它们的做法和这个题一模一样，但是一个需要处理数值，一个需要处理字符串，在对相关api的掌握上会有所帮助，因此建议大家也可以看看。

Problem 4: Leetcode 378 给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

举个例子，如果我们输入是matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8，那么输出就是13，读者可以自己把这9个数排个序，然后看一下第8个元素，它就是13。

这一个问题也是很有意思的。它只是借用到了堆这个结构，主要的解题思路是我们之前所提到的归并排序和二分查找。因此我们用这一个题，其实也可以相当于对于上一节的内容做一个复习。

首先来看看归并排序应该怎么解决。对于这一个问题，很容易想到的就是对于每一行，设置一个指针，然后一直归并到一个新的数组，直到找到了第

个元素。本质上，和两个数组的归并是没有区别的。

我们直接用代码来看看，堆究竟是如何在这里被使用的。

int kthSmallest(vector<vector<int>>& matrix, int k) {
        struct point {
            int val, x, y;
            point(int val, int x, int y) : val(val), x(x), y(y) {}
            bool operator> (const point& a) const { return this->val > a.val; }
        };
        priority_queue<point, vector<point>, greater<point>> que;
        int n = matrix.size();
        for (int i = 0; i < n; i++) {
            que.emplace(matrix[i][0], i, 0);
        }
        for (int i = 0; i < k - 1; i++) {
            point now = que.top();
            que.pop();
            if (now.y != n - 1) {
                que.emplace(matrix[now.x][now.y + 1], now.x, now.y + 1);
            }
        }
        return que.top().val;
    }

大家可以看到，首先我们定义了一个新的结构体，在结构体内定义了一个point数据结构，也定义了比较规则。然后基于这个比较规则定义了小根堆。在一开始的时候，所有的第一列的元素都进入堆，然后不停的弹出最小的（也就是堆顶/根节点），每弹出一个，就记录这个元素的位置，只要它不是最后一列，就把这个元素所在行的下一个元素放入堆，相当于归并排序中，指针向后移了一位。

那么这道题用二分查找又怎么完成呢？注意这个问题，二分查找是目的而不是手段。也就是说我们只需要定义好二分的上下界，然后对于每一个可能值

，去看它是第几小的就可以了。

对于下面这张图，大家可以看到，我们取的是

x = 8

，可以发现，画红线的左边都是

\le 8

的元素。

这一条线有什么特点？容易看出，它是从左下角往右上角去延伸的。换句话说，我们最终其实只需要找到这一条线，就可以记录下来每一个

对应的这个结果，时间复杂度也是线性而不是平方的。比方说

\le x

的元素有

个，那么只要

n < k

，就说明我们的

小了，二分的时候就应该取右半段，反过来同理。

具体怎么找这一条线呢？其实也很简单，概括下来就是

从左下角开始，一直往右走。如果往右走遍历的元素

> x

，那就往上走，并且记录这一行的坐标，代表这一行

\le x

的元素个数。

好的，我们来看一下核心代码。

bool check(vector<vector<int>>& matrix, int mid, int k, int n) {
  int i = n - 1;
  int j = 0;
  int num = 0;
  while (i >= 0 && j < n) {
    if (matrix[i][j] <= mid) {
      num += i + 1;
      j++;
    } else {
      i--;
    }
  }
  return num >= k;
}

int kthSmallest(vector<vector<int>>& matrix, int k) {
  int n = matrix.size();
  int left = matrix[0][0];
  int right = matrix[n - 1][n - 1];
  while (left < right) {
    int mid = left + ((right - left) >> 1);
    if (check(matrix, mid, k, n)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

这里的check函数，做的就是我们之前说的，“找红线”的工作。

Problem 5: Leetcode 295 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构： void addNum(int num) - 从数据流中添加一个整数到数据结构中。double findMedian() - 返回目前所有元素的中位数。

这个感觉很像是个设计题，但是也是高频题+hard的其中一个，我们也拿出来说一下。

我们可以发现这其实是一个流式操作。换句话说，我们不可能等到运行findMedian()这个函数的时候，再从头到尾去枚举数据找到中位数，我们必须要立刻给出结果。因此这里其实就可以用堆了。因为堆可以给出立刻给出最大的/最小的元素。既然这里是中位数，那么不妨我们就设置两个堆。对于偶数的情况，这里相当于要给出两个数的平均值，那么自然想到的就是输出两个堆的堆顶元素。所以说到这里，可能有人已经明白了，关键在于如何构造两个堆，如何向堆中添加元素，使得最终在运行findMedian()的时候，可以立刻给出正确的结果。

首先大家可以想到，如果要输出中位数，我们自然需要两个堆的元素个数尽可能的相同，并且一个保存的是小的一半，一个保存的是大的一半。因此，小的一半应该是大根堆（这样输出的就是最靠近中位数的元素），大的一半应该是小根堆。不妨设这个大根堆叫lo，小根堆叫hi，并且大根堆最多允许比小根堆多一个元素（处理元素奇数的情况，当然反过来也是可以的）。

这样的话，我们的思路就很直接了

把元素输入到lo中，如果目前有奇数个元素，那么lo的元素比hi多了1个，就把lo中的元素移除一个到hi中。这个时候，hi的元素会比lo多一个，因此hi的元素移除一个到lo中，完成平衡。如果目前有偶数个元素，那么如果lo的元素比hi多2个，就把lo中的元素移除一个到hi中，完成平衡。不可能只多1个。

因为我们用的是两个堆，所以“移除”实质上移除的就是堆顶元素。同时要注意，第一步平衡的目的，是要把所有大的元素移到hi中，把所有的小的元素移到lo中。假如说之前的操作都符合这个要求的话，多余的这一个元素，我们平衡一步就可以了。

这么说可能有点绕，我们画一张图，跑一遍，可能就比较清楚了。

归根到底，要抓住过程中的“平衡”的维护。

那么我们来看一下，核心代码是什么样。

class MedianFinder {
    priority_queue<int> lo;                              
    priority_queue<int, vector<int>, greater<int>> hi;  

public:
    void addNum(int num)
    {
        lo.push(num);                                   
        hi.push(lo.top());                               
        lo.pop();
        if (lo.size() < hi.size()) {                    
            lo.push(hi.top());
            hi.pop();
        }
    }

    double findMedian()
    {
        return lo.size() > hi.size() ? (double) lo.top() : (lo.top() + hi.top()) * 0.5;
    }
};

所以如何利用堆，确实是一个学问。

Problem 6: Leetcode 1383 公司有编号为 1 到 n 的 n 个工程师，给你两个数组 speed 和 efficiency ，其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。请你返回由最多 k 个工程师组成的最大团队表现值，由于答案可能很大，请你返回结果对 10^9 + 7 取余后的结果。团队表现值的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。

这个问题又如何利用堆呢？事实上非常简单，注意到这里我们要求两个数，一个是“速度和”，一个是“效率最小值”。所以事实上，只要确定效率的最小值，就可以对应的找到

位工程师，他们的效率都不低于这个数，并且他们的速度和是最大的。而速度和最大的含义，其实就是对应的，在所有符合效率条件的工程师中，寻找速度最大的

k - 1

个工程师（注意不需要寻找

个，因为“效率最小值”对应的工程师是一定要被选上的），这个过程其实就可以使用堆来维护，类似之前的“前

小“的题目。

所以第一件事其实就是，效率的最小值怎么枚举？这一点不难，从大到小排个序就可以。排序之后，对于一个固定的效率值，选中之后，这个效率值之前的所有工程师都是可以选择的。要在其中选择

k- 1

个，用堆进行维护，输出

k -1

个堆顶就可以了。

这里的一个细节就是，一开始不一定能够提供

k- 1

个元素，那么注意到题目中，并没有要求一定要

个工程师，而是“最多”

个，所以直接全选就好。同时要注意的是，在我们枚举效率值的时候，我们的可选工程师个数一定是越来越多的（仔细品一品这句话），所以可以通过动态维护堆，来降低时间复杂度，即“堆中最多只会有

k - 1

个元素“。

好的，我们来看看代码怎么写。

using LL = long long;

struct Staff {
  int s, e;
  bool operator < (const Staff& rhs) const {
    return s > rhs.s;
  }
};

int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
  vector<Staff> v;
  priority_queue<Staff> q;
  for (int i = 0; i < n; ++i) {
    v.push_back({speed[i], efficiency[i]});
  }
  sort(v.begin(), v.end(), [] (const Staff& u, const Staff& v) { return u.e > v.e; });
  LL ans = 0, sum = 0;
  for (int i = 0; i < n; ++i) {
    LL minE = v[i].e;
    LL sumS = sum + v[i].s;
    ans = max(ans, sumS * minE);
    q.push(v[i]); 
    sum += v[i].s;
    if (q.size() == k) {
      sum -= q.top().s;
      q.pop();
    }
  }
  return ans % (int(1E9) + 7);
}

这里的代码还是有一些细节的，读者如果对排序和堆的api不熟悉的话，阅读可能会有点困难。

好的，关于快速排序和堆，我们就先写到这里。

小结

这一节我们主要谈了三个内容：排序方法的设计，快速排序（快速选择）和堆排序。相比较排序方法的设计，快速排序和堆排序都是非常常考的内容，也是考察设计能力的一个很好的切入点。注意，快速排序更多的是考察对排序过程的理解，这样才能更好理解快速选择算法。而堆排序更重要的是堆本身，即如何利用堆和如何向堆中添加元素，维护堆和增加，删减元素。

在下一节我们会介绍数据结构中的栈与队列。栈与队列也可以考察非常多，非常困难的设计题。或许我们可以一节把它们说完？但或许不行hhh

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-07-12，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自学弱猹的精品小屋微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法