c++ - 创建 "relative"优先级队列的算法？ (c/c++)

Question

我想用链表做一个队列。那里有许多算法。但我很好奇的是如何制作相对优先级队列。

也许这种类型的队列有一个特殊的名称，但我不知道，而且我还没有通过谷歌搜索解决方案。

无论如何，假设我有这个结构，它将代表我的列表的节点。

struct Node {
    int value;
    Node* next;
}

如果我想创建一个优先级队列(其中值最小的元素排在第一位)，当我插入例如 5 7 1 8 2 时，我的列表应该如下所示:

1 -> 2 -> 5 -> 7 -> 8

实现起来并不难。我想要做的是 - 当我插入第一个元素时，其他元素应该具有相对于前一个元素的值。因此，在我的示例中，列表/队列将包含以下值:

1 -> 1 -> 3 -> 2 -> 1

我不太确定我将如何实现它？以下想法是否适用:

在 Node 结构中，我添加了另一个字段，它将代表原始值。我找到我要插入的节点的位置，就像创建普通链表时一样，然后我就说

temp->value = temp->originalValue - previous->originalValue;

Answer 1

您需要在每个节点中存储额外的数据，或者是相对优先级，或者是“前一个”指针。由于每当删除节点时都需要更新下一个节点的相对优先级(没有 prev 指针如何做到这一点？)，我建议使用“previous”指针:

struct Node {
    int value;
    Node* next;
    Node* prev;
}

然后一个函数可以评估相对优先级:

int relative_priority(Node* node) {
    if (node == NULL)
        return 0;
    if (node->prev == NULL)
        return node->value;
    return node->value - node->prev->value;
}

请注意，我使用的是 C，对于 C++，您需要将 NULL 替换为 0