在 C++ 中使用带有键更新的最小优先级队列的最简单方法

Question

有时在编程比赛等期间，我们需要一个带有递减键的最小优先级队列的简单工作实现来实现 Dijkstra 算法等。我经常使用 set<;对<键值，ID> >和一个数组（映射 ID-->key_value）一起来实现这一点。

• 向集合中添加一个元素需要 O(log(N)) 时间。要使用 N 个元素构建优先级队列，我们​​只需将它们一一添加到集合中。这总共需要 O(N log(N)) 时间。

• 具有最小 key_value 的元素只是集合中的第一个元素。探测最小元素需要 O(1) 时间。删除它需要 O(log(N)) 时间。

• 为了测试某个 ID=k 是否在集合中，我们首先在数组中查找其 key_value=v_k，然后在集合中搜索元素 (v_k, k)。这需要 O(log(N)) 时间。

• 要将某个 ID=k 的 key_value 从 v_k 更改为 v_k'，我们首先在数组中查找其 key_value=v_k，然后在集合中搜索元素 (v_k, k)。接下来，我们从集合中删除该元素，然后将元素 (v_k', k) 插入集合中。然后我们也更新数组。这需要 O(log(N)) 时间。

虽然上述方法可行，但大多数教科书通常建议使用二叉堆来实现优先级队列，因为构建二叉堆的时间仅为 O(N)。听说C++的STL中内置了一个使用二进制堆的优先级队列数据结构。但是，我不确定如何更新该数据结构的 key_value 。

在 C++ 中使用最小优先级队列和键更新的最简单、最有效的方法是什么？

Answer 1

虽然我的回答不会回答原来的问题，但我认为这对于尝试在 C++/Java 中实现 Dijkstra 算法（比如我自己）时遇到这个问题的人来说可能很有用，这是 OP 评论的，

priority_queue<如前所述，C++ 中的 /code>（或 Java 中的 PriorityQueue）不提供 decrease-key 操作。在实现 Dijkstra 时使用这些类的一个好技巧是使用“延迟删除”。 Dijkstra算法的主循环从优先级队列中提取下一个要处理的节点，并分析其所有相邻节点，最终改变优先级队列中节点的最小路径成本。这就是通常需要 decrease-key 来更新该节点的值的地方。

诀窍是根本不改变。相反，该节点的“新副本”（具有新的更好的成本）被添加到优先级队列中。由于成本较低，节点的新副本将在队列中的原始副本之前被提取，因此它将被更早地处理。

这种“惰性删除”的问题在于，节点的第二个副本具有较高的不良成本，最终将从优先级队列中提取。但是，在处理第二个添加的具有更好成本的副本之后，这种情况总是会发生。因此，从优先级队列中提取下一个节点时，主 Dijkstra 循环必须做的第一件事是检查该节点是否先前已被访问过（并且我们已经知道最短路径）。正是在那个精确的时刻，我们将进行“延迟删除”，并且必须简单地忽略该元素。

这种解决方案会产生内存和时间成本，因为优先级队列存储着我们尚未删除的“死元素”。但真正的成本将相当小，而且恕我直言，对这个解决方案进行编程比任何其他尝试模拟缺失的 decrease-key 操作的替代方案更容易。

Answer 2

