算法（第4版）
算法（第4版）
- 作者: Robert Sedgewick Kevin Wayne
- 简介: 本书作为算法领域经典的参考书，全面介绍了关于算法和数据结构的必备知识，并特别针对排序、搜索、图处理和字符串处理进行了论述。第4版具体给出了每位程序员应知应会的50个算法，提供了实际代码，而且这些Java 代码实现采用了模块化的编程风格，读者可以方便地加以改造。本书配套网站提供了书中内容的摘要及更多的代码实现、测试数据、练习、教学课件等资源。本书适合用作大学教材或从业者的参考书。配套网站algs4.cs.princeton.edu提供了本书内容摘要以及相关代码、测试数据、编程练习、教学课件等资源。
- 出版时间: 2012-10-10
- ISBN: 9787115293800
- 分类: 计算机-编程设计
- 出版社: 人民邮电出版社
- 字数: 618193
- 在线阅读: 微信读书
- 划线数量: 19
- 想法数量: 4
笔记
2.4 优先队列
📌 在这种情况下，一个合适的数据结构应该支持两种操作：删除最大元素和插入元素。这种数据类型叫做优先队列。优先队列的使用和队列（删除最老的元素）以及栈（删除最新的元素）类似，但高效地实现它则更有挑战性。
💭 Priority Queue / Heap
- ⏱ 2024-02-01 12:42:03 ^19836794-7OEvHAwI0
📌 通过插入一列元素然后一个个地删掉其中最小的元素，我们可以用优先队列实现排序算法。一种名为堆排序的重要排序算法也来自于基于堆的优先队列的实现。
- ⏱ 2024-02-01 12:42:22 ^19-1275-1373
📌 优先队列最重要的操作就是删除最大元素和插入元素，所以我们会把精力集中在它们身上。
- ⏱ 2024-02-01 15:56:52 ^19-1762-1858
📌 MaxPQ的任意实现都能很容易地转化为MinPQ的实现，反之亦然，只需要改变一下less()比较的方向即可。
- ⏱ 2024-02-01 15:56:43 ^19-2587-2641
📌 在某些应用场景中，输入量可能非常巨大，甚至可以认为输入是无限的。解决这个问题的一种方法是将输入排序然后从中找出M个最大的元素，但我们已经说明输入将会非常庞大。另一种方法是将每个新的输入和已知的M个最大元素比较，但除非M较小，否则这种比较的代价会非常高昂。
- ⏱ 2024-02-01 16:14:18 ^19-2925-3136
📌 当优先队列的大小超过M时就删掉其中最小的元素。
💭 保留大的，踢出小的，所以维护的是一个MinPQ而不是MaxPQ。
- ⏱ 2024-02-01 16:33:35 ^19836794-7OEKRJL6r
📌 数据结构二叉堆能够很好地实现优先队列的基本操作。在二叉堆的数组中，每个元素都要保证大于等于另两个特定位置的元素。相应地，这些位置的元素又至少要大于等于数组中的另两个元素，以此类推。如果我们将所有元素画成一棵二叉树，将每个较大元素和两个较小的元素用边连接就可以很容易看出这种结构。
💭 所以优先队列是一种数据结构的接口，特征是要提供删除最大（或最小）元素、插入新元素的方法。
而堆是一种具体的数据结构，基于二叉树实现，是优先队列的一个典型实例。堆要求二叉树的每个节点都大于等于（或小于等于）他的两个子节点。
- ⏱ 2024-02-01 16:50:53 ^19836794-7OEM01jgH
📌 当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。
- ⏱ 2024-02-01 16:48:46 ^19-7781-7842
📌 根结点是堆有序的二叉树中的最大结点。
- ⏱ 2024-02-01 16:55:17 ^19-8052-8070
📌 二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不使用数组的第一个位置）。
- ⏱ 2024-02-01 16:56:16 ^19-8869-8925
📌 在一个堆中，位置k的结点的父结点的位置为[k/2]，而它的两个子结点的位置则分别为2k和2k+1。
💭 这里的表示需要数组的下标从1开始，而不是0。
另，父节点的下标严谨来说应该是向下取整，⎣k/2⎦。
- ⏱ 2024-02-01 17:08:17 ^19836794-7OEN8CGoT
📌 一棵大小为N的完全二叉树的高度为[lgN]。
- ⏱ 2024-02-01 17:05:26 ^19-9605-9683
📌 堆的有序化（reheapifying）
- ⏱ 2024-02-02 15:34:40 ^19-10484-10510
📌 在有序化的过程中我们会遇到两种情况。当某个结点的优先级上升（或是在堆底加入一个新的元素）时，我们需要由下至上恢复堆的顺序。当某个结点的优先级下降（例如，将根结点替换为一个较小的元素）时，我们需要由上至下恢复堆的顺序。
- ⏱ 2024-02-02 15:37:04 ^19-10833-10997
📌 只要记住位置k的结点的父结点的位置是[k/2]，这个过程实现起来很简单。
- ⏱ 2024-02-02 23:39:28 ^19-11378-11470
📌 浮（swim）
- ⏱ 2024-02-02 23:40:49 ^19-11611-11625
📌 如果堆的有序状态因为某个结点变得比它的两个子结点或是其中之一更小了而被打破了，那么我们可以通过将它和它的两个子结点中的较大者交换来恢复堆。
- ⏱ 2024-02-02 23:40:19 ^19-12315-12384
📌 由位置为k的结点的子结点位于2k和2k+1可以直接得到对应的代码。
- ⏱ 2024-02-02 23:40:40 ^19-12454-12571
📌 沉（sink）
- ⏱ 2024-02-02 23:40:59 ^19-12646-12660
📌 插入元素。我们将新元素加到数组末尾，增加堆的大小并让这个新元素上浮到合适的位置
- ⏱ 2024-02-04 14:46:37 ^19-13311-13357
📌 删除最大元素。我们从数组顶端删去最大的元素并将数组的最后一个元素放到顶端，减小堆的大小并让这个元素下沉到合适的位置
- ⏱ 2024-02-04 14:46:41 ^19-13423-13487