Priority Queue
প্রায়োরিটি কিউ
আগে-ঢোকা-আগে-পাওয়া নয়, priority অনুযায়ী বের হয় এমন abstract queue — heap দিয়ে insert আর extract-min দুটোই O(log n)।
also: pq
Abstract data type — implementation নয়। Interface:
| Operation | কাজ | Binary heap |
|---|---|---|
| insert | element ঢোকানো | O(log n) |
| extract-min | সবচেয়ে ছোটটা বের করা | O(log n) |
| peek | সবচেয়ে ছোটটা দেখা | O(1) |
কোথায় লাগে: Dijkstra ও A*-এ next node বাছাই, Huffman coding-এ সবচেয়ে rare symbol জোড়া, OS scheduler-এ process বাছাই।
Sorted array দিলে extract O(1) কিন্তু insert O(n); unsorted array ঠিক উল্টোটা। Heap দুই দিকেই log n compromise — এ কারণেই default implementation।