c++ - 最大で 3N の比較を行いながら std::make_heap を実装するにはどうすればよいですか?

Question

C++0x 標準を調べたところ、make_heap は 3*N 回を超えない比較を行う必要があることがわかりました。

つまり、順序付けられていないコレクションを O(N) でヒープ化できます。

   /*  @brief  Construct a heap over a range using comparison functor.

どうしてこれなの？

ソースから手がかりが得られない (g++ 4.4.3)

while (true) + __parent == 0 は手がかりではなく、O(N) 動作の推測です

template<typename _RandomAccessIterator, typename _Compare>
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
          _Compare __comp)
{

  const _DistanceType __len = __last - __first;
  _DistanceType __parent = (__len - 2) / 2;
  while (true)
    {
      _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
      std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
                 __comp);
      if (__parent == 0)
        return;
      __parent--;
    }
}

__adjust_heap は、log N メソッドのように見えます。

while ( __secondChild < (__len - 1) / 2)
{
    __secondChild = 2 * (__secondChild + 1);

私にとってはボグスタンダードのログNです。

  template<typename _RandomAccessIterator, typename _Distance,
       typename _Tp, typename _Compare>
    void
    __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
          _Distance __len, _Tp __value, _Compare __comp)
    {
      const _Distance __topIndex = __holeIndex;
      _Distance __secondChild = __holeIndex;
      while (__secondChild < (__len - 1) / 2)
      {
        __secondChild = 2 * (__secondChild + 1);
          if (__comp(*(__first + __secondChild),
             *(__first + (__secondChild - 1))))
          __secondChild--;
          *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
          __holeIndex = __secondChild;
      }
      if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
      {
        __secondChild = 2 * (__secondChild + 1);
        *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
                             + (__secondChild - 1)));
        __holeIndex = __secondChild - 1;
      }
      std::__push_heap(__first, __holeIndex, __topIndex, 
               _GLIBCXX_MOVE(__value), __comp);      
      }

これが O <= 3N である理由の手がかりをいただければ幸いです。
編集：

実験結果：

この実際の実装では

ヒープ化ヒープの <2N 比較
ヒープを逆の順序でヒープ化する場合は <1.5N。

score 53 · Accepted Answer

n 個の要素にわたるバイナリヒープは、巧妙なアルゴリズムと巧妙な分析を使用して O(n) 時間で作成できます。以下では、明示的なノードと明示的な左右の子ポインターがあると仮定して、これがどのように機能するかについて説明しますが、配列に圧縮した後でも、この分析は完全に有効です。

アルゴリズムは次のように機能します。ノードの約半分を取得し、それらをシングルトンの最大ヒープとして扱うことから始めます。要素が 1 つしかないため、その要素だけを含むツリーは自動的に最大ヒープになる必要があります。さて、これらの木を取り出して、互いにペアにします。ツリーのペアごとに、まだ使用していない値の 1 つを取得し、次のアルゴリズムを実行します。

新しいノードをヒープのルートにし、左右の子ポインターが 2 つの最大ヒープを参照するようにします。
このノードにはそれよりも大きい子がありますが、その子をより大きな子と交換します。

私の主張は、この手順は 2 つの入力 max-heap の要素を含む新しい max heap を生成することになり、時間 O(h) で生成されるというものです。ここで、h は 2 つのヒープの高さです。証明は、ヒープの高さの帰納法です。基本的なケースとして、サブヒープのサイズがゼロの場合、アルゴリズムは単一の最大ヒープですぐに終了し、O(1) 時間で終了します。帰納的なステップでは、いくつかの h について、この手順がサイズ h の任意のサブヒープで機能すると仮定し、サイズ h + 1 の 2 つのヒープで実行するとどうなるかを考えます。新しいルートを追加して、サイズの 2 つのサブツリーを結合する場合h + 1 の場合、次の 3 つの可能性があります。

新しいルートは、両方のサブツリーのルートよりも大きくなります。次に、この場合、ルートがいずれかのサブツリーのどのノードよりも大きいため (推移性により)、新しい最大ヒープがあります。
新しいルートは、1 つの子よりも大きく、他の子よりも小さいです。次に、ルートをより大きなサブチャイルドと交換し、古いルートと子の 2 つのサブツリー (それぞれの高さが h) を使用して、この手順を再帰的に実行します。帰納的仮説により、これは、スワップ先のサブツリーが現在最大ヒープであることを意味します。したがって、新しいルートはスワップしたサブツリー内のすべてのものよりも大きく (追加したノードよりも大きく、そのサブツリー内のすべてのものよりもすでに大きいため)、ヒープ全体は最大ヒープです。他のサブツリーで (ルートよりも大きく、ルートが他のサブツリーのすべてよりも大きかったため)。
新しいルートは、その両方の子よりも小さいです。次に、上記の分析を少し変更したバージョンを使用して、結果のツリーが実際にヒープであることを示すことができます。

さらに、各ステップで子ヒープの高さが 1 ずつ減少するため、このアルゴリズムの全体的な実行時間は O(h) でなければなりません。

この時点で、ヒープを作成するための単純なアルゴリズムができました。

ノードの約半分を取り、シングルトンヒープを作成します。(ここで必要なノードの数を明示的に計算できますが、約半分です)。
これらのヒープをペアにしてから、未使用のノードの 1 つと上記の手順を使用してそれらをマージします。
ヒープが 1 つになるまで手順 2 を繰り返します。

各ステップで、これまでのヒープが有効な最大ヒープであることがわかっているため、最終的には有効な全体の最大ヒープが生成されます。作成するシングルトンヒープの数を賢く選択すれば、最終的には完全なバイナリツリーも作成されます。

ただし、これは O(n lg n) 時間で実行する必要があるようです。これは、O(n) 回のマージを実行し、それぞれが O(h) で実行され、最悪の場合、マージしている木の高さが異なるためです。は O(lg n) です。しかし、この境界は厳密ではなく、分析をより正確にすることで、より良い結果を得ることができます。

特に、マージするすべての木の深さについて考えてみましょう。ヒープの約半分は深さ 0 で、残りの半分は深さ 1、残りの半分は深さ 2 というようになります。これを合計すると、合計が得られます。

0 * n/2 + 1 * n/4 + 2 * n/8 + ... + nk/(2 ^k ) = Σ _{k = 0}^{⌈log n⌉} (nk / 2 ^k ) = n Σ _{k = 0}^{⌈ log n⌉} (k / 2 ^k+1 )

これにより、行われるスワップ数の上限が決まります。各スワップには、最大で 2 つの比較が必要です。したがって、上記の合計に 2 を掛けると、次の合計が得られます。これにより、行われたスワップ数の上限が決まります。

n Σ _{k = 0}^∞ (k / 2 ^k )

ここでの合計は、合計 0 / 2 ⁰ + 1 / 2 ¹ + 2 / 2 ² + 3 / 2 ³ + ... です。これは、複数の異なる方法で評価できる有名な総和です。これを評価する方法の 1 つが、これらの講義スライドのスライド 45 ～ 47 に示されています。最終的には正確に 2n になります。つまり、最終的に行われる比較の数は、上から 3n で確実に制限されます。

お役に立てれば！

score 17 · Accepted Answer

@templatetypedef は、漸近的な実行時間がO(n)である理由について、すでに適切な回答を提供しています。CLRS第 2 版の第 6 章にも証明があります。build_heap

C++ 標準で最大3n 回の比較を使用する必要がある理由については、次のとおりです。

私の実験 (以下のコードを参照) から、実際には2n未満の比較が必要なようです。実際、これらの講義ノートには、 2(n-⌈log n⌉) 回の比較build_heapのみを使用する証明が含まれています。

標準からの境界は、必要以上に寛大なようです。

def parent(i):
    return i/2

def left(i):
    return 2*i

def right(i):
    return 2*i+1

def heapify_cost(n, i):
    most = 0
    if left(i) <= n:
        most = 1 + heapify_cost(n, left(i))
    if right(i) <= n:
        most = 1 + max(most, heapify_cost(n, right(i)))
    return most

def build_heap_cost(n):
    return sum(heapify_cost(n, i) for i in xrange(n/2, 1, -1))

いくつかの結果:

n                     10  20  50  100  1000  10000
build_heap_cost(n)     9  26  83  180  1967  19960

c++ - 最大で 3N の比較を行いながら std::make_heap を実装するにはどうすればよいですか?

2 に答える 2

Related

Reference