Сравнение кучи и дерева
Опубликовано: 20 Февраля, 2023
Что такое куча?
Куча — это специальная структура данных на основе дерева, в которой дерево является полным двоичным деревом.
Типы структуры данных кучи:
Как правило, кучи могут быть двух типов:
- Max-Heap: в Max-Heap ключ, присутствующий в корневом узле, должен быть наибольшим среди ключей, присутствующих во всех его дочерних узлах. Одно и то же свойство должно быть рекурсивно истинным для всех поддеревьев в этом двоичном дереве.
- Min-Heap: в Min-Heap ключ, присутствующий в корневом узле, должен быть минимальным среди ключей, присутствующих во всех его дочерних элементах. Одно и то же свойство должно быть рекурсивно истинным для всех поддеревьев в этом двоичном дереве.
Что такое дерево?
Дерево нелинейно и имеет иерархическую структуру данных, состоящую из набора узлов, так что каждый узел дерева хранит значение и список ссылок на другие узлы («потомки»).
Типы структур данных дерева:
Обычно различают следующие типы древовидных структур данных:
- Бинарное дерево: узел бинарного дерева может иметь не более двух дочерних узлов.
- Двоичное дерево поиска: как следует из названия, двоичные деревья поиска используются для различных алгоритмов поиска и сортировки. Примеры включают дерево AVL и красно-черное дерево. Это нелинейная структура данных. Он показывает, что значение левого узла меньше, чем у его родителя, а значение правого узла больше, чем у его родителя.
Сравнение кучи и дерева:
| С. Нет | куча | Дерево |
|---|---|---|
| 1 | Куча сама по себе является деревом. | Дерево — это не куча. |
| 2 | Обычно куча бывает двух типов: максимальная куча и минимальная куча. | Принимая во внимание, что дерево может быть разных типов, например. двоичное дерево, BST (бинарное дерево поиска), дерево AVL и т. д. |
| 3 | Куча упорядочена. | Двоичное дерево не упорядочено, но упорядочено BST. |
| 4 | Вставка и удаление в худшем случае займут время O(log(N)) . | Вставка и удаление потребуют O (N) в худшем случае, если дерево перекошено. |
| 5 | Нахождение значения Min/Max в куче равно O(1) в соответствующей куче Min/Max. | Нахождение минимального/максимального значения в BST — это O (log (N)) и двоичное дерево — O (N). |
| 6 | Куча также может называться приоритетной очередью. | Дерево также можно назвать связным неориентированным графом без цикла. |
| 7 | Куча может быть построена с линейной временной сложностью. | BST: O(N * log(N)) и двоичное дерево: O(N). |
| 8 | Приложения: алгоритм Прима и алгоритм Дейкстры. | Приложения: Spanning Trees, Trie, B+ Tree, BST, Heap. |
Статьи по Теме:
- Введение в дерево — учебные пособия по структурам данных и алгоритмам
- Введение в кучу - учебные пособия по структурам данных и алгоритмам