2.4.34

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

解答

这里给出最大堆的实现,原因同 2.4.33。

maxIndex()pq[1] 就是最小元素的下标。
change():首先修改 keys 数组中对应的元素,然后对堆中该下标进行重排序。
delete():先从堆中删除元素,再把 keysqp 数组中的对应元素初始化。

代码

/// <summary>
/// 返回最大元素对应的索引。
/// </summary>
/// <returns></returns>
public int MaxIndex()
{
    if (this.n == 0)
        throw new ArgumentOutOfRangeException("Priority Queue Underflow");
    return this.pq[1];
}

/// <summary>
/// 将与索引 <paramref name="i"/> 相关联的元素换成 <paramref name="k"/>。
/// </summary>
/// <param name="i">要修改关联元素的索引。</param>
/// <param name="k">用于替换的新元素。</param>
public void ChangeKey(int i, Key k)
{
    if (!Contains(i))
        throw new ArgumentNullException("队列中没有该索引");
    this.keys[i] = k;
    Swim(this.qp[i]);
    Sink(this.qp[i]);
}

/// <summary>
/// 删除索引 <paramref name="i"/> 对应的键值。
/// </summary>
/// <param name="i">要清空的索引。</param>
public void Delete(int i)
{
    if (!Contains(i))
        throw new ArgumentOutOfRangeException("index is not in the priority queue");
    int index = this.qp[i];
    Exch(index, this.n--);
    Swim(index);
    Sink(index);
    this.keys[i] = default(Key);
    this.qp[i] = -1;
}

另请参阅

PriorityQueue 库

上一题 下一题