2.4.31

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

首先可以观察到堆有这样一个性质,从根结点到某一个叶子结点的路径是有序的,满足二分查找的条件。

但是,
从叶子结点到根结点的路径可以通过不断地令 k = k / 2 得到(从下往上只有一条路径)。
但从根结点到叶子结点的路径却不能简单地通过 k = k * 2 得到(从上往下会有两条分支)。
因此只通过堆本身是无法满足二分查找对于随机访问的要求的。

为了达到 ~loglogN 次比较,我们需要对 Swim() 方法做修改,
即,先通过一个数组来保存路径,再对这个数组进行二分查找,从而获得合适的祖先结点。
路径的长度是 ~logN(完全二叉树的性质),于是二分查找的比较次数即为 ~loglogN。

删除操作原本就是 ~2logN 的,不需要修改。

注意这样的方法仅仅只是减少了比较次数,
为了保持堆的有序,即使找到了结点的合适位置也不能直接插入,
仍然需要将路径上的结点依次下移,空出位置后再插入结点,复杂度仍然是 ~logN。
由于增加了保存路径等操作(建立了大量的小数组),实际算法的运行时间是增加的。

也可以用空间换时间,由于在堆中下标为 k 的结点到根结点的路径是唯一确定的。
因此可以提前计算好路径,用一个数组保存起来(数组的数组),在 Swim 中取出对应路径进行二分查找。
当然这样是很不划算的,除非元素比较的开销非常大。

代码

修改后的 Swim() 方法,注意输入的路径是从下往上的。

/// <summary>
/// 使元素上浮。
/// </summary>
/// <param name="k">需要上浮的元素。</param>
private void Swim(int k)
{
    if (k == 1)
        return;

    // 获取路径
    int heapHeight = (int)(Math.Log(this.n) / Math.Log(2));
    List<int> path = new List<int>();
    int temp = k;
    while (temp >= 1)
    {
        path.Add(temp);
        temp /= 2;
    }

    // lo=插入结点的父结点 hi=根结点
    int lo = 1, hi = path.Count - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (Greater(k, path[mid]))
            hi = mid - 1;   // 当前值比较大,应该向下走
        else
            lo = mid + 1;   // 值较小,向根结点方向走
    }

    for (int i = 1; i < lo; i++)
    {
        Exch(path[i - 1], path[i]);
    }
}

另请参阅

PriorityQueue 库

上一题 下一题