使用min/max-heap算法时，优先级可能会改变。处理这种情况的一种方法是删除并插入元素以更新队列顺序。
对于使用数组实现的优先级队列，这可能会成为一个性能瓶颈，看起来可以避免，特别是在优先级更改小的情况下。
即使这不是优先级队列的标准操作, 这是一种可以根据我的需求进行修改的自定义实现。
是否有公认的最佳实践方法来更新min/max-heap中的元素？
背景信息：我不是二叉树的专家，我继承了一些代码，其中有一个性能瓶颈，即重新插入优先队列中的元素。我为最小堆制作了一个重新插入函数，对新元素进行重新排序——这比（删除和插入）有明显的改善，但这似乎是其他人可能已经用更优雅的方式解决的问题。
如果需要，我可以提供代码链接，但不想过多关注实现细节——因为这个问答可能可以保持通用。
通常的解决方法是将元素标记为无效，并插入一个新元素，然后在弹出无效条目时消除它们。
如果该方法不够用，则可以在 O(log n) 步骤内恢复最小堆不变式，只要知道正在更改的值的位置。
请回想一下，最小堆使用两个基本操作构建和维护，“siftup” 和 “siftdown”（尽管各种各样的来源对哪个是向上或向下有不同的看法）。其中一个将值推向树下面，另一个则将其向上浮动。
如果新值 x1 大于旧值 x0，则只需要修复 x 下面的树，因为 parent(x) ≤ x0 < x1。只需通过将 x 与其两个子节点中较小的那个交换而将 x 向下推到树中，同时 x 大于其子节点之一。
如果新值 x1 小于旧值 x，则 x 下面的树不需要调整，因为 x1 < x0 <= either_child(x)。相反，我们只需要向上移动，当 x 小于其父节点时交换 x 和其父节点。无需考虑兄弟节点，因为它们已经大于或等于可能用较小值替换的父节点。
不需要任何操作。现有的不变式不会改变。
测试1,000,000次：创建一个随机堆。更改随机选择的值。恢复堆条件。验证结果是最小堆。
from heapq import _siftup, _siftdown, heapify
from random import random, randrange, choice
def is_minheap(arr):
return all(arr[i] >= arr[(i-1)//2] for i in range(1, len(arr)))
n = 40
trials = 1_000_000
for _ in range(trials):
# Create a random heap
data = [random() for i in range(n)]
heapify(data)
# Randomly alter a heap element
i = randrange(n)
x0 = data[i]
x1 = data[i] = choice(data)
# Restore the heap
if x1 > x0: # value is increased
_siftup(data, i)
elif x1 < x0: # value is decreased
_siftdown(data, 0, i)
# Verify the results
assert is_minheap(data), direction
由于这篇文章包含了链接到可用代码的内容，因此我将为自己的问题发布答案。
实际上，这非常简单。
通常情况下，最小堆实现具有用于排序的函数，请参见示例：BubbleUp/Down。
这些函数可以在修改后的元素上运行，具体取决于相对于当前值的更改。例如：
if new_value < old_value {
heap_bubble_up(heap, node);
} else if new_value > old_value {
heap_bubble_down(heap, node);
}
std::pop_heap(h.begin(), h.end(), comp); h.pop_back(); h.push_back(newval); std::push_heap(h.begin(), h.end(), comp);。我认为通过更新顶部元素然后在该顶部元素上调用类似于您的“heap_down”的代码可以在比较数量上击败它（我尝试了递归和迭代实现）。结果：在所有情况下都比上述更多的比较。 - Oliver Schönrock__adjust_heap()中。我并没有真正理解它的确切作用，但它可以通过非常少的比较完成工作。 - Oliver Schönrock对于那些对各种算法的相对性能感兴趣的人，我进行了一些调查。
重点
heap.top()元素而已使用c++ STL的规范方法是：
// Note I am using a max-heap, but the comparator is customisable below
std::pop_heap(heap.begin(), heap.end(), comp);
heap.pop_back();
heap.push_back(newval);
std::push_heap(heap.begin(), heap.end(), comp);
这是一个非常简单的案例，没有“知道元素在堆中的位置”的问题。所以我们肯定可以做得更好，对吧……？
注意：对于那些感兴趣的人，我的应用程序是归并排序，其中一个大型数据文件被分成20-50个块，排序并写入磁盘。然后重新读取并合并到最终排序文件中。结果发现，选择从哪个文件合并下一个元素是瓶颈，所以我使用了std::priority_queue，它在底层使用了一个堆。然而，这仍然是瓶颈，很难跟上磁盘，并且在比较时受限于CPU。
以下代码研究了4种实现：
__adjust_heap后跟__push_heap算法我生成随机堆大小、内容和替换值，并迭代1M次。
结果
-O3 tailall优化时会自动优化递归），即使对于这个非常专业的情况，它们始终比STL有更多的比较。因此，仅仅使用堆原语并没有给你带来任何收益。典型结果：
method avg_cmp_cnt
std::heap / std::priority_queue 7.568285
bubble up recursively 8.031054
bubble up iteratively 8.047352
libstc++ __adjust_heap 6.327297
测试代码：
#include "fmt/core.h"
#include <algorithm>
#include <cassert>
#include <concepts>
#include <cstddef>
#include <cstdlib>
#include <execution>
#include <iostream>
#include <random>
#include <stdexcept>
template <std::unsigned_integral T>
T log2(T x) {
T log = 0;
while (x >>= 1U) ++log;
return log;
}
template <typename T, typename Comp = std::less<>>
void print_heap(const std::vector<T>& heap, Comp comp = {}) {
std::size_t levels = log2(heap.size()) + 1;
unsigned width = 6 * (1U << (levels - 1U));
std::cout << "\n\n";
for (const auto& e: heap) std::cout << e << " ";
std::cout << "\n";
std::cout << fmt::format("is_heap = {:}\n\n", std::is_heap(heap.begin(), heap.end(), comp));
if (heap.empty()) {
std::cout << "<empty heap>\n";
return;
}
unsigned idx = 0;
bool done = false;
for (unsigned l = 0; l != levels; ++l) {
for (unsigned e = 0; e != 1U << l; ++e) {
std::cout << fmt::format("{:^{}}", heap[idx], width);
++idx;
if (idx == heap.size()) {
done = true;
break;
}
}
width /= 2;
std::cout << "\n\n";
if (done) break;
}
}
template <typename T, typename Comp = std::less<>>
void replace_top_using_stl(std::vector<T>& heap, T newval, Comp comp = {}) {
if (heap.empty()) throw std::domain_error("can't replace_top on an empty heap");
assert(std::is_heap(heap.begin(), heap.end(), comp));
std::pop_heap(heap.begin(), heap.end(), comp);
heap.pop_back();
heap.push_back(newval);
std::push_heap(heap.begin(), heap.end(), comp);
}
template <typename T, typename Comp = std::less<>>
// NOLINTNEXTLINE recursion is tailcall eliminated by compiler
void bubble_down_recursively(std::vector<T>& heap, std::size_t i, Comp comp = {}) {
const auto left = 2 * i + 1;
const auto right = 2 * i + 2;
const auto n = heap.size();
using std::swap; // enable ADL
if (left >= n) { // no children
return;
} else if (right >= n) { // left exists right does not. NOLINT else after return
if (comp(heap[i], heap[left])) {
swap(heap[i], heap[left]);
bubble_down_recursively(heap, left, comp);
}
} else { // both children exist
// 'larger' is only well named if comp = std::less<>{}
auto larger = comp(heap[right], heap[left]) ? left : right;
if (comp(heap[i], heap[larger])) {
swap(heap[i], heap[larger]);
bubble_down_recursively(heap, larger, comp);
}
}
}
template <typename T, typename Comp = std::less<>>
void replace_top_using_bubble_down_recursively(std::vector<T>& heap, T newval, Comp comp = {}) {
if (heap.empty()) throw std::domain_error("can't replace_top on an empty heap");
assert(std::is_heap(heap.begin(), heap.end(), comp));
heap[0] = newval;
bubble_down_recursively(heap, 0, comp);
}
template <typename T, typename Comp = std::less<>>
void bubble_down_iteratively(std::vector<T>& heap, std::size_t i, Comp comp = {}) {
const auto n = heap.size();
while (true) {
const std::size_t left = 2 * i + 1;
const std::size_t right = 2 * i + 2;
std::size_t largest = i;
if ((left < n) && comp(heap[largest], heap[left])) {
largest = left;
}
if ((right < n) && comp(heap[largest], heap[right])) {
largest = right;
}
if (largest == i) {
break;
}
using std::swap; // enable ADL
swap(heap[i], heap[largest]);
i = largest;
}
}
template <typename T, typename Comp = std::less<>>
void replace_top_using_bubble_down_iteratively(std::vector<T>& heap, T newval, Comp comp = {}) {
if (heap.empty()) throw std::domain_error("can't replace_top on an empty heap");
assert(std::is_heap(heap.begin(), heap.end(), comp));
heap[0] = newval; // stick it in anyway
bubble_down_iteratively(heap, 0, comp); // and fix the heap
}
// borrowed from libstdc++ __push_heap
template <typename RandomAccessIterator, typename Distance, typename Tp, typename Compare>
constexpr void push_heap(RandomAccessIterator first, Distance holeIndex, Distance topIndex,
Tp value, Compare& comp) {
Distance parent = (holeIndex - 1) / 2;
while (holeIndex > topIndex && comp(*(first + parent), value)) {
*(first + holeIndex) = *(first + parent);
holeIndex = parent;
parent = (holeIndex - 1) / 2;
}
*(first + holeIndex) = std::move(value);
}
// borrowed from libstdc++ __adjust_heap
template <typename RandomAccessIterator, typename Distance, typename Tp, typename Compare>
constexpr void adjust_heap(RandomAccessIterator first, Distance holeIndex, Distance len, Tp value,
Compare comp) {
const Distance topIndex = holeIndex;
Distance secondChild = holeIndex;
while (secondChild < (len - 1) / 2) {
secondChild = 2 * (secondChild + 1);
if (comp(*(first + secondChild), *(first + (secondChild - 1)))) secondChild--;
*(first + holeIndex) = *(first + secondChild);
holeIndex = secondChild;
}
if ((len & 1) == 0 && secondChild == (len - 2) / 2) {
secondChild = 2 * (secondChild + 1);
*(first + holeIndex) = *(first + (secondChild - 1));
holeIndex = secondChild - 1;
}
push_heap(first, holeIndex, topIndex, value, comp);
}
template <typename T, typename Comp = std::less<>>
void replace_top_using_adjust_heap(std::vector<T>& heap, T newval, Comp comp = {}) {
if (heap.empty()) throw std::domain_error("can't replace_top on an empty heap");
assert(std::is_heap(heap.begin(), heap.end(), comp));
heap[0] = newval;
adjust_heap(heap.begin(), 0L, heap.end() - heap.begin(), newval, comp);
}
template <typename T>
struct cmp_counter {
static std::size_t cmpcount; // NOLINT must be static because STL takes Comp by value
bool operator()(T a, T b) {
++cmpcount;
return a < b; // effectively std::less<>{};
}
static void reset() { cmpcount = 0; }
};
template <typename T>
std::size_t cmp_counter<T>::cmpcount = 0; // NOLINT global static
int main() {
using ValueType = int;
struct method {
using cb_t = void (*)(std::vector<ValueType>&, ValueType, cmp_counter<ValueType>);
std::string label;
cb_t cb;
};
auto methods = std::vector<method>{
{"std::heap / std::priority_queue", &replace_top_using_stl},
{"bubble up recursively", &replace_top_using_bubble_down_recursively},
{"bubble up iteratively", &replace_top_using_bubble_down_iteratively},
{"libstc++ __adjust_heap", &replace_top_using_adjust_heap},
};
std::cout << fmt::format("{:35s} {:s}\n", "method", "avg_cmp_cnt");
for (auto& method: methods) {
auto prng = std::mt19937_64(1); // NOLINT fixed seed for repeatability
auto heap_element_dist = std::uniform_int_distribution<>(1, 1000);
auto heap_size_dist = std::uniform_int_distribution<std::size_t>(3, 100);
const std::size_t number_of_trials = 1'000'000;
std::size_t total_cmpcount = 0;
cmp_counter<ValueType> comp;
for (unsigned i = 0; i != number_of_trials; ++i) {
std::vector<int> h(heap_size_dist(prng));
std::generate(h.begin(), h.end(), [&] { return ValueType(heap_element_dist(prng)); });
std::make_heap(h.begin(), h.end(), comp);
auto newval = ValueType(heap_element_dist(prng));
cmp_counter<ValueType>::reset();
method.cb(h, newval, comp);
total_cmpcount += cmp_counter<ValueType>::cmpcount;
if (!std::is_heap(h.begin(), h.end(), comp)) {
std::cerr << method.label << "NOT A HEAP ANYMORE!!\n";
return EXIT_FAILURE;
}
}
std::cout << fmt::format("{:35s} {:f}\n", method.label,
double(total_cmpcount) / number_of_trials);
}
}