2.4.31 #
解答 #
首先可以观察到堆有这样一个性质，从根结点到某一个叶子结点的路径是有序的，满足二分查找的条件。
但是，
从叶子结点到根结点的路径可以通过不断地令 k = k / 2 得到（从下往上只有一条路径）。
但从根结点到叶子结点的路径却不能简单地通过 k = k * 2 得到（从上往下会有两条分支）。
因此只通过堆本身是无法满足二分查找对于随机访问的要求的。
为了达到 ~loglogN 次比较，我们需要对 Swim() 方法做修改，
即，先通过一个数组来保存路径，再对这个数组进行二分查找，从而获得合适的祖先结点。
路径的长度是 ~logN（完全二叉树的性质），于是二分查找的比较次数即为 ~loglogN。
删除操作原本就是 ~2logN 的，不需要修改。
注意这样的方法仅仅只是减少了比较次数，
为了保持堆的有序，即使找到了结点的合适位置也不能直接插入，
仍然需要将路径上的结点依次下移，空出位置后再插入结点，复杂度仍然是 ~logN。
由于增加了保存路径等操作（建立了大量的小数组），实际算法的运行时间是增加的。
也可以用空间换时间，由于在堆中下标为 k 的结点到根结点的路径是唯一确定的。
因此可以提前计算好路径，用一个数组保存起来（数组的数组），在 Swim 中取出对应路径进行二分查找。
当然这样是很不划算的，除非元素比较的开销非常大。
代码 #
修改后的 Swim() 方法，注意输入的路径是从下往上的。
private void Swim(int k)
{
if (k == 1)
return;
// 获取路径
var path = new List<int>();
var temp = k;
while (temp >= 1)
{
path.Add(temp);
temp /= 2;
}
// lo=插入结点的父结点 hi=根结点
int lo = 1, hi = path.Count - 1;
while (lo <= hi)
{
var mid = lo + (hi - lo) / 2;
if (Greater(k, path[mid]))
hi = mid - 1; // 当前值比较大，应该向下走
else
lo = mid + 1; // 值较小，向根结点方向走
}
for (var i = 1; i < lo; i++)
{
Exch(path[i - 1], path[i]);
}
}