search

kzhereb / kpi-acts-ta2020

Materials for "Algorithm theory" course
MIT License
0 stars 0 forks source link

D05.10. Other ways of implementing priority queue #36

Open artem-vovchenko01 opened 4 years ago

artem-vovchenko01 commented 4 years ago

D05.10. Other ways of implementing priority queue? D05.10. Інші способи реалізації priority queue?

artem-vovchenko01 commented 4 years ago

Discussion from previous years:

Обговорення з попередніх років:

RedBarboriska commented 4 years ago

Priority queue може бути реалізований за допомогою масиву, зв'язного списку, структури даних купи або двійкового дерева пошуку. Серед цих структур даних купа забезпечує ефективну реалізацію пріоритетних черг.

Для додатків, які виконують багато операцій «peek» для кожної операції «extract-min», тимчасова складність операцій peek може бути зменшена до O (1) у всіх реалізаціях дерева і купи шляхом кешування елемента з найвищим пріоритетом після кожної вставки і видалення.

Порівняльний аналіз різних реалізацій priority queue наведено нижче. type peek insert delete
Linked List O(1) O(n) O(1)
Binary Heap O(1) O(log n) O(log n)
Binary Search Tree O(1) O(log n) O(log n)
AndriyBosik commented 4 years ago

Priority Queue можна реалізувати за допомогою купи Фібоначчі. Операція delete-min працює за О(log n), а часова складність для таких операцій як find-min, insert, decrease-key, meld дорівнює О(1), що робить купу Фібоначчі більш ефективною у порівнянні із бінарною. Проте бінарна купа простіша у реалізації.