Куча (структура данных): различия между версиями
Материал из Поле цифровой дидактики
Patarakin (обсуждение | вклад) |
Patarakin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
{{Понятие | {{Понятие | ||
|Description=В информатике '''ку́ча''' — это специализированная структура данных | |Description=В информатике '''ку́ча''' — это специализированная структура данных типа дерево, которая удовлетворяет ''свойству кучи:'' если ''B'' является узлом-потомком узла ''A'', то ключ(''A'') ≥ ключ(''B''). | ||
|Field_of_knowledge=Информатика | |Field_of_knowledge=Информатика | ||
|FieldActivity=Computational Thinker | |FieldActivity=Computational Thinker | ||
| Строка 7: | Строка 7: | ||
|Environment=Scratch | |Environment=Scratch | ||
}} | }} | ||
Из определения кучи следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют ''max-кучами'' (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют ''min-кучами''). Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух. Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом. | |||
Кучи имеют решающее значение в некоторых эффективных [[алгоритм]]ах на [[Теория графов|графах]], таких, как [[алгоритм Дейкстры]] и сортировка [[Пирамидальная сортировка|методом пирамиды]]. | |||
Версия 10:41, 9 сентября 2022
| Описание | В информатике ку́ча — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). |
|---|---|
| Область знаний | Информатика |
| Авторы | |
| Поясняющее видео | |
| Близкие понятия | Heap |
| Среды и средства для освоения понятия | Scratch |
Из определения кучи следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами). Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух. Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом.
Кучи имеют решающее значение в некоторых эффективных алгоритмах на графах, таких, как алгоритм Дейкстры и сортировка методом пирамиды.