好吧，正如达伦已经说过的， std::priority_queue没有办法降低元素的优先级，也没有删除除当前最小值之外的元素。但默认的 std::priority_queue 只不过是一个围绕 std::vector 的简单容器适配器，它使用 < 中的 std 堆函数。 /code> (std::push_heap， std::pop_heap 和 std::make_heap）。因此，对于 Dijkstra（需要优先更新的地方），我通常自己执行此操作并使用简单的 std::vector。

那么推送只是 O(log N) 操作

vec.push_back(item);
std::push_heap(vec.begin(), vec.end());

当然，为了从 N 个元素重新构造一个队列，我们​​不会使用这个 O(log N) 操作将它们全部推送（使整个事情变得 O(Nlog N)），但是只需将它们全部放入向量中，然后是一个简单的 O(N)

std::make_heap(vec.begin(), vec.end());

最小元素是一个简单的 O(1)

vec.front();

弹出是一个简单的 O(log N) 序列

std::pop_heap(vec.begin(), vec.end());
vec.pop_back();

到目前为止，这就是 std::priority_queuestd::priority_queue< /code> 通常在 兜帽。现在要更改项目的优先级，我们只需要更改它（但是它可能会合并到项目的类型中）并使序列再次成为有效的堆

std::make_heap(vec.begin(), vec.end());

我知道这是一个 O(N) 操作，但另一方面，这会删除任何需要使用附加数据结构或（更糟糕的是）项目类型的扩展来跟踪项目在堆中的位置。考虑到 std::vector 的易用性、紧凑性和线性内存使用（这也会影响运行时），并且考虑到对数优先级更新的性能损失实际上并不那么重要，而且事实上无论如何，我经常使用具有相当少边（顶点数呈线性）的图。

它可能并非在所有情况下都是最快的方法，但肯定是最简单的方法。

编辑：哦，由于标准库使用最大堆，您需要使用与 > 等效的内容来比较优先级（但是您从项目中获取它们），而不是默认的 < 运算符。

Answer 3

我不认为 std::priority_queue 类可以实现高效decrease-key 风格操作的实现。

我推出了自己的基于二进制堆的数据结构来支持这一点，基本上与您为基于 std::set 的优先级队列所描述的非常相似：

• 维护一个二进制堆，按以下顺序排序value 存储pair 的元素以及映射ID -> 的数组。堆索引。在堆例程 heapify_up、heapify_down 等中，有必要确保映射数组与元素的当前堆位置保持同步。这会增加一些额外的 O(1) 开销。
• 根据此处<描述的标准算法，可以在O(N)内完成数组到堆的转换。 /a>.
• 查看根元素的时间复杂度为O(1)。
• 检查ID当前是否在堆中只需要在映射数组中进行O(1)查找。这还允许 O(1) 查看与任何 ID 对应的元素。
• Decrease-key 需要在映射数组中进行 O(1) 查找，然后对映射数组进行 O(log(N)) 更新通过heapify_up、heapify_down进行堆。
• 将新项目推送到堆上的时间复杂度为 O(log(N))，就像从堆中弹出现有项目一样。

因此，与基于 std::set 的数据结构相比，一些操作的运行时间逐渐得到改善。另一个重要的改进是二叉堆可以在数组上实现，而二叉树是基于节点的容器。二进制堆的额外数据局部性通常会转化为改进的运行时间。

此实现的一些问题是：

• 它只允许整数项 ID。
• 它假设项目ID的分布紧密，从零开始（否则映射数组的空间复杂度会爆炸！）。

如果您维护映射哈希表而不是映射数组，则可能会克服这些问题，但运行时开销会稍多一些。对于我的使用来说，整数ID 一直就足够了。

希望这有帮助。

Answer 4

实际上，有一种方法可以使用标准 C++ 库中的内置二进制堆。关键的观察是所有堆函数的实现（即 std::push_heap , std::pop_heap和 std::make_heap) 仅需要类的存储元素中的以下方法A:

• 构造函数 A::A()
• 赋值运算符 A& A::operator=(const A& rhs)
• 比较运算符 bool 运算符<(const A& lhs, const A& rhs)

表示每当移动元素时都会调用赋值运算符在存储所有堆元素的容器中。通过重载该运算符，您可以控制堆中的索引。有了索引后，您可以访问堆中的元素，更改其值并调用 std： :push_heap 更新其在堆中的位置。

查看 Dijkstra 算法的简化实现（无图）：

#include <bits/stdc++.h>

using namespace std;

vector<int> queue_idx;

struct Elem {
    int label;
    int dist;
    bool operator<(const Elem& other) const { return dist > other.dist; }
    Elem& operator=(const Elem& other);
};

vector<Elem> q;

Elem& Elem::operator=(const Elem& other)
{
    label = other.label;
    dist = other.dist;
    queue_idx[label] = this - q.data();
    return *this;
}

void AddElem(int label, int dist)
{
    queue_idx[label] = label;
    q.push_back(Elem{label, dist});
}

void RemoveMin()
{
    pop_heap(q.begin(), q.end());
    Elem res = q.back();
    q.pop_back();
    cout << "dist to " << res.label << " is " << res.dist << endl;
}

void Relax(int label, int dist)
{
    int idx = queue_idx[label];
    Elem& elem = q[idx];
    if (elem.dist > dist)
    {
        elem.dist = dist;
        push_heap(q.begin(), q.begin() + idx + 1);
    }
}

int main()
{
    int n = 5;
    queue_idx.resize(n);
    AddElem(0, 0);
    for (int i = 1; i < n; ++i)
        AddElem(i, INT_MAX);
    make_heap(q.begin(), q.end());
    RemoveMin();
    Relax(1, 50);
    Relax(2, 40);
    Relax(4, 10);
    RemoveMin();
    Relax(3, 20);
    RemoveMin();
    Relax(1, 30);
    RemoveMin();
    Relax(2, 80);
    RemoveMin();
    return 0;
}

我知道这个解决方案取决于标准库的内部实现，但是它只适用于我所知道的任何编译器，并且我在编程比赛中使用了它。

Answer 5

我认为目前 C++ 中没有简单的方法（之前做了一些研究）。

