Куча (структура данных): различия между версиями

Материал из Поле цифровой дидактики
(Новая страница: «{{Понятие |Description=В информатике '''ку́ча''' — это специализированная структура данных типа дерево, которая удовлетворяет ''свойству кучи:'' если ''B'' является узлом-потомком узла ''A'', то ключ(''A'') ≥ ключ(''B''). Из этого следует, что...»)
 
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
{{Понятие
{{Понятие
|Description=В информатике '''ку́ча'''  — это специализированная [[структура данных]] типа [[Дерево (структура данных)|дерево]], которая удовлетворяет ''свойству кучи:'' если ''B'' является узлом-потомком узла ''A'', то ключ(''A'') ≥ ключ(''B''). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют ''max-кучами'' (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют ''min-кучами''). Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух. Куча является максимально эффективной реализацией [[Абстрактный тип данных|абстрактного типа данных]], который называется [[Очередь с приоритетом (программирование)|очередью с приоритетом]]. Кучи имеют решающее значение в некоторых эффективных [[алгоритм]]ах на [[Теория графов|графах]], таких, как [[алгоритм Дейкстры]] и сортировка [[Пирамидальная сортировка|методом пирамиды]].
|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
|similar_concepts=Heap
|Environment=Scratch
}}
}}
Из определения кучи следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют ''max-кучами'' (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют ''min-кучами''). Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух. Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом.
Кучи имеют решающее значение в некоторых эффективных [[алгоритм]]ах на [[Теория графов|графах]], таких, как [[алгоритм Дейкстры]] и сортировка [[Пирамидальная сортировка|методом пирамиды]].

Текущая версия на 15:16, 5 октября 2022


Описание В информатике ку́ча — это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B).
Область знаний Информатика
Авторы
Поясняющее видео
Близкие понятия Heap
Среды и средства для освоения понятия Scratch, Python, Snap!

Из определения кучи следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами). Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух. Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом.

Кучи имеют решающее значение в некоторых эффективных алгоритмах на графах, таких, как алгоритм Дейкстры и сортировка методом пирамиды.