Очередь с приоритетом - История изменений

СВ в 21:21, 25 октября 2026

2026-10-25T21:21:40Z

← Предыдущая		Версия 21:21, 25 октября 2026
Строка 423:		Строка 423:
	\| d-арная куча \|\| <math>O(\log_d n)</math> \|\| <math>O(1)</math> \|\| <math>O(d\log_d n)</math> \|\| <math>O(\log_d n)</math> \|\| <math>\Theta(n)</math> \|\| <math>O(n)</math> \|\| <math>O(n)</math>		\| d-арная куча \|\| <math>O(\log_d n)</math> \|\| <math>O(1)</math> \|\| <math>O(d\log_d n)</math> \|\| <math>O(\log_d n)</math> \|\| <math>\Theta(n)</math> \|\| <math>O(n)</math> \|\| <math>O(n)</math>
	\|-		\|-
	\| Биномиальная куча \|\| аморт. <math>O(1)</math> \|\| <math>O(~~\log n~~)</math> \|\| <math>O(\log n)</math> \|\| <math>O(\log n)</math> \|\| <math>O(\log n)</math> \|\| <math>O(n)</math> \|\| <math>O(n)</math>		\| Биномиальная куча \|\| аморт. <math>O(1)</math> \|\| <math>O(1)</math> \|\| <math>O(\log n)</math> \|\| <math>O(\log n)</math> \|\| <math>O(\log n)</math> \|\| <math>O(n)</math> \|\| <math>O(n)</math>
	\|-		\|-
	\| Фибоначчиева куча \|\| <math>O(1)</math> \|\| <math>O(1)</math> \|\| аморт. <math>O(\log n)</math> \|\| аморт. <math>O(1)</math> \|\| <math>O(1)</math> \|\| <math>O(n)</math> \|\| <math>O(n)</math>		\| Фибоначчиева куча \|\| <math>O(1)</math> \|\| <math>O(1)</math> \|\| аморт. <math>O(\log n)</math> \|\| аморт. <math>O(1)</math> \|\| <math>O(1)</math> \|\| <math>O(n)</math> \|\| <math>O(n)</math>

СВ: /* Дополнительные источники */

2026-10-08T21:25:52Z

Дополнительные источники

← Предыдущая		Версия 21:25, 8 октября 2026
Строка 572:		Строка 572:
	# Knuth D. E. ''The Art of Computer Programming''. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.3.		# Knuth D. E. ''The Art of Computer Programming''. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.3.
	# Wikipedia: Priority queue. URL: https://en.wikipedia.org/wiki/Priority_queue.		# Wikipedia: Priority queue. URL: https://en.wikipedia.org/wiki/Priority_queue.

			[[Category:Алгоритмы и структуры данных]]

СВ: /* Операция: слияние (Merge / Meld) */

2026-09-28T20:16:19Z

Операция: слияние (Merge / Meld)

← Предыдущая		Версия 20:16, 28 сентября 2026
Строка 221:		Строка 221:
	'''Идея.''' Объединить две очереди в одну. Стоимость решающим образом зависит от реализации: копирование массива (<math>\Theta(n)</math>), сцепка списков корней (<math>O(1)</math>), слияние лесов (<math>O(\log n)</math>).		'''Идея.''' Объединить две очереди в одну. Стоимость решающим образом зависит от реализации: копирование массива (<math>\Theta(n)</math>), сцепка списков корней (<math>O(1)</math>), слияние лесов (<math>O(\log n)</math>).

	<~~source~~ lang="text">		<syntaxhighlight lang="text">
	Алгоритм PriorityQueue-Merge(Q1, Q2)		Алгоритм PriorityQueue-Merge(Q1, Q2)
	Вход: Q1, Q2 — очереди		Вход: Q1, Q2 — очереди
Строка 231:		Строка 231:

	Сложность: двоичная куча Θ(n); биномиальная O(log n); фибоначчиева O(1).		Сложность: двоичная куча Θ(n); биномиальная O(log n); фибоначчиева O(1).
	</~~source~~>		</syntaxhighlight>

	'''Крайние случаи.''' Слияние с пустой очередью — возврат второй как есть.		'''Крайние случаи.''' Слияние с пустой очередью — возврат второй как есть.

