$\Huge\color{orchid}{点击此处获取更多干货}$

$\Large\color{black}{点击此处查看上篇}$

接着上篇，先说一下排序：
排序这事用不到插入位序。此处默认了排序规则是greater，那么堆顶每次取出的就是当前排序规则下最末尾的元素，也就是最小值。对长度$n$的序列先执行$n$次push将它们插入堆中，然后执行$n$轮输出$top()$和pop的操作，就可以按照排序规则的反序将序列有序输出（此处对应升序）
堆排序的问题在这里

然后介绍一下该问题出现的两种特殊操作：删除和更新第k个插入的元素
换个例子先看删除：

在这样的一个堆中，删除插入位序1的元素16，首先要根据插入位序1找到堆中的位置4，然后将此位置与末位交换，在base尾部删除，再从这个位置开始向下调整，维护堆性质，就像下图这样：

代码和$\text{pop}$函数类似，但考虑到插入位序k的元素必须要在堆中，因此如果$pos[k]$是0的话需要提前返回

/**
* @brief 删除第k次插入的元素
* @param k 待更新元素的插入位序
* 找到第k次插入的元素位置，并按照pop的类似流程执行
*/
template<class Elem, class Pred>
void PriorityQueue<Elem, Pred>::eraseKthElement(size_t k)
{
    size_t targetIdx = pos[k], endPos = base[size].insIdx;//两个节点分别对应了{targetIdx,k}和{size,endPos}
    if(targetIdx == 0) {    //排除不存在的情况
        return;
    }
    //接下来就跟pop类似了
    pos[k] = 0;
    pos[endPos] = targetIdx;
    swap(base[targetIdx], base[size]);
    base.pop_back();
    size--;
    adjustDown(targetIdx);
}

最后就是更新，一个很显而易见的步骤是找到第k次插入的元素位置，然后赋予新值。但考虑到更新后会破坏原有的堆结构，需要在此分三种情况讨论：
1. 新值和原值相同，什么都不做
2. 新值比原值“大”，则考虑向上调整
3. 新值比原值“小”，则考虑向下调整
这里的“大”“小”指的是当前排序规则下，靠前还是靠后
代码如下：

/**
* @brief 更新第k次插入的元素
* @param k 待更新的插入位序
* @param e 即将被赋予的新值
* @warning 插入位序k对应元素必须存在于堆中，否则抛出异常
*/
template<class Elem, class Pred>
void PriorityQueue<Elem, Pred>::updateKthElement(size_t k, Elem e)
{
    size_t targetIdx = pos[k];
    if (targetIdx == 0) {
        string errorInfo = "The " + to_string(k) + "th element do not exist";
        throw logic_error(errorInfo.c_str());
    }
    Elem pre = base[targetIdx].val;
    if (e == pre) {
        return;
    }
    else {
        base[targetIdx].val = e;
        if (pred(e, pre)) { //新值更靠前，向下调整
            adjustDown(targetIdx);
        }
        else {              //新值更靠后，向上调整
            adjustUp(targetIdx);
        }
    }
}