算法（第四版）C# 习题题解——2.4
写在前面
整个项目都托管在了 github 上：https://github.com/ikesnowy/algorithms-4th-edition-in-csharp
查找更为方便的版本见：
这一节内容可能会用到的库文件有 priorityqueue，同样在 github 上可以找到。
善用 ctrl + f 查找题目。
习题&题解
2.4.1
题目
用序列 p r i o * r * * i * t * y * * * q u e * * * u * e
（字母表示插入元素，星号表示删除最大元素）
操作一个初始为空的优先队列。
给出每次删除最大元素返回的字符。
解答
r r p o t y i i u q e u
优先队列的变化如下：
| 输入命令 | 优先队列 | 输出 |
|---|---|---|
| p | p | |
| r | p r | |
| i | p r i | |
| o | p r i o | |
| * | p i o | r |
| r | p i o r | |
| * | p i o | r |
| * | i o | p |
| i | i o i | |
| * | i i | o |
| t | i i t | |
| * | i i | t |
| y | i i y | |
| * | i i | y |
| * | i | i |
| * | i | |
| q | q | |
| u | q u | |
| e | q u e | |
| * | q e | u |
| * | e | q |
| * | e | |
| u | u | |
| * | u | |
| e | e |
2.4.2
题目
分析以下说法：
要实现在常数时间找到最大元素，
为何不用一个栈或者队列，
然后记录已插入的最大元素并在找出最大元素时返回它的值。
解答
这种方式只能取出一次最大值，这个最大值就是输入序列里面的最大值。
当需要继续取出最大值时（即继续取第二大、第三大、第 i 大的元素），
这个方法就不再适用了（或者说不能在常数时间内完成）。
2.4.3
题目
用以下数据结构实现优先队列，支持插入元素和删除最大元素操作：
无序数组、有序数组、无序链表和链表。
将你的 4 种实现中每种操作在最坏情况下的运行时间上下限制成一张表格。
解答
有序数组的官方版本：https://algs4.cs.princeton.edu/24pq/orderedarraymaxpq.java.html
无序数组的官方版本：https://algs4.cs.princeton.edu/24pq/unorderedarraymaxpq.java.html
| 实现 | insert() | delmax() |
|---|---|---|
| 有序数组 | n | 1 |
| 有序链表 | n | 1 |
| 无序数组 | 1 | n |
| 无序链表 | 1 | n |
在库文件中定义了如下接口，所有的（最大）优先队列都会实现它。
using system;
namespace priorityqueue
{
/// <summary>
/// 实现优先队列 api 的接口。
/// </summary>
/// <typeparam name="key">优先队列容纳的元素。</typeparam>
public interface imaxpq<key> where key : icomparable<key>
{
/// <summary>
/// 向优先队列中插入一个元素。
/// </summary>
/// <param name="v">插入元素的类型。</param>
void insert(key v);
/// <summary>
/// 返回最大元素。
/// </summary>
/// <returns></returns>
key max();
/// <summary>
/// 删除并返回最大元素。
/// </summary>
/// <returns></returns>
key delmax();
/// <summary>
/// 返回队列是否为空。
/// </summary>
/// <returns></returns>
bool isempty();
/// <summary>
/// 返回队列中的元素个数。
/// </summary>
/// <returns></returns>
int size();
}
}
于是我们就可以使用这样的方法测试所有类型的优先队列：
static void test(imaxpq<string> pq)
{
console.writeline(pq.tostring());
pq.insert("this");
pq.insert("is");
pq.insert("a");
pq.insert("test");
while (!pq.isempty())
console.write(pq.delmax() + " ");
console.writeline();
}
代码
给出链表的实现，基于数组的实现可以点击「另请参阅」中的 priorityqueue 库查看。
无序链表
using system;
namespace priorityqueue
{
/// <summary>
/// 不保持元素输入顺序的优先队列。（基于链表）
/// </summary>
/// <typeparam name="key">优先队列中的元素类型。</typeparam>
public class unorderedlinkedmaxpq<key> : imaxpq<key> where key : icomparable<key>
{
/// <summary>
/// 保存元素的链表。
/// </summary>
private readonly linkedlist<key> pq;
/// <summary>
/// 默认构造函数，建立一条优先队列。
/// </summary>
public unorderedlinkedmaxpq()
{
this.pq = new linkedlist<key>();
}
/// <summary>
/// 获得（但不删除）优先队列中的最大元素。
/// </summary>
/// <returns></returns>
public key max()
{
int max = 0;
for (int i = 1; i < this.pq.size(); i++)
if (less(this.pq.find(max), this.pq.find(i)))
max = i;
return this.pq.find(max);
}
/// <summary>
/// 返回并删除优先队列中的最大值。
/// </summary>
/// <returns></returns>
public key delmax()
{
int max = 0;
for (int i = 1; i < this.pq.size(); i++)
if (less(this.pq.find(max), this.pq.find(i)))
max = i;
return this.pq.delete(max);
}
/// <summary>
/// 向优先队列中插入一个元素。
/// </summary>
/// <param name="v">需要插入的元素。</param>
public void insert(key v) => this.pq.insert(v);
/// <summary>
/// 检查优先队列是否为空。
/// </summary>
/// <returns></returns>
public bool isempty() => this.pq.isempty();
/// <summary>
/// 检查优先队列中含有的元素数量。
/// </summary>
/// <returns></returns>
public int size() => this.pq.size();
/// <summary>
/// 比较第一个元素是否小于第二个元素。
/// </summary>
/// <param name="a">第一个元素。</param>
/// <param name="b">第二个元素。</param>
/// <returns></returns>
private bool less(key a, key b) => a.compareto(b) < 0;
}
}
有序链表
using system;
namespace priorityqueue
{
/// <summary>
/// 元素保持输入顺序的优先队列。（基于链表）
/// </summary>
/// <typeparam name="key">优先队列中的元素类型。</typeparam>
public class orderedlinkedmaxpq<key> : imaxpq<key> where key : icomparable<key>
{
/// <summary>
/// 用于保存元素的链表。
/// </summary>
private readonly linkedlist<key> pq;
/// <summary>
/// 默认构造函数，建立一条优先队列。
/// </summary>
public orderedlinkedmaxpq()
{
this.pq = new linkedlist<key>();
}
/// <summary>
/// 向优先队列中插入一个元素。
/// </summary>
/// <param name="v">需要插入的元素。</param>
public void insert(key v)
{
int i = this.pq.size() - 1;
while (i >= 0 && less(v, this.pq.find(i)))
i--;
this.pq.insert(v, i + 1);
}
/// <summary>
/// 返回并删除优先队列中的最大值。
/// </summary>
/// <returns></returns>
public key delmax() => this.pq.delete(this.pq.size() - 1);
/// <summary>
/// 检查优先队列是否为空。
/// </summary>
/// <returns></returns>
public bool isempty() => this.pq.isempty();
/// <summary>
/// 获得（但不删除）优先队列中的最大元素。
/// </summary>
/// <returns></returns>
public key max() => this.pq.find(this.pq.size() - 1);
/// <summary>
/// 检查优先队列中含有的元素数量。
/// </summary>
/// <returns></returns>
public int size() => this.pq.size();
/// <summary>
/// 比较第一个元素是否小于第二个元素。
/// </summary>
/// <param name="a">第一个元素。</param>
/// <param name="b">第二个元素。</param>
/// <returns></returns>
private bool less(key a, key b) => a.compareto(b) < 0;
}
}
另请参阅
2.4.4
题目
一个按降序排列的数组也是一个面向最大元素的堆吗？
解答
是的。
例如这个数组：9 8 7 6 5，画成二叉堆如下：
2.4.5
题目
将 e a s y q u e s t i o n 顺序插入一个面向最大元素的堆中，给出结果。
解答
2.4.6
题目
按照练习 2.4.1 的规则，
用序列 p r i o * r * * i * t * y * * * q u e * * * u * e 操作一个初始空间为空的面向最大元素的堆，
给出每次操作后堆的内容。
解答
官方给出的最大堆实现：https://algs4.cs.princeton.edu/24pq/maxpq.java.html
运行示意图：
运行结果：
p r p r p i r p o i p o i r p o i p o i o i o i i i i t i i i i y i i i i i q u q u q e q e e u e
代码
最大堆的实现
using system;
using system.collections;
using system.collections.generic;
namespace priorityqueue
{
/// <summary>
/// 最大堆。（数组实现）
/// </summary>
/// <typeparam name="key">最大堆中保存的元素。</typeparam>
public class maxpq<key> : imaxpq<key>, ienumerable<key> where key : icomparable<key>
{
private key[] pq; // 保存元素的数组。
private int n; // 堆中的元素数量。
/// <summary>
/// 默认构造函数。
/// </summary>
public maxpq() : this(1) { }
/// <summary>
/// 建立指定容量的最大堆。
/// </summary>
/// <param name="capacity">最大堆的容量。</param>
public maxpq(int capacity)
{
this.pq = new key[capacity];
this.n = 0;
}
/// <summary>
/// 删除并返回最大元素。
/// </summary>
/// <returns></returns>
public key delmax()
{
if (isempty())
throw new argumentoutofrangeexception("priority queue underflow");
key max = this.pq[1];
exch(1, this.n--);
sink(1);
this.pq[this.n + 1] = default(key);
if ((this.n > 0) && (this.n == this.pq.length / 4))
resize(this.pq.length / 2);
return max;
}
/// <summary>
/// 向堆中插入一个元素。
/// </summary>
/// <param name="v">需要插入的元素。</param>
public void insert(key v)
{
if (this.n == this.pq.length - 1)
resize(2 * this.pq.length);
this.pq[++this.n] = v;
swim(this.n);
}
/// <summary>
/// 检查堆是否为空。
/// </summary>
/// <returns></returns>
public bool isempty() => this.n == 0;
/// <summary>
/// 获得堆中最大元素。
/// </summary>
/// <returns></returns>
public key max() => this.pq[1];
/// <summary>
/// 获得堆中元素的数量。
/// </summary>
/// <returns></returns>
public int size() => this.n;
/// <summary>
/// 获取堆的迭代器，元素以降序排列。
/// </summary>
/// <returns></returns>
public ienumerator<key> getenumerator()
{
maxpq<key> copy = new maxpq<key>(this.n);
for (int i = 1; i <= this.n; i++)
copy.insert(this.pq[i]);
while (!copy.isempty())
yield return copy.delmax(); // 下次迭代的时候从这里继续执行。
}
/// <summary>
/// 获取堆的迭代器，元素以降序排列。
/// </summary>
/// <returns></returns>
ienumerator ienumerable.getenumerator()
{
return getenumerator();
}
/// <summary>
/// 使元素上浮。
/// </summary>
/// <param name="k">需要上浮的元素。</param>
private void swim(int k)
{
while (k > 1 && less(k / 2, k))
{
exch(k, k / 2);
k /= 2;
}
}
/// <summary>
/// 使元素下沉。
/// </summary>
/// <param name="k">需要下沉的元素。</param>
private void sink(int k)
{
while (k * 2 <= this.n)
{
int j = 2 * k;
if (j < this.n && less(j, j + 1))
j++;
if (!less(k, j))
break;
exch(k, j);
k = j;
}
}
/// <summary>
/// 重新调整堆的大小。
/// </summary>
/// <param name="capacity">调整后的堆大小。</param>
private void resize(int capacity)
{
key[] temp = new key[capacity];
for (int i = 1; i <= this.n; i++)
{
temp[i] = this.pq[i];
}
this.pq = temp;
}
/// <summary>
/// 判断堆中某个元素是否小于另一元素。
/// </summary>
/// <param name="i">判断是否较小的元素。</param>
/// <param name="j">判断是否较大的元素。</param>
/// <returns></returns>
private bool less(int i, int j)
=> this.pq[i].compareto(this.pq[j]) < 0;
/// <summary>
/// 交换堆中的两个元素。
/// </summary>
/// <param name="i">要交换的第一个元素下标。</param>
/// <param name="j">要交换的第二个元素下标。</param>
private void exch(int i, int j)
{
key swap = this.pq[i];
this.pq[i] = this.pq[j];
this.pq[j] = swap;
}
/// <summary>
/// 检查当前二叉树是不是一个最大堆。
/// </summary>
/// <returns></returns>
private bool ismaxheap() => ismaxheap(1);
/// <summary>
/// 确定以 k 为根节点的二叉树是不是一个最大堆。
/// </summary>
/// <param name="k">需要检查的二叉树根节点。</param>
/// <returns></returns>
private bool ismaxheap(int k)
{
if (k > this.n)
return true;
int left = 2 * k;
int right = 2 * k + 1;
if (left <= this.n && less(k, left))
return false;
if (right <= this.n && less(k, right))
return false;
return ismaxheap(left) && ismaxheap(right);
}
}
}
另请参阅
2.4.7
题目
在堆中，最大的元素一定在位置 1 上，第二大的元素一定在位置 2 或者 3 上。
对于一个大小为 31 的堆，
给出第 k 大的元素可能出现的位置和不可能出现的位置，
其中 k=2、3、4（设元素值不重复）。
解答
k = 2 时，
只可能出现在位置 2、3 上（根节点的子结点，深度为 2，根节点深度为 1）
k = 3 时，
可以直接是根节点的子结点（第 2 或第 3 位，深度为 2），
也可以是第二大元素的子结点（第 4~7 位，也就是深度为 3 的所有位置）
k = 4 时，
可以直接是根节点的子结点（深度为 2 的点）
也可以是第二大元素的子结点（深度为 3 的点）
也可以是第三大元素的子结点（深度为 4 的点）
故范围为第 2~15 位。
不难看出第 k 大元素只可能出现在深度＜k 的位置（\(k \ge 2\)）
即位置小于 \(2 ^ k - 1, (k \ge 2)\)
2.4.8
题目
回答上一道练习中第 k 小元素的可能和不可能的位置。
解答
不难看出第 k 大元素只可能出现在深度＜k 的位置（\(k \ge 2\)）
即位置小于 \(2^k - 1, (k \ge 2)\)。
出现范围为 \([2, \min \{2^k -1, n\}]\)，其中 n 为堆的大小。
2.4.9
题目
给出 a b c d e 五个元素可能构造出来的所有堆，
然后给出 a a a b b 这五个元素可能构造出来的所有堆。
解答
首先 a b c d e 中，根节点必须是 e （假设为最大堆）
d 只能选择 e 作为父结点。
c 可以选择 d 或者 e 作为父结点。
b 可以选择 c 或 d 或 e 作为父结点。
a 可以选择 b 或 c 或 d 或 e 作为父结点。
又由于堆的大小为 5，堆的结构固定，一共三层。
e 只能为根节点
d 可以在左侧或者右侧
当 d 在左侧时，
d 的子结点可以在 a b c 中任取两个，剩下一个当 e 的右侧子结点
总共有 a(3, 2) = 6 种
当 d 在右侧时，
c 的子结点只能取 a 和 b ，故只有 a(2, 2) = 2 种情况。
综上，最大堆总共有 6 + 2 = 8 种构造堆的方式。
最小堆的构造同理，也有 8 种构造方式。
故总共有 8 + 8 = 16 种构造方式。
构造方式（最大堆）：
最大堆
b 只能作为 b 的子结点，a 可以是 b 或 a 的子结点。
根节点恒为 b
第二层结点有两种选择 a b 和 b a
第三层只有一种选择 a a
故总共有两种构造堆的方式。
最小堆
根节点恒为 a
第二层可以是 a a 或 a b
第二层是 a a 时
第三层只能选择 b b
第二层时 a b 时
第三层可选择 a b 或 b a
故总共有三种构造堆的方式。
综上所述，总共有 2 + 3 = 5 种构造方式。
构造方式（全部）：
2.4.10
题目
假设我们不想浪费堆排序的数组 pq[] 中的那个位置，
将最大元素放在 pq[0]，它的子结点放在 pq[1] 和 pq[2]，以此类推。
pq[k] 的父结点和子结点在哪里？
解答
左子树位于 \(2k+1\)，右子树位于 \(2k+2\)，父结点位于 \(\lfloor (i-1)/2 \rfloor\) 。
2.4.11
题目
如果你的应用中有大量插入元素的操作，但只有若干删除最大元素的操作，
哪种优先队列的实现方法更有效：堆、无序数组、有序数组？
解答
有大量插入操作，选择插入操作为常数级别的无序数组实现较为合适。
2.4.12
题目
如果你的应用场景中大量的找出最大元素的操作，但插入元素和删除最大元素操作相对较少，
哪种优先队列的实现方法更有效：堆、无序数组、有序数组？
解答
有序数组，查找最大元素操作是 o(1) 的。
堆要看具体实现，基于数组的实现和有序数组类似，
在插入操作较多的情况下甚至会优于有序数组。
注：
官网给出的堆实现会在插入/删除操作之后对整个数组进行检查，
确认是否为最大堆（ismaxheap 方法）。
在测试时务必删除这部分代码。
2.4.13
题目
想办法在 sink() 中避免检查 j<n。
解答
在官方实现的基础上直接删除 j<n 语句，随后在 delmax() 方法中在 sink(1) 之前让 pq[n + 1] = pq[1] 即可。
首先保存最大值，然后把堆中的第一个元素和最后一个元素交换，随后使 n = n - 1。
随后让 pq[n + 1] = pq[1]，这样在下沉操作时就不会下沉到 pq[n + 1]了。（相等的元素是不会交换的）
故之后的 sink() 语句中不再需要进行边界判断，直接删去即可。
修改后 delmax() 的代码如下：
public key delmax()
{
if (isempty())
throw new argumentoutofrangeexception("priority queue underflow");
key max = this.pq[1];
exch(1, this.n--);
pq[n + 1] = pq[1];
sink(1);
this.pq[this.n + 1] = default(key);
if ((this.n > 0) && (this.n == this.pq.length / 4))
resize(this.pq.length / 2);
debug.assert(ismaxheap());
return max;
}
2.4.14
题目
对于没有重复元素的大小为 n 的堆，一次删除最大元素的操作中最少要交换几个元素？
构造一个能够达到这个交换次数的大小为 15 的堆。
连续两次删除最大元素呢？三次呢？
解答
对于 n <= 2 的堆
第一步让最大元素和末端元素交换。
第二步下沉时由于 n <= 1，不需要交换。
故总共发生了一次交换，两个元素发生了交换。
对于 n = 3 的堆
第一步让最大元素和末端元素交换。
第二步如果末端元素大于另一侧的子结点，那么就不需要交换。
故最优情况时总共发生一次交换，两个元素被交换。
对于 n > 3 的堆。
第一步需要让最末端元素和最大元素交换。
由于堆中第二大的元素必定位于根节点之后。
故最末端元素一定小于该第二大元素。
因此在下沉操作时必定会和第二大元素进行交换。
故至少发生两次交换，总共有三个元素发生了交换。
构造的堆（n=15）
92 和 100 交换，随后 92 和 99 交换
构造最优情况堆的方式如下（取根结点为 100）：
对于每个结点，左子结点大于右子结点，
且左子结点的子元素都小于右子树的最小值，
（上例中省略了这部分元素，可以将它们当作负数）
于是第一次 delmax 的时候，只需要两次交换，三个元素被交换。
（即 87 最后被交换到上例中 99 的位置）
第二次 delmax 的时候，只需要三次交换，六个元素被交换.
（88 交换到 97 的位置）
因此当 n > 7 时，连续两次 delmax() 最少只需要 5 次交换。
第三次 delmax 的时候，只需要四次交换，九个元素被交换。
（89 交换到 95 的位置）
因此当 n > 15 时，连续三次 delmax() 最少只需要 9 次交换。
2.4.15
题目
设计一个程序，在线性时间内检测数组 pq[] 是否是一个面向最小元素的堆。
解答
minpq 的官方实现见：https://algs4.cs.princeton.edu/24pq/minpq.java.html
事实上只需要把 maxpq 中的比较调换方向即可。
在线性时间内检测是否是面向最小元素的堆的方法：
/// <summary>
/// 确定以 k 为根节点的二叉树是不是一个最小堆。
/// </summary>
/// <param name="k">需要检查的二叉树根节点。</param>
/// <returns></returns>
private bool isminheap(int k)
{
if (k > this.n)
return true;
int left = 2 * k;
int right = 2 * k + 1;
if (left <= this.n && greater(k, left))
return false;
if (right <= this.n && greater(k, right))
return false;
return isminheap(left) && isminheap(right);
}
用递归方法遍历整个二叉树，确认都满足堆的性质。由于每个结点都只会被比较三次（与父结点比较一次，与每个子结点各比较一次），由于 3n~n，因此这个方法是 o(n) 的。
代码
最小堆的接口 iminpq。
using system;
namespace priorityqueue
{
/// <summary>
/// 实现优先队列 api 的接口。（最小堆）
/// </summary>
/// <typeparam name="key">优先队列容纳的元素。</typeparam>
public interface iminpq<key> where key : icomparable<key>
{
/// <summary>
/// 向优先队列中插入一个元素。
/// </summary>
/// <param name="v">插入元素的类型。</param>
void insert(key v);
/// <summary>
/// 返回最小元素。
/// </summary>
/// <returns></returns>
key min();
/// <summary>
/// 删除并返回最小元素。
/// </summary>
/// <returns></returns>
key delmin();
/// <summary>
/// 返回队列是否为空。
/// </summary>
/// <returns></returns>
bool isempty();
/// <summary>
/// 返回队列中的元素个数。
/// </summary>
/// <returns></returns>
int size();
}
}
minpq.cs
using system;
using system.collections;
using system.collections.generic;
using system.diagnostics;
namespace priorityqueue
{
/// <summary>
/// 最小堆。（数组实现）
/// </summary>
/// <typeparam name="key">最小堆中保存的元素类型。</typeparam>
public class minpq<key> : iminpq<key>, ienumerable<key> where key : icomparable<key>
{
private key[] pq; // 保存元素的数组。
private int n; // 堆中的元素数量。
/// <summary>
/// 默认构造函数。
/// </summary>
public minpq() : this(1) { }
/// <summary>
/// 建立指定容量的最小堆。
/// </summary>
/// <param name="capacity">最小堆的容量。</param>
public minpq(int capacity)
{
this.pq = new key[capacity + 1];
this.n = 0;
}
/// <summary>
/// 从已有元素建立一个最小堆。（o(n)）
/// </summary>
/// <param name="keys">已有元素。</param>
public minpq(key[] keys)
{
this.n = keys.length;
this.pq = new key[keys.length + 1];
for (int i = 0; i < keys.length; i++)
this.pq[i + 1] = keys[i];
for (int k = this.n / 2; k >= 1; k--)
sink(k);
debug.assert(isminheap());
}
/// <summary>
/// 删除并返回最小元素。
/// </summary>
/// <returns></returns>
public key delmin()
{
if (isempty())
throw new argumentoutofrangeexception("priority queue underflow");
key min = this.pq[1];
exch(1, this.n--);
this.pq[this.n + 1] = this.pq[1];
sink(1);
this.pq[this.n + 1] = default(key);
if ((this.n > 0) && (this.n == this.pq.length / 4))
resize(this.pq.length / 2);
//debug.assert(isminheap());
return min;
}
/// <summary>
/// 向堆中插入一个元素。
/// </summary>
/// <param name="v">需要插入的元素。</param>
public void insert(key v)
{
if (this.n == this.pq.length - 1)
resize(2 * this.pq.length);
this.pq[++this.n] = v;
swim(this.n);
//debug.assert(isminheap());
}
/// <summary>
/// 检查堆是否为空。
/// </summary>
/// <returns></returns>
public bool isempty() => this.n == 0;
/// <summary>
/// 获得堆中最小元素。
/// </summary>
/// <returns></returns>
public key min() => this.pq[1];
/// <summary>
/// 获得堆中元素的数量。
/// </summary>
/// <returns></returns>
public int size() => this.n;
/// <summary>
/// 获取堆的迭代器，元素以降序排列。
/// </summary>
/// <returns></returns>
public ienumerator<key> getenumerator()
{
maxpq<key> copy = new maxpq<key>(this.n);
for (int i = 1; i <= this.n; i++)
copy.insert(this.pq[i]);
while (!copy.isempty())
yield return copy.delmax(); // 下次迭代的时候从这里继续执行。
}
/// <summary>
/// 获取堆的迭代器，元素以降序排列。
/// </summary>
/// <returns></returns>
ienumerator ienumerable.getenumerator()
{
return getenumerator();
}
/// <summary>
/// 使元素上浮。
/// </summary>
/// <param name="k">需要上浮的元素。</param>
private void swim(int k)
{
while (k > 1 && greater(k / 2, k))
{
exch(k, k / 2);
k /= 2;
}
}
/// <summary>
/// 使元素下沉。
/// </summary>
/// <param name="k">需要下沉的元素。</param>
private void sink(int k)
{
while (k * 2 <= this.n)
{
int j = 2 * k;
if (greater(j, j + 1))
j++;
if (!greater(k, j))
break;
exch(k, j);
k = j;
}
}
/// <summary>
/// 重新调整堆的大小。
/// </summary>
/// <param name="capacity">调整后的堆大小。</param>
private void resize(int capacity)
{
key[] temp = new key[capacity];
for (int i = 1; i <= this.n; i++)
{
temp[i] = this.pq[i];
}
this.pq = temp;
}
/// <summary>
/// 判断堆中某个元素是否大于另一元素。
/// </summary>
/// <param name="i">判断是否较大的元素。</param>
/// <param name="j">判断是否较小的元素。</param>
/// <returns></returns>
private bool greater(int i, int j)
=> this.pq[i].compareto(this.pq[j]) > 0;
/// <summary>
/// 交换堆中的两个元素。
/// </summary>
/// <param name="i">要交换的第一个元素下标。</param>
/// <param name="j">要交换的第二个元素下标。</param>
private void exch(int i, int j)
{
key swap = this.pq[i];
this.pq[i] = this.pq[j];
this.pq[j] = swap;
}
/// <summary>
/// 检查当前二叉树是不是一个最小堆。
/// </summary>
/// <returns></returns>
private bool isminheap() => isminheap(1);
/// <summary>
/// 确定以 k 为根节点的二叉树是不是一个最小堆。
/// </summary>
/// <param name="k">需要检查的二叉树根节点。</param>
/// <returns></returns>
private bool isminheap(int k)
{
if (k > this.n)
return true;
int left = 2 * k;
int right = 2 * k + 1;
if (left <= this.n && greater(k, left))
return false;
if (right <= this.n && greater(k, right))
return false;
return isminheap(left) && isminheap(right);
}
}
}
另请参阅
2.4.16
题目
对于 n=32，构造数组使得堆排序使用的比较次数最多以及最少。
解答
最好情况比较简单，只需要一个所有键值完全相同的数组即可。
最坏情况的构造方法参考了一篇论文（见「另请参阅」部分），结果如下：
最好输入：1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
最坏输入：1 4 7 12 10 16 14 19 17 20 5 27 8 28 2 24 9 18 6 23 11 22 21 31 13 26 25 30 15 29 3 32
代码
用于构造堆排序最坏情况的类。
using system;
using system.collections;
using system.collections.generic;
using system.diagnostics;
namespace priorityqueue
{
/// <summary>
/// 生成最大堆的最坏情况。参考论文：https://arxiv.org/abs/1504.01459
/// </summary>
public class maxpqworstcase
{
private int[] pq; // 保存元素的数组。
private int n; // 堆中的元素数量。
/// <summary>
/// 建立指定容量的最大堆。
/// </summary>
/// <param name="capacity">最大堆的容量。</param>
public maxpqworstcase(int capacity)
{
this.pq = new int[capacity + 1];
this.n = 0;
}
/// <summary>
/// 制造堆排序的最坏情况。
/// </summary>
/// <param name="n">需要构造的数组大小。</param>
/// <returns>最坏情况的输入数组。</returns>
public int[] makeworst(int n)
{
int[] strategy = win(n);
for (int i = 0; i < strategy.length; i++)
{
unremovemax(strategy[i]);
}
for (int i = 1; i <= this.n / 2; i++)
unfixheap(i);
int[] worstcase = new int[n];
for (int i = 1; i <= n; i++)
worstcase[i - 1] = this.pq[i];
return worstcase;
}
private bool less(int i, int j) => this.pq[i].compareto(this.pq[j]) < 0;
private int pulldown(int i, int j)
{
int toreturn = this.pq[j];
for (int m = j; m / 2 >= i; m /= 2)
{
this.pq[m] = this.pq[m / 2];
}
return toreturn;
}
private void unfixheap(int i)
{
int j = (int)(i * math.pow(2, math.floor(math.log10(this.n / i) / math.log10(2))));
this.pq[i] = pulldown(i, j);
}
private void unremovemax(int i)
{
int p = (this.n + 1) / 2;
if (less(p, i))
return;
this.n++;
this.pq[this.n] = pulldown(1, i);
this.pq[1] = this.n;
}
private int[] par(int l)
{
int n = (int)math.pow(2, l) - 1;
int[] s7 = { 0, 1, 2, 3, 4, 4, 5 };
int[] strategy = new int[n];
for (int i = 0; i < math.min(n, 7); i++)
{
strategy[i] = s7[i];
}
if (n <= 7)
return strategy;
for (int lev = 3; lev < l; lev++)
{
int i = (int)math.pow(2, lev) - 1;
strategy[i] = i;
strategy[i + 1] = i - 1;
strategy[i + 2] = i + 1;
strategy[i + 3] = i + 2;
strategy[i + 4] = i + 4;
strategy[i + 5] = i + 3;
for (int k = i + 6; k <= 2 * i; k++)
{
strategy[k] = k - 1;
}
}
return strategy;
}
private int[] win(int n)
{
int[] strategy = new int[n];
int[] s = par((int)math.floor(math.log10(n) / math.log10(2)) + 1);
for (int i = 1; i <= n - 1; i++)
{
strategy[i] = s[i];
}
int i = (int)math.pow(2, math.floor(math.log10(n + 1) / math.log10(2))) - 1;
if ((n == i) || (n <= 7))
return strategy;
strategy[i] = i;
if (n == i + 1)
return strategy;
strategy[i + 1] = (i + 1) / 2;
if (n == i + 2)
return strategy;
for (int i = i + 2; i <= n - 1; i++)
{
if (i == 2 * i - 2)
strategy[i] = i;
else
strategy[i] = i - 1;
}
return strategy;
}
}
}
另请参阅
给出堆排序最坏情况构造方法的论文
suchenek m a. a complete worst-case analysis of heapsort with experimental verification of its results, a manuscript (ms)[j]. arxiv preprint arxiv:1504.01459, 2015.
本题用到的库文件
priorityqueue 库
2.4.17
题目
证明：构造大小为 k 的面向对象最小元素的优先队列，
然后进行 n-k 次替换最小元素操作（删除最小元素后再插入元素）后，
n 个元素中的前 k 大元素均会留在优先队列中。
解答
英文版原文是：insert followed by remove the minimum，因此是先插入再删除。
大致上相当于一个缓冲区，把比较大的留下来，比较小的筛出去。
首先我们有一个大小为 k 的优先队列，保证最小值在最前。
接下来我们插入一个元素，可以分成两种情况。
如果插入的元素比最小值还要小，那么这个插入的元素会在之后被删除，原队列中的元素不变。
如果插入的元素比最小值大（或者相等），那么最小值会被删除，留下插入的元素。
于是可以观察到这样一个逻辑，在不断的插入过程中，比较小的元素会被过滤，只留下较大的元素。
那么我们可以把题目转化为：
向一个优先队列插入 n 个元素，保证队列的大小不超过 k，如果超过 k 了就删除最小值。
那么前 k 次插入不受影响，之后的 n-k 次插入就会按照之前说过的流程进行。
最后只留下 n 个元素中较大的 k 个元素，得证。
2.4.18
题目
在 maxpq 中，如果一个用例使用 insert() 插入了一个比队列中的所有元素都大的新元素，随后立即调用 delmax()。
假设没有重复元素，此时的堆和进行这些操作之前的堆完全相同吗？
进行两次 insert()
（第一次插入一个比队列所有元素都大的元素，第二次插入一个更大的元素）
操作接两次 delmax() 操作呢？
解答
首先看第一种情况，一次 insert() 接一次 delmax()。
由于插入的数比堆中的所有元素都大，这个元素会一路上升到根结点。
记上升路径上的点为 $ a_1,a_2,a_3, \dots , a_k $，其中 $ a_k $ 是插入的结点，$ a_1 $ 是根结点。
插入完成后路径上点的次序变为 $ a_k, a_1, a_2, \dots, a_{k-1} $ 。
随后进行一次 delmax()，先做交换，次序变为 $ a_{k-1}, a_1, \dots, a_{k-2}, a_k $ 。
由于 $ a_1 $ 是堆中原来的最大值，下沉时一定会和它交换。
根据定义，二叉堆是父结点总是优于子结点的完全二叉树，因此以后续结点作为根结点的子树也都是堆。
故同理 $ a_{k-1} $ 会和 $ a_2, a_3, \dots,a_{k-2} $ 交换，即沿原路径返回。
因此这种情况下前后堆不发生改变。
然后看第二种情况，操作顺序为 insert() insert() delmax() delmax()。
根据之前的结论，插入最大结点之后立即删除最大元素不会使堆发生变化，中间的两个操作抵消。
序列变为：insert() delmax()。
同理再次利用刚才的结论，操作抵消，堆不发生变化。
故第二种情况也不会使堆发生改变。
2.4.19
题目
实现 maxpq 的一个构造函数，接受一个数组作为参数。
使用正文 2.4.5.1 节中所述的自底向上的方法构造堆。
解答
官方实现已经包含了这部分的代码，见：https://algs4.cs.princeton.edu/24pq/maxpq.java.html
相应的构造函数（java）
public maxpq(key[] keys) {
n = keys.length;
pq = (key[]) new object[keys.length + 1];
for (int i = 0; i < n; i++)
pq[i+1] = keys[i];
for (int k = n/2; k >= 1; k--)
sink(k);
assert ismaxheap();
}
代码
构造函数（c#）
/// <summary>
/// 从已有元素建立一个最大堆。（o(n)）
/// </summary>
/// <param name="keys">已有元素。</param>
public maxpq(key[] keys)
{
this.n = keys.length;
this.pq = new key[keys.length + 1];
for (int i = 0; i < keys.length; i++)
this.pq[i + 1] = keys[i];
for (int k = this.n / 2; k >= 1; k--)
sink(k);
debug.assert(ismaxheap());
}
另请参阅
2.4.20
题目
证明：基于下沉的堆构造方法使用的比较次数小于 2n，交换次数小于 n。
解答
官网给出了解答：
首先介绍第一种解法。
设叶子结点的高度为 $ 0 $，根结点的高度为 $ h $。
于是某个结点 sink 时的最大交换次数即为该结点的高度。
故某一层结点的最大交换次数为 该层结点数 × 该层的高度。
于是总交换次数最大为：
\[
\begin{align*}
& h+2(h-1)+2^2(h-2)+ \dots + 2^h(0) \\
& =\sum_{k=0}^{h-1} 2^k(h-k) \\
& =h\sum_{k=0}^{h-1}2^k - \sum_{k=0}^{h-1}k2^k \\
\end {align*}
\]
第一项为等比数列的和，第二项为等差数列乘以等比数列的和。
于是第一项可以直接通过公式求得，第二项可以利用错位相减法求得。
\[
\begin{align*}
& h\sum_{k=0}^{h-1}2^k - \sum_{k=0}^{h-1}k2^k \\
& =h2^{h}-h-\sum_{k=0}^{h-1}k2^k \\
& =h2^{h}-h +\sum_{k=0}^{h-1} k2^k - 2\sum_{k=0}^{h-1} k2^k \\
& =h2^{h}-h+2^h - 2-(h-1)2^h \\
& =2^{h+1}-h-2 \\
& =n-h-1 \le n
\end{align*}
\]
于是交换次数小于 $ n $，比较次数小于 $ 2n $。
另一种解法，可以配合官网的图片帮助理解。
首先堆中某个结点最多一路下沉到叶子结点，
最大交换次数就是该结点的高度（记叶子结点的高度为 0）。
考虑根结点一路下沉到叶子结点的轨迹，
设为 $ a_0, a_1, a_2, ... , a_k $，其中 $ k $ 为根结点的高度，$ a_0 $ 是根结点。
$ a_0 $ 下沉后结点顺序变为 $ a_1, a_2, ..., a_k, a_0 $ 。
根据下沉的定义，有 $ a_1 > a_2 > \dots > a_k > a_0 $ 。
因此 $ a_1 $ 下沉时不可能与 $ a_2 $ 交换，而会向另一个方向下沉。
其余结点同理，可以发现每个结点的下沉路径不会与其他结点重合。
一棵完全二叉树共有 $ n - 1 $ 条边，每访问一条边代表进行了一次交换。
故交换次数必定小于 $ n $，比较次数为交换次数的两倍小于 $ 2n $。
2.4.21
题目
基础数据结构。
说明如何使用优先队列实现第一章中的栈、队列和随机队列这几种数据结构。
解答
给元素添上序号组成结点，按照序号排序即可，每个结点可以用类似于这样的实现：
class elemtype<t> : icomparable<elemtype<t>>
{
private int key;
private t element;
public elemtype(int key) => this.key = key;
public int compareto(elemtype<t> other)
{
return this.key.compareto(other.key);
}
}
栈：
用最大元素在最前的优先队列。
每个结点都包含一个元素和一个序号，
插入新元素时序号递增，这样最后插入的元素总在最前。
队列：
用最小元素在最前的优先队列。
每个结点都包含一个元素和一个序号，
插入新元素时序号递增，这样最先插入的元素总在最前。
随机队列：
优先队列的选择任意
每个结点都包含一个元素和一个序号，
插入新元素时随机指定一个序号，这样元素的顺序就是任意的了。
2.4.22
题目
调整数组大小。
在 maxpq 中加入调整数组大小的代码，
并和命题 q 一样证明对于一般性长度为 n 的队列其数组访问的上限。
解答
官方实现中已经包含了调整数组大小的代码，见：https://algs4.cs.princeton.edu/24pq/maxpq.java.html
截取如下：
// helper function to double the size of the heap array
private void resize(int capacity) {
assert capacity > n;
key[] temp = (key[]) new object[capacity];
for (int i = 1; i <= n; i++) {
temp[i] = pq[i];
}
pq = temp;
}
只要在队列快满时重新分配空间，再把元素复制进去即可。
在不触发重新分配空间的情况下，
每次队列操作的比较次数上限就等于命题 q 中给出的 $ \lg n+1 $（插入） 和 $ 2\lg n $（删除）。
插入元素最多需要 $ \lg n $ 次交换（比较次数-1），
删除元素最多需要 \(1 + \lg n - 1 = \lg n\) 次交换 （注意开始时有一次交换）。
同时一次比较需要 $ 2 $ 次数组访问，一次交换需要 \(4\) 次数组访问（记 a[i] 为一次数组访问）。
换算成数组访问次数就是 $ 6 \lg n + 2 $（插入）和 $ 8 \lg n $ （删除）。
在触发重新分配空间的情况下，需要额外的 $ 2n $ 次数组访问来重新分配空间。
故上限为 $ 6 \lg n +2n + 2 $ 和 $ 8 \lg n + 2n $。
如果取均摊分析，那么相当于把多出来的 $ 2n $ 次访问平均到 $ n $ 次操作中。
设第 $ n $ 次插入触发了重新分配空间，$ n $ 是 $ 2 $ 的幂。
重新分配空间进行了 $ 2 + 4 + 8 + 16 + ... + 2n = 2n - 2 $ 次数组访问。
平均到 $ n $ 次插入过程，每次插入多进行 $ 2 - 2 / n $ 次数组访问。
于是插入的上限变为 $ 6 \lg n + 4 - 2 / n $。
同理删除的上限变为 $ 8 \lg n + 2 - 2 / n $。
代码
重新分配空间（c#）
/// <summary>
/// 重新调整堆的大小。
/// </summary>
/// <param name="capacity">调整后的堆大小。</param>
private void resize(int capacity)
{
key[] temp = new key[capacity];
for (int i = 1; i <= this.n; i++)
{
temp[i] = this.pq[i];
}
this.pq = temp;
}
另请参阅
2.4.23
题目
multiway 的堆。
只考虑比较的成本且假设找到 t 个元素中的最大者需要 t 次比较，
在堆排序中使用 t 向堆的情况下找出使比较次数 nlogn 的系数最小的 t 值。
首先，假设使用的是一个简单通用的 sink() 方法；
其次，假设 floyd 方法在内循环中每轮可以节省一次比较。
解答
简单的 sink 实现
sink 方法会在所有的 $ t $ 个子结点中寻找最大的结点。
如果找到的结点比当前结点大，那么就进行交换。
否则视为结点已经下沉到了合适的位置，结束循环。
根据题意，在 $ t $ 个元素中找最大值需要 $ t $ 次比较。
sink 操作需要找到 $ t $ 个子结点中的最大值并与当前结点相比较。
于是 sink 操作每次最多需要 $ t + 1 $ 次比较。
建堆过程，对 2.4.20 的证明进行推广。
设 $ t $ 叉树的高度为 $ h $ ，叶子结点的高度为 $ 0 $，根结点的高度为 $ h $。
根据 sink 操作的定义，高度为 $ k $ 的结点最多进行 $ k $ 次交换（到达叶子结点）。
于是建堆需要的总交换次数为：
\[
\begin{align*}
& h+t(h-1)+t^2(h-2)+ \dots + t^h(0) \\
& =\sum_{k=0}^{h-1} t^k(h-k) \\
& =h\sum_{k=0}^{h-1}t^k - \sum_{k=0}^{h-1}kt^k \\
\end {align*}
\]
其中，第一个数列是等比数列，第二个数列是等差数列和等比数列之积，可以利用错位相减法求得，即：
\[
\begin{align*}
& h\sum_{k=0}^{h-1}t^k - \sum_{k=0}^{h-1}kt^k \\
& =\frac{h-ht^{h}}{1-t}-\sum_{k=0}^{h-1}kt^k \\
& =\frac{h-ht^{h}}{1-t} -\frac{\sum kt^k - t\sum kt^k}{1-t} \\
& =\frac{h-ht^h}{1-t}-\frac{t(1-t^{h-1})}{(1-t)^2}+\frac{(h-1)t^h}{1-t} \\
& =\frac{h-t^h}{1-t}-\frac{t(1-t^{h-1})}{(1-t)^2} \\
& =\frac{h-ht+t^{h+1}-t}{(1-t)^2}
\end{align*}
\]
考虑到对于 $ t $ 叉堆，结点数可以表示为 $ n=\frac{t^{h+1}-1}{t-1} $ 。故交换次数可以化简为：
\[
\begin{align*}
& \frac{h-ht+t^{h+1}-t}{(1-t)^2} \\
& =\frac{h-ht+t^{h+1}-t +1-1}{(1-t)^2} \\
& =\frac{t^{h+1}-1}{(1-t)^2}+\frac{h-ht-t+1}{(1-t)^2} \\
& =-\frac{n}{1-t}+\frac{h}{1-t}+\frac{1}{1-t} \\
& =\frac{n-h-1}{t-1} \le n
\end{align*}
\]
故建堆所需比较次数最大为 $ (t+1)n $。
每次删除最大元素都会对根结点调用一次 sink 操作，
因此排序所需的比较次数最多为 $ (t+1)n\log_t(n) $。
相加得堆排序所需的总交换次数最多为 $ (t+1)n + (t+1)n\log_t(n) =(t+1)(n\log_tn+n) $ 。
利用换底公式将对数的底换成 2，得到：$ \frac{t+1}{\lg t} n\log n $。
于是问题变为求 $ f(t)= \frac{t+1}{\lg t} $ 的最小值，对其求导，得到：
\[
( \frac{t+1}{\lg t} )'=\frac{-t+t\ln t-1}{t\ln^2t}·\ln 2
\]
直接求导数的零点会比较困难，但利用勘根公式可以寻找到根所在的区间。
由于 \(\ln 2\) 不影响正负，我们直接将其去掉，变为
\[
\frac{-t+t\ln t-1}{t\ln^2t}=\frac{-1+\ln t-\frac{1}{t}}{\ln^2t}
\]
由于 $ t > 1 $，分母总是为正，因此导函数正负就等于下面这个函数的正负：
\[
\begin {align*}
g(t)=\ln t -1-\frac{1}{t}
\end {align*}
\]
$ t = e $ 时 $ g(t) < 0 $ ，$ t=e+1 $ 时 $ g(t) > 0 $。于是可以求得在 $ (e, e+1) $ 上 $ f(t) $ 存在极小值。
又由于 $ g(t) $ 在 $ (e + 1, +\infty) $ 始终为正，因此在 $ (e, e+1) $ 上存在的是最小值（$ t \ge 2 $）。
因为 $ t $ 为大于 $ 1 $ 的正整数，且 $ f(4) < f(3) $，故 $ t=4 $ 时系数最小，此时系数为 $ 2.5 $。
floyd 方法
在删除最大元素的过程中，根结点会和最后一个结点交换，然后对新的根结点执行 sink 操作。
大多数情况下，这个结点会被一路交换到树的最后一层。
因此我们省去 sink 操作中与自己比较的过程，直接和子结点中的较大者进行交换。
这样一路交换到树的底部，随后再让这个结点与自己的父结点比较，向上「回到」合适的位置。
大多数结点都不需要向上交换，
因此这样的优化可以减少比较次数（下降一层需要的比较次数从 $ t+1 $ 变为 $ t $）。
利用 floyd 方法对于建堆没有影响（建堆也可以使用 floyd 方法，参见「另请参阅」部分）。
于是建堆的比较次数仍为 $ (t+1)n $。
排序的比较次数变为 $ tn\log_t(n) $。
总的比较次数变为 $ (t+1)n + tn\log_t(n) $。
我们仍然只关心 \(n\lg n\) 的系数，系数为 $ f(t)= \frac{t}{\lg t} $。
按照之前的方法再求一次最小值，求得 $ t = 3 $ 时系数最小，此时系数为 $ 1.89 $。
另请参阅
floyd 提出的堆排序优化
floyd r w. algorithm 245: treesort[j]. communications of the acm, 1964, 7(12): 701.
通过将这种方法应用到建堆获得的快速建堆方法
mcdiarmid c j h, reed b a. building heaps fast[j]. journal of algorithms, 1989, 10(3): 352-365.
2.4.24
题目
使用链接的优先队列。
用堆排序的二叉树实现一个优先队列，但使用链表结构代替数组。
每个结点都需要三个链接：两个向下，一个向上。
你的实现即使在无法预知队列大小的情况下也能保证优先队列的基本操作所需时间为对数级别。
解答
链式实现，每个结点都包含一个指向父结点的指针和两个指向子结点的指针。
交换结点可以直接用交换两个结点的值来实现（与数组的实现一样），而不是对两个结点的指针进行交换。
于是 sink() 和 swim() 操作就比较简单，直接按照定义实现即可。
比较困难的是删除和插入结点，或者更具体的说，
如何找到按照完全二叉树定义下序号向后/向前一位的结点？
我们首先在堆里面维护两个指针，一个指向根结点（root），另一个指向当前最后一个结点（last）。
当需要插入新结点时，我们需要找到 last 的后一位的父结点，然后把新的结点插入为该结点的左子结点。
这段话可能比较绕，下面这个示意图可以帮助理解，有三种情况：
标黄的代表 last 指着的位置。
我们先从简单的说起，中间的第二种情况，新插入的结点应该放在右侧，即作为 last 的父结点的右子结点。
如果 last 已经是右子结点了，那么就考虑第三种情况。
此时应该向上回溯，直到在某一次回溯中，结点是从父结点的左侧回溯上来的
（即图中路径 a-b-b，b-b 这一步是从左子树回溯上来的）。
于是待插入的位置就在该父结点的右子树的最左侧结点（即图中根结点的右子结点 a）。
最后是图中第一种情况，整棵树已经是满二叉树了。
这种情况下会一路回溯到根结点，那么只要一路下沉到最左侧的叶子结点，把新结点插入到其左子树上即可。
删除结点同理，也是这三种情况，只是需要找前一个结点，判断条件中的左右正好相反。
如果已经是右子结点了，只需要把 last 改为其父结点的左子树即可。
如果是左子结点，就需要回溯，直到某一次回溯是从右子树回溯上来的，last 应该指向其左子树的最右侧结点。
如果删除后正好变成满二叉树，那么会一直回溯到根结点，last 应该指向整棵树的最右侧结点。
代码实现中还需要处理只有一个结点以及没有结点时的特殊情况。
根据上面的算法，插入/删除找到相应位置所需的最大耗时为 2lgn
（从树的一侧回溯到根结点，再下沉到另一侧的底部）。
sink 和 swim 是 o(lgn) 级的，因此整个插入/删除操作是 o(lgn) 的。
代码
using system;
namespace priorityqueue
{
/// <summary>
/// 基于链式结构实现的最大堆。
/// </summary>
/// <typeparam name="key">优先队列中保存的数据类型。</typeparam>
public class maxpqlinked<key> : imaxpq<key> where key : icomparable<key>
{
/// <summary>
/// 二叉