批量更新二進制堆中的節點優先級？

Question

我發佈了一個相當混亂的問題，所以我重寫了它從零開始...

這實際上是純理論問題。

說，我們有二進制堆。讓堆是一個MaxHeap，所以根節點的值最大，每個節點的值都比子節點的值大。我們可以在堆上做一些常見的低級操作：「交換兩個節點」，「比較兩個節點」。

使用這些低級操作，我們可以實現通常的高級遞歸操作：「篩選」，「篩選」。

使用這些篩選和篩選，我們可以實現「插入」，「修復」和「更新」。我對「更新」功能感興趣。假設我已經擁有要更改節點的位置。因此，更新功能很簡單：

function update (node_position, new_value){ 
    heap[node_position] = new_value; 
    sift_up(node_position); 
    sift_down(node_position); 
} 

我的問題是：是否有（mathematicaly）可能的話，進行更高級的「更新」功能，即可以同時更新多個節點，在某種程度上，所有節點將它們的值更改爲new_values，然後，他們的位置被糾正？事情是這樣的：

function double_update (node1_pos, node2_pos, node1_newVal, node2_newVal){ 
    heap[node1_pos] = node1_newVal; 
    heap[node2_pos] = node2_newVal; 
    sift_up(node1_position); 
    sift_down(node1_position); 
    sift_up(node2_position); 
    sift_down(node2_position); 
} 

我做了一些測試，這本「double_update」和它的工作，雖然它並不能證明什麼。

什麼「三重更新」，等等...

我做了一些其他測試與「多更新」，在那裏我改變了所有節點的值，然後叫{篩機（）;篩向下（）; }按照隨機順序對其中的每一個進行一次。這並不奏效，但結果並不是很正確。

我知道這聽起來不太有用，但我對它背後的理論很感興趣。如果我讓它工作，我確實有一個使用它。

Answer 1

確實可以做到這一點，但如果你打算在二進制堆中更改大量的鍵，你可能想看看其他堆結構，如斐波那契堆或配對堆可以做到這一點比二進制堆快得多。用n個節點更改二進制堆中的k個鍵需要O（k log n）時間，而在Fibonacci堆中，需要時間O（k）。這是漸近最優化的，因爲如果不進行至少Ω（k）的工作，你甚至不能觸及k個節點。

要考慮的另一件事是，如果您一次更改多於Ω（n/log n）個鍵，那麼您至少要做Ω（n）的工作。在這種情況下，通過使用標準heapify算法在Θ（n）時間內從頭重新構建堆來實現更新可能會更快。

希望這會有所幫助！

Answer 2

這裏有一個竅門，可能時髦的算法，對於時髦的一些定義：

（很多東西離開了，只給想法）：

template<typename T> class pseudoHeap { 
    private: 
    using iterator = typename vector<T>::iterator; 
    iterator max_node; 
    vector<T> heap; 
    bool heapified; 

    void find_max() { 
     max_node = std::max_element(heap.begin(), heap.end()); 
    } 

    public: 
    void update(iterator node, T new_val) { 
     if (node == max_node) { 
      if (new_val < *max_node) { 
       heapified = false; 
       *max_node = new_val; 
       find_max(); 
      } else { 
       *max_node = new_val; 
      } 
     } else { 
      if (new_val > *max_node) max_node = new_val; 
      *node = new_val; 
      heapified = false; 
    } 

    T& front() { return &*max_node; } 

    void pop_front() { 
     if (!heapified) { 
      std::iter_swap(vector.end() - 1, max_node); 
      std::make_heap(vector.begin(), vector.end() - 1); 
      heapified = true; 
     } else { 
      std::pop_heap(vector.begin(), vector.end()); 
     } 
    }   
}; 

保持堆是昂貴的。如果在開始彈出堆之前更新了n，那麼在您需要對堆進行排序時（O(n log n)），您只需對矢量進行排序就可以完成相同的工作量。如果知道最大值始終是有用的，那麼有理由保持堆，但如果最大值不可能被修改爲比其他任何值更大，則可以始終保持最大值（1）（即，1/n乘以O(n)，其餘時間爲O(1)。這就是上面的代碼所做的，但是對於計算max也可能更好，因爲front()按照您的要求

作爲另一種選擇，如果修改通常不會導致值移動很遠，只需執行一個簡單的「找到新家並旋轉子向量」循環，雖然它是O(n) instea d爲O(log n)，由於常數較小，因此短期走勢仍然較快。

換句話說，不要使用優先堆，除非您經常需要找到最高k值。讀取之間有很多修改時，通常會有更好的方法。