二項式堆結構不會讓您指向節點（或迭代器）

Question

我一直在玩Binomial堆，而且我遇到了一個問題，我想在此討論，因爲我認爲它可能會涉及某些用戶實現Binomial Heap數據結構。

我的目標是讓指向節點或句柄的指針，它們直接指向Binomial Heap內部節點，當我將它們插入到二項式堆中時，該節點又包含我的優先級值（通常爲整數）。 以這種方式，我將指針/句柄保持爲我所插入的內容，如果是這種情況，我可以使用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)作品：在所有我看到了實現中，交換節點之間的優先值，不節點本身。 這將使節點的所有指針/句柄/迭代器無效，因爲它們仍然指向正確的節點，但這些節點不會具有您之前插入的同一優先級值，而是另一個節點。

如果我們看到Binomial堆（或一般的二叉樹）是如何構造的：這是非常合乎邏輯的：您有一個父節點，被許多孩子視爲「父母」，所以很多孩子指出它，但是那個父節點並不知道有多少個孩子（或者更重要的是哪個孩子）指向它，所以它會是不可能的這樣交換一個節點的位置。你唯一的選擇是交換整數優先級鍵，但是這將使節點的所有指針/句柄/迭代器無效。

注：可能的解決辦法NOT成爲其中代替使用binomial_heap_delete_node(node)，一個可以只設置該節點的優先級，以除去到-999999999（或最小值）和彈出的最小節點出來：這不會解決問題，因爲binomial_heap_decrease_key(node, key)仍然需要節點的父子交換操作，而唯一的解決辦法就是交換整數優先級。

我想知道是否有人在此問題之前發生過。 我認爲唯一的解決方案是使用另一個堆結構，比如Binary Heap，Pairing Heap或其他。

Answer 1

與許多數據結構問題一樣，用額外的間接級別來解決這個問題並不困難。定義類似於：

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字段可能是數據本身，而不是指向它的指針。主要思想是在句柄和節點之間添加間接級別提供了必要的靈活性。