この質問と同様に、上位n要素を保持するデータ構造を探していますが、並べ替え順序を維持するという要件が追加されています。明らかに、最後にソートすることもできますが、その場でソートするより効率的な方法があるかもしれません。挿入のみが行われ、削除は行われず、最後に上位n要素の反復が行われます。
この質問は言語に依存しませんが、C# になるため、ネイティブの .NET コレクションを使用する回答が望ましいです。
編集: 並べ替え順序は、上位n 個の要素が繰り返される最後の最後にのみ重要であることを明確にする必要があります。途中で挿入が行われるため、上位n 個の要素が保持される限り、並べ替え順序は関係ありません。
nの順序と挿入するアイテムの数について の手がかりを提供する必要があります。
ソート順は関係があると思いますが、どの要素が上位nの一部であるかを他にどのように知ることができますか? すべての挿入の最後に上位nのみが必要であるという理由だけで、構造またはアルゴリズムに対する賛成/反対のバイアスが作成されている可能性があります。
上位nに含まれていないアイテムを保持するのはなぜですか? サイズ n+1のソートされたセット ( Python の deque を考えて) を使用できます。追加するときは、リストを反復処理し、新しいアイテムをセット内の正しい場所に挿入します。セットがサイズ (n+1) になると、各挿入の後に最後の項目の削除が続きます。このようにして、取得されることのないアイテムでデータ構造を大きくすることなく、常に上位n 個のアイテムを取得できます。
さらに、一番下の要素 ( nの最後、それをbと呼びます) の値を保持する場合、それを使用して挿入を完全にスキップできます。これにより、新しいアイテムxがbより大きい場合、比較の回数が O(1) に制限されます。
本当にそれらを常にソートしておく必要がある場合は、自己平衡二分探索木を使用する必要があります。ただし、これ（要素を並べ替えたままにする）は最適化ではなく、コストのかかる贅沢であることを考慮に入れてください。
自己平衡二分探索木は、暗黙のヒープよりも一定の係数で遅くなります。
ソートされた要素にどのようにアクセスしますか？ソートされたシーケンスを反復処理するだけの場合は、通常の自己平衡二分探索木で十分です。
いつでもソートされたシーケンスの位置によって任意の要素にアクセスしたい場合（別の贅沢...）、ツリーを拡張する必要があります。基本的に、すべてのノードには、それ自体を含むサブツリー内のノードの数をカウントする追加のフィールドがあります。
この回答はケリーのものに似ていますが、テスト済みのコード例があります。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();
}
反復処理を行う前に、上位 k 個の要素を最後に並べ替えるだけの価値があるかもしれません。k が十分に小さい場合 (たとえば、要素の総数の半分未満)、これは、クエリを実行しないソート済みリストを維持するよりも安価になります。
STL の部分的な並べ替えのような、事前に構築された部分的な並べ替え方法を調べてください。
すべての要素のソート済みリストの作成は、その場であるかどうかに関係なく、比較ベースのソートのために O(n log n) で行われます。部分的なソートは少し良くなります。
これは最初のものと同様のデータ構造ですが、今回は内部のリンク リストを使用して挿入速度を向上させています。バイナリ検索を使用して挿入ポイントを見つけることができないため、速度が多少低下しますが、(項目 > n の) 挿入と削除は O(1) であり、バイナリ検索の欠如のバランスを取る必要があります。リンク リストには 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();
}
}