2.4.40 #
解答 #
如同书上所说，可以节省约 50% 的比较次数。
先沉后浮的实现也很简单，将 swim 方法加入，
然后修改 sink 方法，去掉其中检查是否需要下沉的条件（if(!Less(pq, k, j))），
然后在 sink 方法的循环之后调用 swim。
为了获得比较次数，你可以添加一个静态全局变量 compareCount，
然后修改 Less 方法，在作比较的同时使 compareCount++ ，
每次执行 Sort 时先让 compareCount 置零，最后返回 compareCount。
代码 #
public static class HeapFloyd
{
/// <summary>
/// 利用堆排序对数组进行排序。
/// </summary>
/// <param name="pq">需要排序的数组。</param>
public static void Sort<T>(T[] pq) where T : IComparable<T>
{
var n = pq.Length;
// 建堆
for (var k = n / 2; k >= 1; k--)
{
Sink(pq, k, n);
}
// 排序
while (n > 1)
{
Exch(pq, 1, n--);
SinkThenSwim(pq, 1, n);
}
}
/// <summary>
/// 令堆中的元素下沉。
/// </summary>
/// <param name="pq">需要执行操作的堆。</param>
/// <param name="k">需要执行下沉的结点下标。</param>
/// <param name="n">堆中元素的数目。</param>
private static void Sink<T>(T[] pq, int k, int n) where T : IComparable<T>
{
while (2 * k <= n)
{
var j = 2 * k;
if (j < n && Less(pq, j, j + 1))
j++;
if (!Less(pq, k, j))
break;
Exch(pq, k, j);
k = j;
}
}
/// <summary>
/// 先下沉后上浮。
/// </summary>
/// <typeparam name="T">堆中的元素类型。</typeparam>
/// <param name="pq">包含堆元素的数组。</param>
/// <param name="k">要下沉的元素。</param>
/// <param name="n">元素数量。</param>
private static void SinkThenSwim<T>(T[] pq, int k, int n) where T : IComparable<T>
{
while (2 * k <= n)
{
var j = 2 * k;
if (j < n && Less(pq, j, j + 1))
j++;
Exch(pq, k, j);
k = j;
}
Swim(pq, k);
}
/// <summary>
/// 使元素上浮。
/// </summary>
/// <param name="pq">优先队列。</param>
/// <param name="k">需要上浮的元素。</param>
private static void Swim<T>(T[] pq, int k) where T : IComparable<T>
{
while (k > 1 && Less(pq, k / 2, k))
{
Exch(pq, k, k / 2);
k /= 2;
}
}
/// <summary>
/// 比较堆中下标为 <paramref name="a"/> 的元素是否小于下标为 <paramref name="b"/> 的元素。
/// </summary>
/// <param name="pq">元素所在的数组。</param>
/// <param name="a">需要比较是否较小的结点序号。</param>
/// <param name="b">需要比较是否较大的结点序号。</param>
/// <returns>如果下标为 <paramref name="a"/> 的元素较小则返回 <c>true</c>，否则返回 <c>false</c>。</returns>
private static bool Less<T>(T[] pq, int a, int b) where T : IComparable<T> => pq[a - 1].CompareTo(pq[b - 1]) < 0;
/// <summary>
/// 交换堆中的两个元素。
/// </summary>
/// <param name="pq">要交换的元素所在堆。</param>
/// <param name="a">要交换的结点序号。</param>
/// <param name="b">要交换的结点序号。</param>
private static void Exch<T>(T[] pq, int a, int b)
{
var temp = pq[a - 1];
pq[a - 1] = pq[b - 1];
pq[b - 1] = temp;
}
}