Куча (структура данных)
В компьютерных науках ку́ча — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами). Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух. Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом. Кучи имеют решающее значение в некоторых эффективных алгоритмах на графах, таких, как алгоритм Дейкстры на d-кучах и сортировка методом пирамиды.
Структуру данных куча не следует путать с понятием куча в динамическом распределении памяти. Впервые термин использовался именно для структур данных. В некоторых ранних популярных языках программирования типа ЛИСП обеспечивалось динамическое распределение памяти с использованием структуры данных «куча», которая и дала своё имя выделяемому объёму памяти.[1].
Кучи обычно реализуются в виде массивов, что исключает наличие указателей между её элементами.
Над кучами обычно проводятся следующие операции:
- найти максимум или найти минимум: найти максимальный элемент в max-куче или минимальный элемент в min-куче, соответственно
- удалить максимум или удалить минимум: удалить корневой узел в max- или min-куче, соответственно
- увеличить ключ или уменьшить ключ: обновить ключ в max- или min-куче, соответственно
- добавить: добавление нового ключа в кучу.
- слияние: соединение двух куч с целью создания новой кучи, содержащей все элементы обеих исходных.
Содержание
Варианты
- 2-3 куча
- Двуродительская куча
- Двоичная куча
- Биномиальная куча
- Очередь Бродала
- Куча с D потомками
- Фибоначчиева куча
- Куча с приоритетом самого левого
- Спаренная куча
- Асимметричная куча
- Мягкая куча
- Тернарная куча
- Декартово дерево
Сравнение теоретических оценок вариантов
Ниже приведены оценки временно́й сложности вычислений для операций над некоторыми видами кучи.[1] Там, где значение отмечено звездочкой, оценка сделана методом амортизационного анализа (по наихудшему времени), в остальных случаях оценка является регулярным худшим случаем. O(F) даёт асимптотическую верхнюю границу, а Θ(F) является асимптотически точной оценкой (см. обозначения «O» большое и «o» малое). Имена операций выбраны для min-кучи.
| Операция | Двоичная | Биномиальная | Фибоначчиева | Спаренная[2] | Бродал |
|---|---|---|---|---|---|
| найти минимум | Θ(1) | Θ(log n) or Θ(1) | Θ(1)[1] | Θ(1) | Θ(1) |
| удалить минимум | Θ(log n) | Θ(log n) | O(log n)* | O(log n)* | O(log n) |
| добавить | Θ(log n) | O(log n) | Θ(1) | O(1)* | Θ(1) |
| уменьшить ключ | Θ(log n) | Θ(log n) | Θ(1)* | O(log n)* | Θ(1) |
| слияние | Θ(n) | O(log n)** | Θ(1) | O(1)* | Θ(1) |
(*) Амортизационное время
(**) Где n — размер наибольшей кучи
Заметим, что «очередь Бродала» представляет собой реализацию очереди с параллельным приоритетом, разработанную группой во главе с Гертом Бродалом.[3]
Применение
Структуры данных типа кучи имеют множество применений.
- Пирамидальная сортировка: один из лучших применяемых методов сортировки, не имеющий квадратичных наихудших сценариев.
- Алгоритмы поиска: при использовании кучи поиск минимума, максимума, того и другого, медианы или k-того наибольшего элемента может быть сделан за линейное время (часто даже за константное время).[4]
- Алгоритмы на графах: Применение кучи в качестве структуры данных для внутреннего обхода даёт сокращение времени выполнения на полиномиальный порядок. Примерами таких проблем являются алгоритм построения минимального остовного дерева Прима и проблема кратчайшего пути Дейкстры.
Полная и почти полная бинарная куча может быть представлена очень эффективным способом с помощью индексного массива. Первый (или последний) элемент будет содержать корень. Следующие два элемента массива содержат узлы-потомки корня. Следующие четыре элемента содержат четверых потомков от двух узлов — потомков корня, и т.д. Таким образом, потомки узла уровня n будут расположены на позициях 2n и 2n+1 для массива, индексируемого с единицы, или на позициях 2n+1 и 2n+2 для массива, индексируемого с нуля. Это позволяет перемещаться вверх или вниз по дереву, выполняя простые вычисления индекса массива. Балансировка кучи делается перестановкой элементов, которые нарушают порядок. Поскольку мы можем построить кучу с помощью массива без дополнительной памяти (для узлов, например), то можно использовать пирамидальную сортировку для сортировки массива прямо на месте.
Реализации
- Стандартная библиотека шаблонов языка C++ предоставляет шаблоны функций для управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.
- Набор шаблонов Java платформы Java 2 (начиная с версии 1.5) предоставляет реализацию бинарной кучи в классе java.util.PriorityQueue<E>.
- Python имеет модуль heapq, который реализует очереди с приоритетами с помощью бинарной кучи.[5]
- Начиная с версии 5.3 PHP в стандартной библиотеке имеются методы maxheap (SplMaxHeap) и minheap (SplMinHeap).
- В Perl имеются реализации бинарной, биномиальной и фибоначчиевой куч во всеобъемлющей сети архивов.[6]
См. также
Напишите отзыв о статье "Куча (структура данных)"
Примечания
- ↑ 1 2 3 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest (1990): Introduction to algorithms. MIT Press / McGraw-Hill.
- ↑ Iacono, John (2000), [dx.doi.org/10.1007%2F3-540-44985-X_5 "Improved upper bounds for pairing heaps"], Proc. 7th Scandinavian Workshop on Algorithm Theory, vol. 1851, Lecture Notes in Computer Science, Springer-Verlag, сс. 63–77, DOI 10.1007/3-540-44985-X_5
- ↑ [www.ceid.upatras.gr/faculty/zaro/pub/jou/J9-JPDC-pq.pdf A Parallel Priority Queue with Constant Time Operations], <www.ceid.upatras.gr/faculty/zaro/pub/jou/J9-JPDC-pq.pdf>
- ↑ Frederickson, Greg N. (1993), [ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf "An Optimal Algorithm for Selection in a Min-Heap"], Information and Computation, vol. 104, Academic Press, сс. 197–214, doi:[dx.doi.org/10.1006%2Finco.1993.1030 10.1006/inco.1993.1030], <ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf>
- ↑ [docs.python.org/library/heapq.html Python heapq]
- ↑ [search.cpan.org/perldoc?Heap Perl нeap]
| ||||||||||||||||||||||
Отрывок, характеризующий Куча (структура данных)
– Можно мне присоединиться к вам? – сказал тихо подошедший Диммлер и подсел к ним.– Ежели бы мы были ангелами, так за что же мы попали ниже? – сказал Николай. – Нет, это не может быть!
– Не ниже, кто тебе сказал, что ниже?… Почему я знаю, чем я была прежде, – с убеждением возразила Наташа. – Ведь душа бессмертна… стало быть, ежели я буду жить всегда, так я и прежде жила, целую вечность жила.
– Да, но трудно нам представить вечность, – сказал Диммлер, который подошел к молодым людям с кроткой презрительной улыбкой, но теперь говорил так же тихо и серьезно, как и они.
– Отчего же трудно представить вечность? – сказала Наташа. – Нынче будет, завтра будет, всегда будет и вчера было и третьего дня было…
– Наташа! теперь твой черед. Спой мне что нибудь, – послышался голос графини. – Что вы уселись, точно заговорщики.
– Мама! мне так не хочется, – сказала Наташа, но вместе с тем встала.
Всем им, даже и немолодому Диммлеру, не хотелось прерывать разговор и уходить из уголка диванного, но Наташа встала, и Николай сел за клавикорды. Как всегда, став на средину залы и выбрав выгоднейшее место для резонанса, Наташа начала петь любимую пьесу своей матери.
Она сказала, что ей не хотелось петь, но она давно прежде, и долго после не пела так, как она пела в этот вечер. Граф Илья Андреич из кабинета, где он беседовал с Митинькой, слышал ее пенье, и как ученик, торопящийся итти играть, доканчивая урок, путался в словах, отдавая приказания управляющему и наконец замолчал, и Митинька, тоже слушая, молча с улыбкой, стоял перед графом. Николай не спускал глаз с сестры, и вместе с нею переводил дыхание. Соня, слушая, думала о том, какая громадная разница была между ей и ее другом и как невозможно было ей хоть на сколько нибудь быть столь обворожительной, как ее кузина. Старая графиня сидела с счастливо грустной улыбкой и слезами на глазах, изредка покачивая головой. Она думала и о Наташе, и о своей молодости, и о том, как что то неестественное и страшное есть в этом предстоящем браке Наташи с князем Андреем.
Диммлер, подсев к графине и закрыв глаза, слушал.
– Нет, графиня, – сказал он наконец, – это талант европейский, ей учиться нечего, этой мягкости, нежности, силы…
– Ах! как я боюсь за нее, как я боюсь, – сказала графиня, не помня, с кем она говорит. Ее материнское чутье говорило ей, что чего то слишком много в Наташе, и что от этого она не будет счастлива. Наташа не кончила еще петь, как в комнату вбежал восторженный четырнадцатилетний Петя с известием, что пришли ряженые.
Наташа вдруг остановилась.
– Дурак! – закричала она на брата, подбежала к стулу, упала на него и зарыдала так, что долго потом не могла остановиться.
– Ничего, маменька, право ничего, так: Петя испугал меня, – говорила она, стараясь улыбаться, но слезы всё текли и всхлипывания сдавливали горло.
Наряженные дворовые, медведи, турки, трактирщики, барыни, страшные и смешные, принеся с собою холод и веселье, сначала робко жались в передней; потом, прячась один за другого, вытеснялись в залу; и сначала застенчиво, а потом всё веселее и дружнее начались песни, пляски, хоровые и святочные игры. Графиня, узнав лица и посмеявшись на наряженных, ушла в гостиную. Граф Илья Андреич с сияющей улыбкой сидел в зале, одобряя играющих. Молодежь исчезла куда то.
Через полчаса в зале между другими ряжеными появилась еще старая барыня в фижмах – это был Николай. Турчанка был Петя. Паяс – это был Диммлер, гусар – Наташа и черкес – Соня, с нарисованными пробочными усами и бровями.
После снисходительного удивления, неузнавания и похвал со стороны не наряженных, молодые люди нашли, что костюмы так хороши, что надо было их показать еще кому нибудь.
Николай, которому хотелось по отличной дороге прокатить всех на своей тройке, предложил, взяв с собой из дворовых человек десять наряженных, ехать к дядюшке.
– Нет, ну что вы его, старика, расстроите! – сказала графиня, – да и негде повернуться у него. Уж ехать, так к Мелюковым.
Мелюкова была вдова с детьми разнообразного возраста, также с гувернантками и гувернерами, жившая в четырех верстах от Ростовых.
– Вот, ma chere, умно, – подхватил расшевелившийся старый граф. – Давай сейчас наряжусь и поеду с вами. Уж я Пашету расшевелю.
Но графиня не согласилась отпустить графа: у него все эти дни болела нога. Решили, что Илье Андреевичу ехать нельзя, а что ежели Луиза Ивановна (m me Schoss) поедет, то барышням можно ехать к Мелюковой. Соня, всегда робкая и застенчивая, настоятельнее всех стала упрашивать Луизу Ивановну не отказать им.
Наряд Сони был лучше всех. Ее усы и брови необыкновенно шли к ней. Все говорили ей, что она очень хороша, и она находилась в несвойственном ей оживленно энергическом настроении. Какой то внутренний голос говорил ей, что нынче или никогда решится ее судьба, и она в своем мужском платье казалась совсем другим человеком. Луиза Ивановна согласилась, и через полчаса четыре тройки с колокольчиками и бубенчиками, визжа и свистя подрезами по морозному снегу, подъехали к крыльцу.
Наташа первая дала тон святочного веселья, и это веселье, отражаясь от одного к другому, всё более и более усиливалось и дошло до высшей степени в то время, когда все вышли на мороз, и переговариваясь, перекликаясь, смеясь и крича, расселись в сани.
Две тройки были разгонные, третья тройка старого графа с орловским рысаком в корню; четвертая собственная Николая с его низеньким, вороным, косматым коренником. Николай в своем старушечьем наряде, на который он надел гусарский, подпоясанный плащ, стоял в середине своих саней, подобрав вожжи.
Было так светло, что он видел отблескивающие на месячном свете бляхи и глаза лошадей, испуганно оглядывавшихся на седоков, шумевших под темным навесом подъезда.
В сани Николая сели Наташа, Соня, m me Schoss и две девушки. В сани старого графа сели Диммлер с женой и Петя; в остальные расселись наряженные дворовые.
– Пошел вперед, Захар! – крикнул Николай кучеру отца, чтобы иметь случай перегнать его на дороге.
Тройка старого графа, в которую сел Диммлер и другие ряженые, визжа полозьями, как будто примерзая к снегу, и побрякивая густым колокольцом, тронулась вперед. Пристяжные жались на оглобли и увязали, выворачивая как сахар крепкий и блестящий снег.
Николай тронулся за первой тройкой; сзади зашумели и завизжали остальные. Сначала ехали маленькой рысью по узкой дороге. Пока ехали мимо сада, тени от оголенных деревьев ложились часто поперек дороги и скрывали яркий свет луны, но как только выехали за ограду, алмазно блестящая, с сизым отблеском, снежная равнина, вся облитая месячным сиянием и неподвижная, открылась со всех сторон. Раз, раз, толконул ухаб в передних санях; точно так же толконуло следующие сани и следующие и, дерзко нарушая закованную тишину, одни за другими стали растягиваться сани.
