正直、追加の話見るまで最小と交換って私も「？」になった。
要するに1回目はソート済み配列が無いので >>282 をする。
要素を追加する度に、閾値以上かを見て、閾値以上ならソート済み配列で小さい順から二分探索して順番になる位置に挿入。
全要素1000で閾値以上が100とかなら、ソートするのが100だけだから、かなり高速化する。
追加もソート済みに入れるだけなので、遅くは無いし、次に取り出す事考えると(追加と同時にソート済みにしておく)、ソート済みから取り出すだけになるので全体として速くなる。
と言う考えであってる。。。と思う。