СВ: /* Операция: удаление элемента (Delete) */

2026-09-28T20:16:08Z

Операция: удаление элемента (Delete)

← Предыдущая		Версия 20:16, 28 сентября 2026
Строка 202:		Строка 202:
	'''Идея.''' Удалить конкретный элемент по дескриптору. Универсальный приём: уменьшить ключ до <math>-\infty</math> и извлечь минимум.		'''Идея.''' Удалить конкретный элемент по дескриптору. Универсальный приём: уменьшить ключ до <math>-\infty</math> и извлечь минимум.

	<~~source~~ lang="text">		<syntaxhighlight lang="text">
	Алгоритм PriorityQueue-Delete(Q, x)		Алгоритм PriorityQueue-Delete(Q, x)
	Вход: x — дескриптор элемента		Вход: x — дескриптор элемента
Строка 211:		Строка 211:
	Сложность: O(log n) для куч (в фибоначчиевой амортизированно O(log n)).		Сложность: O(log n) для куч (в фибоначчиевой амортизированно O(log n)).
	Корректность: после Decrease-Key x — минимум, поэтому Extract-Min удаляет именно его.		Корректность: после Decrease-Key x — минимум, поэтому Extract-Min удаляет именно его.
	</~~source~~>		</syntaxhighlight>

	'''Крайний случай.''' Если у элемента есть операция прямого удаления по позиции (индексированная куча), удаляют заменой на последний и просеиванием в нужную сторону — без «<math>-\infty</math>».		'''Крайний случай.''' Если у элемента есть операция прямого удаления по позиции (индексированная куча), удаляют заменой на последний и просеиванием в нужную сторону — без «<math>-\infty</math>».

СВ: /* Операция: извлечение минимума (Extract-Min) */

2026-09-28T20:15:54Z

Операция: извлечение минимума (Extract-Min)

← Предыдущая		Версия 20:15, 28 сентября 2026
Строка 137:		Строка 137:
	'''Псевдокод (в терминах двоичной кучи).'''		'''Псевдокод (в терминах двоичной кучи).'''

	<~~source~~ lang="text">		<syntaxhighlight lang="text">
	Алгоритм PriorityQueue-Extract-Min(Q)		Алгоритм PriorityQueue-Extract-Min(Q)
	Вход: Q — непустая min-очередь		Вход: Q — непустая min-очередь
Строка 147:		Строка 147:
	5 return min		5 return min

	Сложность: двоичная куча O(log n); d-арная O(d·log_d n); биномиальная O(log n);		</syntaxhighlight>
	фибоначчиева аморт. O(log n). Память O(1).
	Корректность: после удаления оба поддерева корня — кучи, поэтому sift-down		Сложность: двоичная куча O(log n); d-арная O(d·log_d n); биномиальная O(log n); фибоначчиева аморт. O(log n). Память O(1).
	восстанавливает свойство кучи во всём дереве.
	~~</source>~~		Корректность: после удаления оба поддерева корня — кучи, поэтому sift-down восстанавливает свойство кучи во всём дереве.

	'''Крайние случаи.''' Последний элемент — очередь пустеет. Единственный ребёнок (при чётном <math>n</math>) — сравнение только с ним.		'''Крайние случаи.''' Последний элемент — очередь пустеет. Единственный ребёнок (при чётном <math>n</math>) — сравнение только с ним.

СВ: /* Операция: изменение ключа (Decrease-Key / Increase-Key) */

2026-09-28T20:15:28Z

Операция: изменение ключа (Decrease-Key / Increase-Key)

← Предыдущая		Версия 20:15, 28 сентября 2026
Строка 163:		Строка 163:
	'''Псевдокод (индексированная куча).'''		'''Псевдокод (индексированная куча).'''

	<~~source~~ lang="text">		<syntaxhighlight lang="text">
	Алгоритм Indexed-Decrease-Key(Q, id, k′)		Алгоритм Indexed-Decrease-Key(Q, id, k′)
	Вход: id — дескриптор; k′ ≤ key[id]		Вход: id — дескриптор; k′ ≤ key[id]
