Comments 6
и также реализует first in first out для элементов с одинаковым приоритетом:
Кажется, это утверждение ломается в таком сценарии (пример для двоичной кучи):
- добавить в очередь такую последовательность пар
(1, 1), (2, 2), (2, 3), (3, 4), (3, 5), (3, 6), (3, 7), где первое число — приоритет. Ровно в таком порядке они окажутся во внутреннем массиве - извлечь минимальный элемент
(1, 1). Внутренний массив будет выглядеть так:[ (2, 2), (3, 7), (2, 3), (3, 4), (3, 5), (3, 6)](пара(3, 7)поднялась наверх, и утонула налево, так как у вершин на втором уровне равные приоритеты) - извлечь
(2, 2), массив станет таким:[ (2, 3), (3, 7), (3, 6), (3, 4), (3, 5)](поднялся элемент(3, 6)и утонул направо) - извлечь
(2, 3), массив:[ (3, 5), (3, 7), (3, 6), (3, 4)](поднялся(3, 5), тонуть ему не нужно) - извлечь
(3, 5), хотя в очереди ещё остался(3, 4), который был добавлен раньше
А, даже трёх элементов хватает:
var queue = new PriorityQueue<string, int>();
queue.Enqueue("Миша_1", 29);
queue.Enqueue("Маша_2", 30);
queue.Enqueue("Дима_3", 30);
while (queue.TryDequeue(out var name, out var age))
{
Console.WriteLine($"{name}, age {age}");
}Вывод:
Миша_1, age 29
Дима_3, age 30
Маша_2, age 30
Спасибо за дополнение, действтительно очередь с приоритетами не гарантирует сохранение порядка для элементов с одинаковым приоритетом, об этом даже явно сказано в документации, поэтому поправил статью.
> Note that the type does not guarantee first-in-first-out semantics for elements of equal priority.
что позволяет получить итоговую сложность O(log4 N)
Не понятно, как получилась такая сложность для EnqueueRange, если внутри Heapify метод MoveDown*Comparerвызывается N/Arity раз
Да, тут вышла путаница у меня с терминами из-за того, что в общем случае термин heapify применяется к процедуре, которая для конкретного элемента ставит его на нужное место чтобы куча стала в согласованное состояние:
> This function takes in an element index index, and maintains the min heap property, by swapping with the smallest element of its immediate sub-tree.
И как раз heapify имеет сложность в зависимости от высоты. Только вот в внутренней реализации .net метод Heapify производит операцию над каждым элементом, поэтому в итоге мы всё равно получим сложность равную сложности построения кучи.
А ещё Heapify в случае EnqueueRange будет работать только для пустой очереди, если там уже были элементы, то последовательно вызовется много Enqueue. В общем, метод получается скорее сахарный, чем оптимизирующий, таковым он будет только для сценария пустой кучи.
Кажется у вас ошибка в последнем примере, с изменяемым приоритетом. Вы добавляете в очередь "mutablePriorityCI" и для "Документации" и "CI".
.NET 6: PriorityQueue