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