但我可以发布这样一个数据结构的实现：

#include <cstdint>
#include <random>

using TrackingHeapIndex = int;
using TrackingHeapPriority = double;

struct InvVarInfo
{
  TrackingHeapIndex aVar_ = 0;
  TrackingHeapPriority balance_ = 0;

  InvVarInfo() = default;

  explicit InvVarInfo(const TrackingHeapIndex aVar, const TrackingHeapPriority balance)
    : aVar_(aVar), balance_(balance)
  {
  }
};

struct IviRandLess
{
  bool operator()(const InvVarInfo& a, const InvVarInfo& b) const
  {
    if (a.balance_ != b.balance_)
    {
      return a.balance_ < b.balance_;
    }
    return RandBitGen::glob_.Next();
  }
};

template <typename Compare>
struct TrackingHeap
{
  std::vector<TrackingHeapIndex> vTracker_;
  std::vector<InvVarInfo> items_;
  Compare comp_;

  explicit TrackingHeap(const Compare& comp) : comp_(comp) { }

  void InitEqual(const TrackingHeapIndex nItems)
  {
    assert(items_.size() == 0);
    items_.resize(nItems);
    vTracker_.resize(nItems+1);
    #pragma omp parallel for schedule(static, kRamPageBytes/(2*sizeof(TrackingHeapIndex)))
    for (TrackingHeapIndex i = 0; i < nItems; i++)
    {
      items_[i].aVar_ = i + 1;
      vTracker_[i+1] = i;
    }
  }

  void MakeHeap()
  {
    TrackingHeapIndex largestEven = 0;
    while(2 * size_t(largestEven) + 1 < items_.size())
    {
      largestEven = largestEven * 2 + 1;
    }
    for(TrackingHeapIndex iFirst = largestEven; ; iFirst=(iFirst-1) / 2)
    {
      const TrackingHeapIndex iLimit = std::min(items_.size(), size_t(iFirst)*2 + 1);
      #pragma omp parallel for schedule(guided, kCacheLineSize)
      for(TrackingHeapIndex i=iFirst; i<iLimit; i++)
      {
        TrackingHeapIndex iLeft, iRight, iSel, iParent = i;
        for(;;)
        {
          iLeft = 2 * iParent + 1;
          iRight = iLeft + 1;
          if(iRight < TrackingHeapIndex(items_.size()))
          {
            if(comp_(items_[iLeft], items_[iRight]))
            {
              iSel = iLeft;
            } else
            {
              iSel = iRight;
            }
          }
          else if(iLeft < TrackingHeapIndex(items_.size()))
          {
            iSel = iLeft;
          } else
          {
            break;
          }
          if(comp_(items_[iSel], items_[iParent]))
          {
            std::swap(items_[iSel], items_[iParent]);
            std::swap(vTracker_[abs(items_[iSel].aVar_)], vTracker_[abs(items_[iParent].aVar_)]);
            iParent = iSel;
          }
          else
          {
            break;
          }
        }
      }
      if(iFirst == 0)
      {
        break;
      }
    }
  }

  void BubbleDown(TrackingHeapIndex parent)
  {
    for (;;)
    {
      const TrackingHeapIndex leftChild = parent * 2 + 1;
      const TrackingHeapIndex rightChild = leftChild + 1;
      if (rightChild >= items_.size())
      {
        assert(items_.size() >= 1);
        if (parent + 1 < items_.size())
        {
          items_[parent] = std::move(items_.back());
          vTracker_[abs(items_[parent].aVar_)] = parent;
        }
        items_.pop_back();
        return;
      }
      TrackingHeapIndex selChild;
      if (comp_(items_[leftChild], items_[rightChild]))
      {
        selChild = leftChild;
      }
      else
      {
        selChild = rightChild;
      }
      items_[parent] = std::move(items_[selChild]);
      vTracker_[abs(items_[parent].aVar_)] = parent;
      parent = selChild;
    }
  }

  void BubbleUp(TrackingHeapIndex child)
  {
    while (child > 0)
    {
      const TrackingHeapIndex parent = (child - 1) / 2;
      if (comp_(items_[child], items_[parent]))
      {
        std::swap(items_[parent], items_[child]);
        std::swap(vTracker_[abs(items_[parent].aVar_)], vTracker_[abs(items_[child].aVar_)]);
        child = parent;
      }
      else
      {
        return;
      }
    }
  }

  bool Pop(InvVarInfo& target)
  {
    if (items_.empty())
    {
      return false;
    }
    target = std::move(items_[0]);
    vTracker_[abs(target.aVar_)] = -1;
    BubbleDown(0);
    return true;
  }

