分层优先级索引

Hierarchical priority index

我正在寻找一个 C++ 库,它具有以下问题的索引解决方案。我曾尝试过自己的解决方案,但得出的结论是我在这里发明了一个轮子。

我有一个可以接水的源桶。它需要在层次结构之间拆分水。我想它也可以表示为具有优先级的队列。在具有更高优先级的桶装满之前,其他桶不会接收任何水。有的水桶有children个水桶,应该从那里过水。所有 children 都可以拥有自己的 children,因此他们也是某些人的母亲。 妈妈水桶可以严格排队(一个接一个)传水,也可以按比例分水。

在下面的图片中,我试图说明情况。我们有 Bucket 作为层次结构的顶部。它有3children。他们根据优先级(1、2、3)严格按顺序接水。在桶 1 装满之前,桶 2 不会接收任何水。桶 1 也有 3 children。两个孩子具有相同的优先级和 50% 和 50% 的比例,第三个 child 只有在其他两个孩子吃饱后才会喝水。第一个孩子有了孩子,他们把水分成 20% 和 80%。

任意级别的整数 1 具有最高优先级。如果桶在同一层次上有相似的整数,我们可以认为它们的优先级相等,然后看分裂的比例。第一层编号为 1 的桶将首先接收水。然后它必须将水传递到第二级,在那里水将被分配 50%-50%,然后 50% 将在最后一级之间按 50%(20% 和 80%)分配。

                                             +--------------+
                                             |              |
                                             |   Bucket     |
                                             +-+-----+----+-+
                                               |     |    |
                                               |     |    |
                                      1        |     |    |       3
                              +----------------+     |    +-----------------+
                              |                      |                      |
                              |                      |2                     |
                              ^                      |                      ^
                           +------+                  |                   +--+--+
                           |  |   |                  ^                   |     |
                  1        |  |   |   2           +--+--+                +-----+
                  0.5      |  |   |               |     |
                +----------+  |1  +-------+       +-----+
                |             |0.5        |
                ^             ^           ^
             +--+--+      +---+---+     +-+---+
             |     |      |       |     |     |
             ++-+--+      +-------+     +-----+
              | |
     1 0.2    | |
   +----------+ |1 0.8
   |            |
   |            |
   v            v
+--+--+      +--+--+
|     |      |     |
+-----+      +-----+

我需要索引所有孩子和他们的比例,这样,当我收到水时,我会根据所有优先级和共享权重拆分水。我的想法是使用 double 变量的整数部分的位来表示层次结构每个级别的优先级,并使用小数部分来存储比例。

您可以通过与访问者一起遍历 depth-first 您的树,将您的问题从树表示转换为队列:

#include <map>
#include <list>

struct Bucket
{
    std::map<unsigned int, Bucket> children; // <priority, children>

    template<class Visitor>
    void visit(const Visitor& visitor)
    {
        for (auto it = children.rbegin(); it!= children.rend(); ++it)
        {
            visitor(&it->second);
            it->second.visit(visitor);
        }
    }
};

int main()
{
    Bucket root_bucket;
    // populate root_bucket
    // ...

    // index root_bucket
    std::list<Bucket*> indexed_buckets;
    root_bucket.visit( [&](Bucket* b){ indexed_buckets.push_back(b); });
}

Demo

之后,indexed_buckets 将包含指向填充顺序中的桶的指针。只需将第一个装满,然后将剩余的水装满下一个。