二项式堆结构不允许您拥有指向节点（或迭代器）的指针

Question

我一直在玩二项式堆，我遇到了一个问题，我想在这里讨论一下，因为我认为它可能与某些用户实现二项式堆数据结构有关。

我的目标是拥有指向节点或句柄的指针，它直接指向二项式堆内部节点，当我将它们插入二项式堆时，这些节点又包含我的优先级值，通常是一个整数。通过这种方式，我将 pointer/handle 保留为我插入的内容，如果是这种情况，我可以使用 binomial_heap_delete_node(node) 直接删除该值，就像迭代器一样。

正如我们将看到的，使用二项式堆不可能，这是因为该数据结构的架构。

二项式堆的主要问题是，在某些时候您需要一个操作：binomial_heap_swap_parent_and_child(parent, child)，并且您在 binomial_heap_decrease_key(node, key) 和 binomial_heap_delete_node(node) 中都需要这个操作].这些操作的目的很明确，看名字就知道了。

所以，问题是 binomial_heap_swap_parent_and_child(parent, child) 是如何工作的：在我看到的 all 实现中，它交换了 priority 值在节点之间，NOT 节点本身。这将使所有 pointers/handles/iterators 节点失效，因为它们仍将指向正确的节点，但这些节点不会具有您之前插入的相同优先级值，而是另一个。

这是非常合乎逻辑的，如果我们观察二项式堆（或一般的二项式树）的结构：您有一个 parent 节点，许多 children 将其视为 "the parent"，这么多children指向它，但是那个parent节点不知道有多少children（或者更重要的是，哪个 children) 指向它，因此 不可能 像这样交换节点的位置。您唯一的选择是交换整数优先级密钥，但这将使所有 pointers/handles/iterators 节点无效。

注意：一种可能的解决方案是 NOT，而不是使用 binomial_heap_delete_node(node)，只需将要删除的节点的优先级设置为 -999999999（或这样的最小值）值）并弹出最小节点：这不会解决问题，因为 binomial_heap_decrease_key(node, key) 仍然需要节点 parent-child 交换操作，唯一的解决方案是交换整数优先级。

我想知道以前是否有人遇到过这个问题。我认为唯一的解决办法是使用另一种堆结构，例如二叉堆、配对堆或其他。

Answer 1

与许多数据结构问题一样，通过额外的间接级别解决这个问题并不难。定义如下：

struct handle {
  struct heap_node *node;  // points to node that "owns" this handle
  struct user_data *data;  // priority key calculated from this
}

您向用户提供句柄（通过复制或pointer/reference；您的选择）。

每个内部节点恰好指向一个句柄（即node->handle->node == node）。交换两个这样的指针以交换父子。

可能有多种变化。例如。 data 字段可以是数据本身而不是指向它的指针。主要思想是在句柄和节点之间添加间接级别提供了必要的灵活性。

二项式堆结构不允许您拥有指向节点（或迭代器）的指针

Binomial Heaps structure doesn't let you to have pointer to nodes (or iterators)

algorithm

heap

heapsort

data-structures