挿入操作が膨大な場合、優先度キューのどの実装が有効になりますか？

-2

アプリケーションに膨大な数の挿入操作が含まれているとしますが、の操作で最大操作が削除されたとします。どちらの優先度キューインプリメンテーションをとすれば、ヒープ、順序付けされていない配列、または順序付けされた配列が最も効果的だろうと思いますか？挿入操作が膨大な場合、優先度キューのどの実装が有効になりますか？

例を挙げて説明できますか？

出典

2017-04-14 Pooja

はhttps://cs.stackexchange.com/questions/2824/most-efficient-known-priority-queue-for-insertsまたはhttps://cs.stackexchange.com/questions/524/doesい-there-exist-a-priority-queue-o1-extractはあなたの質問に答えますか？ –

@DylanVanderBerg Heap、Unordered arrayまたはOrdered配列を使用するPQ実装から、巨大な挿入操作とアプリケーションでの削除操作が少ない場合に効果的です。 – Pooja

これを読んでみてください[article（priority queue）]（http://algs4.cs.princeton.edu/24pq/） –

類似した質問http://gateoverflow.in/65570/gatebook-examを見ましたか？
優先度キューには4つの実装があります。

|Structure   | Insertion | Extract-max| 
|----------   |---------- |------------| 
|Unordered list  | O(1) | O(n)  | 
|Ordered list  | O(n) | O(1)  | 
|Binary Search Tree | O(logn) | O(logn) | 
|Heap    | O(logn) | O(logn) | 
----------------------------------------------

出典

2017-04-14 05:57:25 Rizwan

挿入操作が膨大な場合、優先度キューのどの実装が有効になりますか？

答えて

関連する問題