a1、a2、...、anなどの一連の要素があります。（n〜4 * 10 ^ 7）
入力はほとんどソートされます。より具体的には、a_i未満の要素は、左側または右側に非常に近くなります（〜300要素）。
このシーケンスを効率的にソートするにはどうすればよいですか？
質問する
53 次
これは、Nが最大オーバーラップ（この場合はN = 300）であるN個の要素のヒープを使用して行うことができます。
空のヒープから始めます。
シーケンス内の各要素について：
ヒープに要素を追加します
ヒープにN個を超える要素がある場合は、最小の要素を出力（およびヒープから削除）します。
最後に、ヒープ内の残りの要素を出力します。
これは複雑になりますO（nlogN）