2.4.26

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

解答

用类似于「半交换」的方法避免频繁调用 Exch() 方法。
上浮时,先单独保存待上浮的元素,随后进行比较,
如果当前 k 值对应的父结点(即 k/2 )小于待上浮的元素,令 pq[k]=pq[k/2]
否则令当前 k 值等于待上浮的元素,终止循环。
下沉的过程类似。

修改后的 sink 和 swim 方法:

/// <summary>
/// 使元素上浮。
/// </summary>
/// <param name="k">需要上浮的元素。</param>
private void Swim(int k)
{
    Key key = this.pq[k];
    while (k > 1 && this.pq[k / 2].CompareTo(key) < 0)
    {
        this.pq[k] = this.pq[k / 2];
        k /= 2;
    }
    this.pq[k] = key;
}

/// <summary>
/// 使元素下沉。
/// </summary>
/// <param name="k">需要下沉的元素。</param>
private void Sink(int k)
{
    Key key = this.pq[k];
    while (k * 2 <= this.n)
    {
        int j = 2 * k;
        if (Less(j, j + 1))
            j++;
        if (this.pq[j].CompareTo(key) < 0)
            break;
        this.pq[k] = this.pq[j];
        k = j;
    }
    this.pq[k] = key;
}

另请参阅

PriorityQueue 库

上一题 下一题