11

次の問題があるとします。

「一連の数字から最大の 5000 個の数字を保存する」

頭に浮かぶ解決策は、ツリー内のノード数のカウントと、カウントが 5000 に達すると最小のノードへの参照を維持するバイナリ サーチ ツリーです。カウントが 5000 に達すると、追加するそれぞれの新しい数をツリーの最小のアイテム。大きい場合は、新しい数を追加してから、最小のものを削除し、新しい最小値を計算できます (これは、以前の最小値を既に持っている非常に単純なはずです)。

このソリューションに関する私の懸念は、バイナリ ツリーが自然に歪んでしまうことです (片側だけを削除しているため)。

ひどく歪んだツリーを作成しないこの問題を解決する方法はありますか?

誰かがそれを望む場合に備えて、これまでのソリューションの疑似コードを以下に含めました。

process(number)
{
  if (count == 5000 && number > smallest.Value)
  {
    addNode( root, number)
    smallest = deleteNodeAndGetNewSmallest ( root, smallest)
  }
}

deleteNodeAndGetNewSmallest( lastSmallest)
{
  if ( lastSmallest has parent)
  {
    if ( lastSmallest has right child)
    {
      smallest = getMin(lastSmallest.right)
      lastSmallest.parent.right = lastSmallest.right
    }
    else
    {
      smallest = lastSmallest.parent
    }
  }
  else 
  {
    smallest = getMin(lastSmallest.right)
    root = lastSmallest.right
  }
  count--
  return smallest
}

getMin( node)
{
  if (node has left)
    return getMin(node.left)
  else
    return node
}

add(number)
{
  //standard implementation of add for BST
  count++
}
4

2 に答える 2

38

これに対する最も簡単な解決策は、最大サイズ 5000の最小ヒープを維持することです。

  • 新しい数値が到着するたびに - ヒープが 5000 より小さいかどうかを確認し、そうであれば追加します。
  • そうでない場合は、最小値が新しい要素よりも小さいかどうかを確認し、小さい場合はポップアウトして代わりに新しい要素を挿入します。
  • 完了すると、5000 個の最大要素を含むヒープが作成されます。

このソリューションはO(nlogk)複雑です。nは要素の数で、kは必要な要素の数です (この場合は 5000)。

これは、選択アルゴリズムO(n)を使用して行うこともできます。すべての要素を保存してから、5001 番目に大きい要素を見つけ、それよりも大きいものをすべて返します。ただし、実装が難しく、妥当なサイズの入力の場合は、それほど良くないかもしれません。また、ストリームに重複が含まれている場合は、さらに処理が必要です。

于 2012-05-25T09:36:49.443 に答える
1

(最小) プライオリティ キューを使用します。各着信アイテムをキューに追加し、サイズが 5,000 に達したら、着信要素を追加するたびに最小 (最上位) 要素を削除します。キューには 5,000 の最大要素が含まれ、入力が停止すると、内容が削除されます。この MinPQ はヒープとも呼ばれますが、これはオーバーロードされた用語です。挿入と削除には約 log2(N) かかります。N が 5,000 で最大になる場合、これは処理しているアイテムの数の 12 [log2(4096) = 12] 倍強になります。

優れた情報源は、Robert Sedgewick と Kevin Wayne による Algorithms (第 4 版) です。このテキストに基づいた優れた MOOC が coursera.org にあります。

于 2013-11-01T16:31:03.133 に答える