リスト/配列の最小要素を効率的に削除する必要があるこの問題に遭遇しました。それを解決するのはかなり簡単です - ヒープで十分です。
ただし、現在の問題は、最小の要素を削除すると、データ構造内の他の要素が変更され、順序が変更される可能性があることです。例はこれです：
私は要素の配列を持っています:
[1,3,5,7,9,11,12,15,20,33]
配列から「1」を削除すると、「5」と「12」がそれぞれ「4」と「17」に変更されます。
[3,4,7,9,11,17,15,20,33]
したがって、順序は維持されません。
ただし、削除される要素には、変更されるすべての要素へのポインターがありますが、変更される要素の数と量はわかりません。
だから私の質問は：
並べ替えを維持しながらデータ構造から最小の要素を削除するときに、これらの要素を格納してパフォーマンスを最大化する最良の方法は何ですか? それとも、ソートせずにそのままにしておくべきですか？
私の現在の実装では、それらをソートせずにベクトルに格納するだけなので、時間の複雑さは O(N^2)、最小要素を見つけるための O(N)、および N 個の削除です。