排序、堆与贪心

我真正开始理解“排序、堆与贪心”，不是在背完某段代码之后，而是在一次次写错之后。最明显的问题是：排序、堆和贪心以前在我脑子里是三块分开的知识，做 Top K 和任务调度后才发现它们经常在同一个问题里配合。把这些错误重新摊开来看，我才找到比口诀更可靠的理解方式。

排序、堆与贪心这一章关注的是“候选选择”和“顺序带来的结构”。它们在工程里非常常见：排行榜、任务调度、优先级队列、Top K、区间选择、资源分配，都离不开这几类思想。

这一章的重点不是死记排序代码，而是理解为什么排序之后问题会变简单，为什么堆可以动态维护最值，为什么贪心必须证明正确。

先从整理一叠卡片开始

如果只整理一次，可以把全部卡片排好序；如果卡片不断加入，而你每次只关心最小或最大的一张，维护一个堆通常更合适；如果要从一堆活动里选出尽量多的不冲突安排，则可能需要排序后做贪心选择。

它们分别回答三个不同问题：

1. 排序：怎样得到完整顺序？
2. 堆：怎样持续维护当前最重要的候选？
3. 贪心：怎样证明眼前选择不会损害最终结果？

我为什么先补这一章

这一章重点解决：

1. 排序算法怎么选。
2. Top K 和动态最值为什么适合用堆。
3. 贪心策略为什么不能只凭直觉。
4. 如何从“局部选择”推导“全局最优”。

我自己的学习顺序

1. 排序算法：从比较排序到工程选择。
2. 堆与优先队列算法：Top K、中位数与任务调度。
3. 贪心算法：局部最优与证明思维。

我当时最容易混淆的地方

排序不是目的，排序通常是在制造一个可利用的顺序，让后续判断更简单。

堆不是排序专用结构，它更像一个动态候选池：每次都能快速拿到当前最重要的元素。

贪心最危险的地方是“看起来很合理”。真正能用贪心，必须能说明每一步局部选择不会破坏最终最优。

我后来这样检查自己是否真的理解

• 快排为什么平均快，但最坏会退化？
• 什么时候用小根堆维护前 K 大？
• 区间调度为什么按结束时间排序通常有效？
• 贪心和动态规划都在做选择，它们的区别是什么？