上位n個の要素をソート順に保つための最良のデータ構造は何ですか？

Question

this questionに似ていますが、ソート順を維持するという要件が追加されているので、先頭にはnの要素があります。明らかに私は最後を分別することができましたが、その場でそれを行うより効率的な方法があるかもしれません。挿入が行われるのは決して削除されず、最後にはnの要素が繰り返されます。

この質問は言語に依存しませんが、C＃で扱われるため、.NETのネイティブコレクションを使用した回答が望ましいです。

EDIT：ソート順序は、最上部のnの要素が反復されるときにのみ重要であることを明確にする必要があります。途中で挿入があると、先頭のn要素が保持されている限り、ソート順は関係ありません。

Answer 1

本当にそれらを並べ替える必要がある場合は、自己バランス型バイナリ検索ツリーを使用する必要があります。しかし、これを（要素をソートしておく）最適化ではなく、コストのかかる贅沢であることを考慮してください。

セルフバランスバイナリ検索ツリーは、定数要素による暗黙的ヒープよりも低速です。

どのようにソートされた要素にアクセスしますか？並べ替えられたシーケンスを繰り返し処理したい場合は、通常の自己バランス型バイナリ検索ツリーで十分です。

いつでもソートされたシーケンスの任意の要素（別の高級...）にアクセスするには、ツリーを拡張する必要があります。基本的に、すべてのノードには、そのサブツリー内のノードの数をカウントする追加のフィールドがあります。

Answer 2

繰り返しを繰り返す前に、最後の要素を単純に並べ替えるだけの価値があります。 kが十分に小さい（たとえば要素の総数の半分以下）場合、これは決して照会しないソートされたリストを維持するよりも安いでしょう。

STLの部分ソートのような、あらかじめ作成された部分ソート方法を調べます。

すべての要素の並べ替えられたリストの作成は、オンザフライであるかどうかに関わらず、比較ベースの並べ替えのためにO（n log n）で行われます。部分的な並べ替えはやや良いでしょう。

Answer 3

nの順番と挿入するアイテムの数を手がかりにしなければなりません。

ソート順が関係していると思いますが、どの要素がトップの一部であるかを知る方法はありますかn？ただすべての挿入の最後に、nのトップが欲しいと思っているだけで、構造やアルゴリズムのバイアスを作成しているかもしれません。

なぜトップにないアイテムを残してくださいn？サイズn + 1のソートされたセット（thinking of Python's deque）を使用できます。追加するときは、リストを反復して、新しい項目をセット内の正しい場所に挿入します。セットがサイズ（n + 1）になると、各挿入の後に最後のアイテムが削除されます。この方法では、決して取り出せないアイテムでデータ構造を拡張することなく、常にトップnアイテムを持つことができます。また

、あなたは（Nの最後、Bそれを呼び出す）底部要素の値を保持する場合は、あなたが完全に挿入をスキップすることを使用することができます。これにより、新規項目xがbより大きい場合、O（1）に対する比較の回数が制限されます。

Answer 4

この回答はKelly'sに似ていますが、テスト済みのコード例があります。 Nのサイズは小さい< 100なので、アイテムの数が（最適化されていない）値（たとえば20個）を上回っている場合、バイナリ検索ルックアップで修正された単純な挿入ソートを使用しました。私は、その使い方を示すサンプルコンソールアプリケーション（C＃）を含んでいます。私はそれが動作することを確認するためにそれを簡単にテストしましたが、私は現時点でそれを完全に分析しませんでした。この構造は、メモリ使用量を削減するために最適化されています。

public class TopNStructure<T> : IEnumerable<T> where T : IComparable<T> 
{ 
    private const int SizeForLinearOrBinaryInsert = 20; 

    private int _maxSize; 
    private int _currentSize; 
    private T[] _items; 
    private IComparer<T> _comparer; 

    /// <summary> 
    /// The number of items 
    /// </summary> 
    public int Count { get { return _currentSize; } } 

    public TopNStructure(int maxSize, IComparer<T> comparer) 
    { 
     if (maxSize <= 0) 
     { 
      throw new ArgumentOutOfRangeException("Max size must be a postive, non-zero value"); 
     } 
     _maxSize = maxSize; 
     _currentSize = 0; 
     _items = new T[maxSize]; 
     _comparer = comparer; 
    } 

    public TopNStructure(int maxSize) 
     : this(maxSize, Comparer<T>.Default) { } 

    /// <summary> 
    /// Adds an item to this structure 
    /// </summary> 
    /// <param name="item">The item to add</param> 
    /// <returns>True if the item was added, false otherwise</returns> 
    public bool Add(T item) 
    { 
     if (_currentSize == 0) 
     { 
      _items[0] = item;    
     } 
     else if (_currentSize == _maxSize) 
     { 
      if (_comparer.Compare(_items[_currentSize - 1], item) <= 0) 
      { 
       return false; 
      } 
      else 
      { 
       Insert(item); 
       return true; 
      } 
     } 
     else if (_currentSize == 1) 
     { 
      if (_comparer.Compare(_items[0], item) <= 0) 
      { 
       _items[1] = item; 
      } 
      else 
      { 
       _items[1] = _items[0]; 
       _items[0] = item; 
      }    
     } 
     else 
     { 
      if (_comparer.Compare(_items[_currentSize - 1], item) <= 0) 
      { 
       _items[_currentSize] = item; 
      } 
      else 
      { 
       Insert(item); 
      } 
     } 
     _currentSize++; 
     return true; 
    } 

