对 Queap 数据结构的插入操作

Question

我正在尝试创建一个 Queap 维基百科上描述的数据结构 link 由于缺少 information.The 操作 Insert，我陷入了 Insert 操作的实施过程中，其中描述的似乎是从 element 中设置了一些数据，这些数据将被插入

 public static void Insert(Queap Q, Element x) {
            if (Q.n == 0)
                    Q.minL = x;
            Q.l.add(x);
            x.inList = true;
            if (x.compareTo(Q.minL) < 0)
                    Q.minL = x;
    }

该操作似乎具有复杂性 O(1)，正如此处所述：该操作的成本为 O(1)。列表 L 的大小增加 1，势能增加某个常数 c.。但是如果元素是 int 值，我该如何设置它？

Answer 1

根据 article:

To add element x to list l, the element x is added to the end of the list and a bit variable in element x is set to one. This operation is done to determine if the element is either in the list or in a 2-4 tree.

你问：

But if the element is an int value how can I set this?

queap 中的元素不直接对应于正在存储的数据类型的实例（在您的例子中，int）。

相反，一个元素对应于以下组合：

正在存储的数据类型的实例，并且
一个布尔标志，指示元素是在列表中还是在 2-4 树中。

这可以用 struct 表示：

template <typename T>
struct Element {
  T value;
  bool in_list;
};

或使用 pair:

template <typename T>
using Element = std::pair<T, bool>;

对 Queap 数据结构的插入操作

Insert operation on Queap Data Structure

c++

java

algorithm

tree

priority-queue