Оглавление:
Определение - что значит куча?
Куча в контексте структуры данных - это древовидная структура данных, которая удовлетворяет свойству кучи, где каждому элементу присваивается ключевое значение или весовое значение. Ключ с более низким значением всегда имеет родительский узел с ключом с более высоким значением. Это называется структурой max-heap, и среди всех узлов корневой узел имеет самый высокий ключ.
Иногда древовидная структура имеет правило обратной структуры, где элемент с ключом с более высоким значением всегда имеет ключ с более низким значением в качестве родительского узла. Это называется структурой минимальной кучи, и среди всех узлов корневой узел имеет самый низкий ключ.
Техопедия объясняет кучу
Не существует практических ограничений на количество дочерних элементов, которые каждый узел может иметь в куче, даже если у каждого узла обычно максимум два. Куча считается наиболее эффективной реализацией абстрактного типа данных, известного как очередь с приоритетами. Реализация кучи имеет важное значение в различных алгоритмах графа (включая алгоритм Дейкстры), а также в алгоритме сортировки heapsort.
Кучи имеют несколько отклонений, которые действуют как реализации очереди с приоритетами абстрактного типа данных с высокой эффективностью. Многие приложения, такие как графовые алгоритмы, требуют реализации очередей с приоритетами.
Массив является наиболее распространенной формой реализации кучи, где не требуется указателей для связи между его элементами.
Кучи выполняют несколько операций, в том числе:
- Find-max: поиск узла с наивысшим ключом среди группы узлов
- Find-min: ищет самый низкий ключевой узел среди группы узлов
- Delete-max: удаляет самый высокий ключевой узел среди группы узлов
- Delete-min: удаляет самый низкий ключевой узел среди группы узлов
Кучи также включают функции, которые выполняют слияние, вставку и смену ключей.
Это определение было написано в контексте структуры данных
