1

かなり紛らわしい質問を投稿したので、最初から書き直しました...

これは実際には純粋に理論的な問題です。

たとえば、バイナリ ヒープがあるとします。ヒープを MaxHeap にすると、ルート ノードが最大の値を持ち、すべてのノードがその子よりも大きな値を持ちます。このヒープでは、「2 つのノードを交換する」、「2 つのノードを比較する」などの一般的な低レベルの操作を実行できます。

これらの低レベルの操作を使用して、通常の高レベルの再帰操作「シフトアップ」、「シフトダウン」を実装できます。

これらのふるい分けとふるい分けを使用して、「挿入」、「修復」、「更新」を実装できます。「更新」機能に興味があります。変更するノードの位置が既にあると仮定しましょう。したがって、更新機能は非常に単純です。

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

私の質問は: すべてのノードが値を 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」でこれをいくつかテストしたところ、何も証明されていませんが、機能しました。

「トリプルアップデート」などはどうですか...

「マルチ更新」を使用して他のテストをいくつか行いました。そこでは、すべてのノードの値を変更してから { sift-up(); を呼び出しました。ふるいにかける(); ランダムな順序でそれぞれに 1 回。これはうまくいきませんでしたが、結果は正しくありませんでした。

これは役に立たないように聞こえますが、その背後にある理論に興味があります。そして、私がそれを機能させれば、実際には1つの用途があります.

4

2 に答える 2

1

これを行うことは間違いなく可能ですが、バイナリ ヒープ内の多数のキーを変更することを計画している場合は、フィボナッチ ヒープやペアリング ヒープなどの他のヒープ構造を検討することをお勧めします。バイナリヒープ。n ノードのバイナリ ヒープで k キーを変更するには O(k log n) の時間がかかりますが、フィボナッチ ヒープでは O(k) の時間がかかります。少なくとも Ω(k) の作業を行わないと k ノードに触れることさえできないため、これは漸近的に最適です。

考慮すべきもう 1 つのことは、一度に Ω(n / log n) を超えるキーを変更すると、少なくとも Ω(n) の作業を行うことになるということです。その場合、標準の heapify アルゴリズムを使用して Θ(n) 時間でゼロからヒープを再構築するだけで、更新を実装する方がおそらく高速です。

お役に立てれば！

于 2012-12-09T17:15:35.790 に答える
1

ファンキーのいくつかの定義のためのトリックであり、おそらくファンキーなアルゴリズムは次のとおりです。

（アイデアを与えるために、多くのものが省略されています）：

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))。常に最大値を知っておくと便利な場合は、ヒープを保持する理由がありますが、最大値が他の値よりも変更される可能性が低い場合は、最大値を常に手元に置いておくことができます償却コストO(1) (つまり、1/nコストがかかりO(n)、残りの時間はO(1). . 要件によって異なります。front()O(1)O(1)

さらに別の方法として、通常、変更によって値が大きく移動しない場合は、単純な「新しいホームを見つけてサブベクトルを回転させる」ループを実行しO(n)ますO(log n)。定数が小さくなります。

つまり、常に上位 k 個の値を見つける必要がある場合を除き、優先ヒープを使用しないでください。読み取りの間に多くの変更がある場合、通常はより良いアプローチがあります。

于 2012-12-10T05:26:17.767 に答える