Строка 170:		Строка 170:
	2 i ← pos[id] # O(1) благодаря карте позиций		2 i ← pos[id] # O(1) благодаря карте позиций
	3 sift-up(i) # при обмене обновляются pos для обоих узлов		3 sift-up(i) # при обмене обновляются pos для обоих узлов
	</~~source~~>		</syntaxhighlight>

	Сложность: O(log n) (высота кучи); в фибоначчиевой куче — амортизированно O(1).		Сложность: O(log n) (высота кучи); в фибоначчиевой куче — амортизированно O(1).
Строка 178:		Строка 178:
	'''Ленивый вариант''' (когда <code>decrease-key</code> нет) — рис. 3:		'''Ленивый вариант''' (когда <code>decrease-key</code> нет) — рис. 3:

	<~~source~~ lang="text">		<syntaxhighlight lang="text">
	Алгоритм Lazy-Extract-Min(Q, dist)		Алгоритм Lazy-Extract-Min(Q, dist)
	Вход: Q — очередь с возможными устаревшими записями; dist[v] — актуальные ключи		Вход: Q — очередь с возможными устаревшими записями; dist[v] — актуальные ключи
Строка 187:		Строка 187:
	4 return (k, v)		4 return (k, v)
	5 # иначе запись устарела — просто пропускаем и берём следующую		5 # иначе запись устарела — просто пропускаем и берём следующую
	</~~source~~>		</syntaxhighlight>

	Сложность: амортизированно O(log n) на актуальное извлечение; каждая релаксация кладёт не более одной лишней записи, поэтому суммарное число записей O(m).		Сложность: амортизированно O(log n) на актуальное извлечение; каждая релаксация кладёт не более одной лишней записи, поэтому суммарное число записей O(m).

СВ: /* Операция: чтение минимума (Find-Min / Peek) */

2026-09-28T20:15:09Z

Операция: чтение минимума (Find-Min / Peek)

← Предыдущая		Версия 20:15, 28 сентября 2026
Строка 120:		Строка 120:
	'''Контракт.''' Возвращает ссылку на элемент с наименьшим ключом, не удаляя его; ошибка, если очередь пуста. В кучах минимум доступен напрямую (корень или указатель <code>min</code>) — <math>O(1)</math>; в неупорядоченном массиве — <math>O(n)</math>.		'''Контракт.''' Возвращает ссылку на элемент с наименьшим ключом, не удаляя его; ошибка, если очередь пуста. В кучах минимум доступен напрямую (корень или указатель <code>min</code>) — <math>O(1)</math>; в неупорядоченном массиве — <math>O(n)</math>.

	<~~source~~ lang="text">		<syntaxhighlight lang="text">
	Алгоритм PriorityQueue-Min(Q)		Алгоритм PriorityQueue-Min(Q)
	Вход: Q — непустая min-очередь		Вход: Q — непустая min-очередь
	Выход: элемент с наименьшим ключом		Выход: элемент с наименьшим ключом
	1 return элемент, на который указывает минимум структуры		1 return элемент, на который указывает минимум структуры
	</~~source~~>		</syntaxhighlight>

	Сложность: O(1) для всех куч (и O(1) при хранении указателя даже там, где он неявный).		Сложность: O(1) для всех куч (и O(1) при хранении указателя даже там, где он неявный).

СВ: /* Операция: вставка (Insert) */

2026-09-28T20:14:59Z

Операция: вставка (Insert)

← Предыдущая		Версия 20:14, 28 сентября 2026
Строка 101:		Строка 101:
	'''Псевдокод (в терминах двоичной кучи).'''		'''Псевдокод (в терминах двоичной кучи).'''

	<~~source~~ lang="text">		<syntaxhighlight lang="text">
	Алгоритм PriorityQueue-Insert(Q, k, v)		Алгоритм PriorityQueue-Insert(Q, k, v)
	Вход: Q — min-очередь; (k, v) — новый элемент		Вход: Q — min-очередь; (k, v) — новый элемент
