我一直在玩二项式堆,我遇到了一个我想在这里讨论的问题,因为我认为它可能涉及到一些用户实现二项式堆栈数据结构。
我的目标是让指向节点或句柄的指针直接指向二项式堆内部节点,当我将它们插入二项式堆栈时,这些节点又包含我的优先级值,通常是整数。通过这种方式,我将指针/句柄保留为我插入的内容,如果是这种情况,我可以使用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)
是如何工作的:在我看到的所有实现中,它在节点之间交换优先级值,而NOT节点本身。这将使指向节点的所有指针/句柄/迭代器失效,因为它们仍然指向正确的节点,但这些节点的优先级值与您之前插入的优先级值不同,而是另一个。
如果我们观察二项式堆(或二项式树)的结构,这是非常合乎逻辑的:你有一个父节点,被许多子节点视为"父节点",所以有很多子节点指向它,但该父节点不知道有多少子节点(或者更重要的是,哪些子节点)指向它,所以像这样交换节点的位置是不可能的。您唯一的选择是交换整数优先级键,但这将使指向节点的所有指针/句柄/迭代器无效。
注意:一个可能的解决方案是,不使用binomial_heap_delete_node(node)
,而只需将要删除的节点的优先级设置为-99999999999(或这样的最小值),并弹出最小节点:这不会解决问题,因为binomial_heap_decrease_key(node, key)
仍然需要节点父子交换操作,唯一的解决方案就是交换整数优先级。
我想知道以前是否有人遇到过这个问题。我认为唯一的解决方案是使用另一个堆结构,如二进制堆、配对堆或其他结构。
与许多数据结构问题一样,通过额外的间接级别来解决这个问题并不困难。定义如下:
struct handle {
struct heap_node *node; // points to node that "owns" this handle
struct user_data *data; // priority key calculated from this
}
您为用户提供句柄(通过复制或指针/引用;由您选择)。
每个内部节点恰好指向一个句柄(即node->handle->node == node
)。交换两个这样的指针来交换父指针和子指针。
有几种变化是可能的。例如,data
字段可以是数据本身,而不是指向它的指针。其主要思想是在句柄和节点之间添加间接级别可以提供必要的灵活性。