    /// <summary> 
    /// Insert the item into the data structure 
    /// </summary> 
    /// <param name="item">The item to insert</param> 
    private void Insert(T item) 
    { 
     int start = 0; 
     if (_currentSize >= SizeForLinearOrBinaryInsert) 
     { 
      start = Array.BinarySearch<T>(_items, 0, _currentSize, item, _comparer); 
      if (start < 0) 
      { 
       start = ~start; 
      } 
      ShiftAndInsert(item, start, _currentSize);     
      return; 
     } 
     else 
     { 
      for (int i = start; i < _currentSize; i++) 
      { 
       if (_comparer.Compare(_items[i], item) > 0) 
       { 
        ShiftAndInsert(item, i, _currentSize);      
        return; 
       } 
      } 
      _items[_currentSize] = item; 
     }       
    } 

    /// <summary> 
    /// 
    /// </summary> 
    /// <param name="index"></param> 
    /// <param name="maxIndex"></param> 
    private void ShiftAndInsert(T item, int index, int maxIndex) 
    { 
     if (maxIndex >= _maxSize) 
     { 
      maxIndex = _maxSize - 1; 
     } 
     for (int i = maxIndex; i > index; i--) 
     { 
      _items[i] = _items[i - 1]; 
     } 
     _items[index] = item; 
    } 


    public IEnumerator<T> GetEnumerator() 
    { 
     return ((IEnumerable<T>)_items).GetEnumerator(); 
    } 

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
    { 
     return _items.GetEnumerator(); 
    } 
} 

static void Main(string[] args) 
{ 
    TopNStructure<double> data = new TopNStructure<double>(25); 

    Random rand = new Random(132151); 
    for (int i = 0; i < 50; i++) 
    { 
     double value = rand.NextDouble(); 
     data.Add(value); 
    } 

    int j = 0; 
    foreach (double value in data) 
    { 
     Console.WriteLine("{0} {1}", j, value); 
     j++; 
    } 
    Console.ReadKey(); 
} 

Answer 5

これは私の最初のものと似たデータ構造ですが、今回は内部のリンクリストを使用して挿入速度を改善しています。バイナリ検索を使用して挿入ポイントを見つけることはできないが、挿入と削除（アイテム> n）はO（1）なので、バイナリ検索の不足のバランスを取る必要があるため、速度が低下します。 Linkedリストには2つの追加ポインタがあるため、この構造体はより多くのメモリを使用します。

public class TopNStructureLinkedList<T> : IEnumerable<T> where T : IComparable<T> 
{ 
    private const int SizeForLinearOrBinaryInsert = 20; 

    private int _maxSize; 
    private int _currentSize; 
    private LinkedList<T> _items; 
    private IComparer<T> _comparer; 
    private LinkedListNode<T> _largestItemNode; 

    /// <summary> 
    /// The number of items 
    /// </summary> 
    public int Count { get { return _currentSize; } } 

    public TopNStructureLinkedList(int maxSize, IComparer<T> comparer) 
    { 
     _maxSize = maxSize; 
     _currentSize = 0; 
     _items = new LinkedList<T>(); 
     _comparer = comparer; 
     _largestItemNode = null; 
    } 

    public TopNStructureLinkedList(int maxSize) 
     : this(maxSize, Comparer<T>.Default) { } 

    /// <summary> 
    /// Adds an item to this structure 
    /// </summary> 
    /// <param name="item">The item to add</param> 
    /// <returns>True if the item was added, false otherwise</returns> 
    public bool Add(T item) 
    { 
     if (_currentSize == 0) 
     { 
      _largestItemNode = _items.AddFirst(item);    
     } 
     else if (_currentSize == 1) 
     { 
      if (_comparer.Compare(_largestItemNode.Value, item) <= 0) 
      { 
       _largestItemNode = _items.AddAfter(_largestItemNode, item);     
      } 
      else 
      { 
       _items.AddBefore(_largestItemNode, item);     
      } 
     } 
     else if (_currentSize == _maxSize) 
     { 
      if (_comparer.Compare(_largestItemNode.Value, item) <= 0) 
      { 
       return false; 
      } 
      else 
      { 
       Insert(item); 
       _largestItemNode = _items.Last.Previous; 
       _items.RemoveLast(); 
       return true; 
      } 
     } 
     else 
     { 
      if (_comparer.Compare(_largestItemNode.Value, item) <= 0) 
      { 
       _largestItemNode = _items.AddAfter(_largestItemNode, item);  
      } 
      else 
      { 
       Insert(item); 
      } 
     } 
     _currentSize++; 
     return true; 
    } 

    /// <summary> 
    /// Insert the item into the data structure 
    /// </summary> 
    /// <param name="item">The item to insert</param> 
    private void Insert(T item) 
    { 
     LinkedListNode<T> node = _largestItemNode.Previous; 
     while (node != null) 
     {    
      if(_comparer.Compare(node.Value, item) <= 0) { 
       _items.AddAfter(node, item); 
       return; 
      } 
      node = node.Previous;    
     } 
     _items.AddFirst(item); 

    } 

    public IEnumerator<T> GetEnumerator() 
    { 
     return ((IEnumerable<T>)_items).GetEnumerator(); 
    } 

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
    { 
     return _items.GetEnumerator(); 
    } 
} 

Answer 6

メモリに問題がない場合は、最後に配列全体を部分的に並べ替える方が良いです。 O（log n）挿入データ構造を使用しても、このような方法で実現できる最高の複雑さは、O（n log k）：n個の挿入がO（log k）になります。

Selection Algorithmを使用すると、配列のk個のトップ要素を見つけると、複雑さがO（k log n）になります。 kはnよりも小さいので、より良いです。

QuickSelectのウィキペディアの記事に実装があります。また、純粋なPriorityQueue（ここで言及されているほとんどの人とは異なる方法で）を使用する方が簡単です。概要：

create_heap(array) // O(n) 
for(int i=0; i<k; i++) 
    sorted[i] = heap_pop(array) //O(log n)