Строка 109:		Строка 109:
	3 sift-up(x) # поднять, пока key[parent] > key[x]		3 sift-up(x) # поднять, пока key[parent] > key[x]
	4 size[Q] ← size[Q] + 1		4 size[Q] ← size[Q] + 1
	</~~source~~>		</syntaxhighlight>

	Сложность: двоичная куча O(log n); d-арная O(log_d n); биномиальная аморт. O(1); фибоначчиева O(1). Память O(1).		Сложность: двоичная куча O(log n); d-арная O(log_d n); биномиальная аморт. O(1); фибоначчиева O(1). Память O(1).

СВ: /* Корректность и оценка сложности */

2026-09-28T20:14:03Z

Корректность и оценка сложности

← Предыдущая		Версия 20:14, 28 сентября 2026
Строка 474:		Строка 474:
	\|about=(соблюдение контракта)		\|about=(соблюдение контракта)
	\|statement=Если реализация возвращает в <code>Extract-Min</code> элемент с минимальным ключом и сохраняет множество остальных элементов, то она удовлетворяет контракту ADT.		\|statement=Если реализация возвращает в <code>Extract-Min</code> элемент с минимальным ключом и сохраняет множество остальных элементов, то она удовлетворяет контракту ADT.
	\|proof= ~~Контракт — это постусловия таблицы из §4.~~ <code>Extract-Min</code> по определению возвращает минимум и удаляет ровно его; повторяя, получаем все постусловия для остальных операций (они затрагивают лишь множество и ключ одного элемента).		\|proof= <code>Extract-Min</code> по определению возвращает минимум и удаляет ровно его; повторяя, получаем все постусловия для остальных операций (они затрагивают лишь множество и ключ одного элемента).
	}}		}}

СВ: /* Корректность и оценка сложности */

2026-09-28T20:10:31Z

Корректность и оценка сложности

← Предыдущая		Версия 20:10, 28 сентября 2026
Строка 471:		Строка 471:
	== Корректность и оценка сложности ==		== Корректность и оценка сложности ==

	~~'''~~Теорема 1 (соблюдение контракта)~~.'''~~ Если реализация возвращает в <code>Extract-Min</code> элемент с минимальным ключом и сохраняет множество остальных элементов, то она удовлетворяет контракту ADT.		{{Теорема
			\|about=(соблюдение контракта)
	~~''Доказательство.''~~ Контракт — это постусловия таблицы из §4. <code>Extract-Min</code> по определению возвращает минимум и удаляет ровно его; повторяя, получаем все постусловия для остальных операций (они затрагивают лишь множество и ключ одного элемента). ~~<math>\blacksquare</math>~~		\|statement=Если реализация возвращает в <code>Extract-Min</code> элемент с минимальным ключом и сохраняет множество остальных элементов, то она удовлетворяет контракту ADT.
			\|proof= Контракт — это постусловия таблицы из §4. <code>Extract-Min</code> по определению возвращает минимум и удаляет ровно его; повторяя, получаем все постусловия для остальных операций (они затрагивают лишь множество и ключ одного элемента).
			}}

	'''Инвариант конкретной реализации.''' Для двоичной кучи инвариант — «свойство кучи: ключ родителя не больше ключей детей». Из него следует, что корень — минимум: любой другой ключ лежит в поддереве некоторого ребёнка и потому не меньше корня по транзитивности. Это и есть '''уточнение''' (refinement) спецификации реализацией: инвариант структуры влечёт постусловие ADT.		'''Инвариант конкретной реализации.''' Для двоичной кучи инвариант — «свойство кучи: ключ родителя не больше ключей детей». Из него следует, что корень — минимум: любой другой ключ лежит в поддереве некоторого ребёнка и потому не меньше корня по транзитивности. Это и есть '''уточнение''' (refinement) спецификации реализацией: инвариант структуры влечёт постусловие ADT.