В последнее время я начинаю писать задачи на Leetcode. Однако я немного запутался в очереди приоритетов.
Вот некоторые концепции приоритетной очереди.
Приоритетная очередь является расширением очереди со следующими свойствами.
1) Каждый элемент имеет связанный с ним приоритет.
2) Элемент с высоким приоритетом удаляется из очереди перед элементом с низким приоритетом.
/> 3) Если два элемента имеют одинаковый приоритет, они обслуживаются в соответствии с их порядком в очереди.
Использование кучи:
Куча обычно предпочтительнее для реализации приоритетной очереди, поскольку кучи обеспечивают более высокую производительность по сравнению с массивами или связанными списками. В двоичной куче getHighestPriority() может быть реализован за время O(1),
- insert() может быть реализован за время O(Logn) и
2. deleteHighestPriority() также можно реализовать за время O(Logn).
С кучей Фибоначчи функции insert() и getHighestPriority() могут быть реализованы за O(1) амортизированное время, а deleteHighestPriority() может быть реализовано за O(Logn) амортизированное время.
Используйте кучу, когда вам нужны только самые большие или самые маленькие элементы, и вам не нужно поддерживать операции быстрого поиска, удаления или поиска для произвольных элементов.
Куча — хороший выбор, когда вам нужно вычислить k самых больших или k самых маленьких элементов в коллекции. В первом случае используйте минимальную кучу, во втором — максимальную кучу.
PriorityQueue в Java
В качестве примера возьмем mergeKLists.
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) return null;
PriorityQueue<Integer> pq = new PriorityQueue<>(lists.length);
for(ListNode cur: lists){
while(cur!=null){
pq.offer(cur.val);
cur = cur.next;
}
}
ListNode dummy = new ListNode(0);
ListNode node = dummy;
while(pq.size()>0){
node.next = new ListNode(pq.poll());
node = node.next;
}
return dummy.next;
}
}
pq.poll() для ближайшего сверху. PriorityQueue по умолчанию используется для увеличения порядка.
Ну, я думаю, что указатель действительно важен.
ListNode dummy = new ListNode(0); ListNode node = dummy;
O(n * log(k)). Для n элементов мы будем вставлять и удалять каждый из кучи. Это влечет за собой O(n * 2log(k)) работы и просто становится O(n * log(k)) после удаления констант.
n = общее количество элементов во всех списках
k = количество переданных нам отсортированных списков
Вставка и удаление из двоичной кучи занимают время O(log(n)), где n — общее количество элементов в куче.