  void Push(InvVarInfo&& item)
  {
    items_.emplace_back(std::move(item));
    vTracker_[abs(items_.back().aVar_)] = items_.size() - 1;
    BubbleUp(items_.size() - 1);
  }

  bool Remove(const TrackingHeapIndex aVar)
  {
    const TrackingHeapIndex index = vTracker_[aVar];
    if(index < 0)
    {
      return false;
    }
    assert(0 <= index && index < items_.size());
    vTracker_[aVar] = -1;
    BubbleDown(index);
  }

  void OnBalanceUpdate(TrackingHeapIndex index, const InvVarInfo& old)
  {
    if (comp_(items_[index], old))
    {
      // higher priority
      BubbleUp(index);
      return;
    }
    for (;;)
    {
      const TrackingHeapIndex leftChild = index * 2 + 1;
      if (leftChild >= TrackingHeapIndex(items_.size()))
      {
        break;
      }
      const TrackingHeapIndex rightChild = leftChild + 1;
      TrackingHeapIndex selChild;
      if (rightChild >= TrackingHeapIndex(items_.size()) || comp_(items_[leftChild], items_[rightChild]))
      {
        selChild = leftChild;
      }
      else
      {
        selChild = rightChild;
      }
      if (!comp_(items_[selChild], items_[index]))
      {
        break;
      }
      std::swap(items_[index], items_[selChild]);
      std::swap(vTracker_[abs(items_[index].aVar_)], vTracker_[abs(items_[selChild].aVar_)]);
      index = selChild;
    }
  }

  template<bool bubble> void SetBalance(const TrackingHeapIndex aVar, const TrackingHeapPriority newBalance)
  {
    TrackingHeapIndex index = vTracker_[aVar];
    assert(0 <= index && index < TrackingHeapIndex(items_.size()));
    const InvVarInfo old = items_[index];
    if (old.balance_ == newBalance)
    {
      return;
    }
    items_[index].balance_ = newBalance;
    if constexpr (bubble)
    {
      OnBalanceUpdate(index, old);
    }
  }

  void ModifyBalance(const TrackingHeapIndex aVar, const TrackingHeapPriority change)
  {
    TrackingHeapIndex index = vTracker_[aVar];
    assert(0 <= index && index < TrackingHeapIndex(items_.size()));
    const InvVarInfo old = items_[index];
    items_[index].balance_ += change;
    OnBalanceUpdate(index, old);
  }

  void Toggle(const TrackingHeapIndex aVar)
  {
    TrackingHeapIndex index = vTracker_[aVar];
    assert(0 <= index && index < TrackingHeapIndex(items_.size()));
    const InvVarInfo old = items_[index];
    items_[index].aVar_ *= -1;
    OnBalanceUpdate(index, old);
  }
};

作为奖励，它在 MakeHeap() 操作中具有一定的并行性。

Answer 6

使用这些代码而不是使用STL优先级队列

arr：要插入到优先级队列中的元素数组

n：要插入到优先级队列中的元素数量

索引：元素索引（从1开始，而不是从0开始）

new_key ：新值（键值）

用于构建优先级队列。

void build_min_PQ(long int *arr, long int n)
{
   for(long int i = n/2; i>0; i--)
   {
       adjust_PQ(arr, n, i);
   }    
}

用于删除元素

void delete_element_pq(long int* arr, long int n, long int index)
{
    long int left_i = 2*index, right_i = 2*index+1;
    cout<<"index = "<<index<<" n = "<<n;nl
    arr[1] = arr[n];
    n--;
    adjust_PQ(arr, n, 1);
}

用于调整父项

void adjust_parent(long int* arr, long int n, long int index)
{
    long int parent;
    parent = index/2;
    if(parent > 0)
    {
        if(arr[index] < arr[parent])
        {
            long int temp;
            temp = arr[parent];
            arr[parent] = arr[index];
            arr[index] = temp;
            adjust_parent(arr, n, parent);
        }
    }
}

用于减少键 // 也可用于增加键

void decrease_key(long int* arr, long int n, long int new_key, long int index)        
 //  initially index = 1    //assuming array with sufficient size
{
    arr[index] = new_key;
    adjust_parent(arr, n, index);
}

用于插入优先级队列

void insert_pq(long int* arr, long int n, long int key)
{
    arr[n+1] = INT_MAX;
    decrease_key(arr, n+1, key, n+1);
}

用于提取顶部（最小）元素

long int ext_min(long int* arr, long int n)
{
    if(n>0)
    {
        long int temp = arr[1];
        delete_element_pq(arr, n, 1);
        return temp;
    }
    return -1;            // if PQ is empty;
}

以相同的顺序使用此模块

并且此代码也可以针对自定义数据类型进行修改
这里使用 long int 块的值作为键