2.4.34

2.4.34 #

解答 #

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

maxIndex()：pq[1] 就是最小元素的下标。

change()：首先修改 keys 数组中对应的元素，然后对堆中该下标进行重排序。

delete()：先从堆中删除元素，再把 keys 和 qp 数组中的对应元素初始化。

代码 #

/// <summary>
/// 返回最大元素对应的索引。
/// </summary>
/// <returns>最大元素对应的索引。</returns>
/// <exception cref="ArgumentOutOfRangeException">当优先队列为空时抛出该异常。</exception>
public int MaxIndex()
{
    if (_n == 0)
        throw new InvalidOperationException("Priority Queue Underflow");
    return _pq[1];
}

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

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

另请参阅 #

PriorityQueue 库