Phenquestions
Иллюстрация структур данных кучи
Есть два типа кучи: максимальная куча и минимальная куча. В структуре с максимальной кучей максимальное значение является корнем, а значения становятся меньше по мере спуска по дереву; любой родитель равен или больше по значению, чем любой из его непосредственных потомков. В структуре min-heap минимальным значением является корень, а значения становятся больше по мере спуска дерева; любой родитель либо равен, либо меньше по значению, чем любой из его непосредственных потомков. На следующих диаграммах первая - это максимальная куча, а вторая - минимальная куча:
Для обеих куч обратите внимание, что для пары дочерних элементов не имеет значения, является ли тот, что слева, большее значение. Строка на уровне в дереве не обязательно должна заполняться слева направо от минимума до максимума; он также не обязательно заполняется от максимума до минимума, слева.
Представление кучи в массиве
Чтобы программное обеспечение могло легко использовать кучу, куча должна быть представлена в виде массива. Максимальная куча выше, представленная в виде массива:
89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69Это делается, начиная с корневого значения в качестве первого значения для массива. Значения размещаются непрерывно, читая дерево слева направо, сверху вниз. Если элемент отсутствует, его позиция в массиве пропускается. У каждого узла есть двое потомков. Если узел находится в индексе (позиции) n, его первый дочерний элемент в массиве имеет индекс 2n + 1, а его следующий дочерний элемент находится в индексе 2n + 2. 89 имеет индекс 0; его первый дочерний элемент, 85, имеет индекс 2 (0) + 1 = 1, а его второй дочерний элемент имеет индекс 2 (0) + 2 = 2. 85 находится под индексом 1; его первый дочерний элемент, 84, имеет индекс 2 (1) + 1 = 3, а его второй дочерний элемент, 82, находится в индексе 2 (1) + 2 = 4. 79 находится под индексом 5; его первый дочерний элемент, 65, имеет индекс 2 (5) + 1 = 11, а его второй дочерний элемент имеет индекс 2 (5) + 2 = 12. Формулы применяются к остальным элементам массива.
Такой массив, в котором значение элемента и взаимосвязь между элементами подразумевается положением элемента, называется неявной структурой данных.
Неявная структура данных для указанной выше минимальной кучи:
65, 68, 70, 73, 71, 83, 84,,,, 79, 80,,, 85, 89Вышеупомянутая максимальная куча представляет собой полное двоичное дерево, но не полное двоичное дерево. Поэтому некоторые локации (позиции) в массиве пусты. Для полного двоичного дерева ни одно место в массиве не будет пустым.
Теперь, если бы куча была почти полным деревом, например, если бы отсутствовало значение 82, тогда массив был бы:
89, 85, 87, 84`` 79, 73, 80, 81``, 65, 69В этой ситуации три локации пусты. Однако формулы все еще применимы.
Операции
Структура данных - это формат данных (e.грамм. дерево), плюс взаимосвязь между значениями, плюс операции (функции), выполняемые над значениями. Для кучи отношение, которое проходит через всю кучу, состоит в том, что родительский элемент должен быть равен или больше по значению, чем дочерние элементы, для максимальной кучи; и родитель должен быть равен или меньше по значению, чем дети, для минимальной кучи. Это отношение называется свойством кучи. Операции с кучей сгруппированы под заголовками Создание, Базовая, Внутренняя и Проверка. Ниже приводится краткое описание операций с кучей:
Сводка операций с кучей
Есть определенные программные операции, которые являются общими для кучи, а именно:
Создание кучи
create_heap: создание кучи означает формирование объекта, представляющего кучу. На языке C вы можете создать кучу с типом объекта struct. Одним из членов структуры будет массив кучи. Остальные члены будут функциями (операциями) для кучи. Create_heap означает создание пустой кучи.
Heapify: массив кучи - это частично отсортированный (упорядоченный) массив. Heapify означает предоставление массива кучи из несортированного массива - подробности см. Ниже.
Слияние: это означает формирование объединенной кучи из двух разных куч - подробности см. Ниже. Две кучи должны быть как max-heap, так и min-heap. Новая куча соответствует свойству heap, в то время как исходная куча сохраняется (не стирается).
Слияние: это означает объединение двух куч одного типа, чтобы сформировать новую, сохраняя дубликаты - см. Подробности ниже. Новая куча соответствует свойству кучи, в то время как исходная куча уничтожается (стирается). Основное различие между слиянием и слиянием заключается в том, что для слияния одно дерево подходит как поддерево к корню другого дерева, позволяя дублировать значения в новом дереве, а для слияния формируется новое дерево кучи, удаляя дубликаты. Нет необходимости поддерживать две исходные кучи с помощью слияния.
Основные операции с кучей
find_max (find_min): найдите максимальное значение в массиве max-heap и верните копию или найдите минимальное значение в массиве min-heap и верните копию.
Вставить: добавить новый элемент в массив кучи и переупорядочить массив так, чтобы сохранялось свойство кучи диаграммы.
extract_max (extract_min): найти максимальное значение в массиве max-heap, удалить и вернуть его; или найдите минимальное значение в массиве min-heap, удалите и верните его.
delete_max (delete_min): найдите корневой узел max-heap, который является первым элементом массива max-heap, удалите его, не обязательно возвращая его; или найдите корневой узел min-heap, который является первым элементом массива min-heap, удалите его, не обязательно возвращая его;
Заменить: найдите корневой узел любой кучи, удалите его и замените новым. Неважно, будет ли возвращен старый рут.
Операции с внутренней кучей
Увеличить_key (уменьшить_key): увеличить значение любого узла для максимальной кучи и переупорядочить, чтобы сохранить свойство кучи, или уменьшить значение любого узла для минимальной кучи и переупорядочить, чтобы сохранить свойство кучи.
Удалить: удалить любой узел, затем изменить порядок, чтобы свойство кучи сохранялось для максимальной или минимальной кучи.
shift_up: перемещать узел вверх в max-heap или min-heap столько, сколько необходимо, переставляя для сохранения свойства кучи.
shift_down: переместить узел вниз в max-heap или min-heap на столько, сколько необходимо, переставляя для сохранения свойства кучи.
Осмотр кучи
Размер: Это возвращает количество ключей (значений) в куче; он не включает пустые места массива кучи. Куча может быть представлена кодом, как на схеме, или массивом.
пустой: Это возвращает логическое значение true, если в куче нет узла, или логическое значение false, если в куче есть хотя бы один узел.
Просеивание в кучу
Есть отсеивание и отсеивание:
Sift-Up: Это означает, что узел поменяется местами с его родителем. Если свойство кучи не удовлетворено, замените родительский элемент на его собственный. Продолжайте этот путь по пути, пока свойство кучи не будет удовлетворено. Процедура может достигнуть корня.
Просеивание вниз: Это означает обмен узла большого значения с меньшим из двух его дочерних элементов (или одним дочерним элементом для почти полной кучи). Если свойство кучи не выполняется, замените нижний узел меньшим узлом двух его собственных дочерних узлов. Продолжайте этот путь по пути, пока свойство кучи не будет удовлетворено. Процедура может дойти до листа.
Кучу
Heapify означает сортировку несортированного массива, чтобы свойство кучи было удовлетворено для max-heap или min-heap. Это означает, что в новом массиве могут быть пустые места. Базовый алгоритм создания кучи max-heap или min-heap выглядит следующим образом:
- если корневой узел более крайний, чем любой из его дочерних узлов, то поменяйте корень с менее крайним дочерним узлом.
- Повторите этот шаг с дочерними узлами в схеме обхода дерева предварительного заказа.
Последнее дерево - это дерево кучи, удовлетворяющее свойству кучи. Куча может быть представлена как древовидная диаграмма или в виде массива. Полученная куча представляет собой частично отсортированное дерево, i.е. частично отсортированный массив.
Детали операции кучи
В этом разделе статьи подробно описаны операции с кучей.
Создание кучи деталей
create_heap
См. Выше!
нагружать
См. Выше
слияние
Если массивы кучи,
89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69а также
89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71объединены, результат без дубликатов может быть,
89, 85, 87, 84, 82, 83, 81, 80, 79, 73, 68, 65, 69, 70, 71После некоторого просеивания. Обратите внимание, что в первом массиве 82 нет дочерних элементов. В результирующем массиве он находится под индексом 4; и его позиции с индексом 2 (4) + 1 = 9 и 2 (4) + 2 = 10 свободны. Это означает, что у него также нет дочерних элементов на новой древовидной диаграмме. Исходные две кучи не следует удалять, поскольку их информация на самом деле не находится в новой куче (новом массиве). Базовый алгоритм объединения куч одного типа следующий:
- Присоедините один массив к основанию другого массива.
- Heapify удаляет дубликаты, следя за тем, чтобы узлы, у которых не было дочерних элементов в исходной куче, по-прежнему не имели дочерних элементов в новой куче.
объединить
Алгоритм объединения двух куч одного типа (двух максимальных или двух минимальных) выглядит следующим образом:
- Сравните два корневых узла.
- Сделайте менее крайний корень и остальную часть его дерева (поддерево) вторым потомком крайнего корня.
- Просеиваем заблудшего потомка корня теперь крайнего поддерева, вниз в крайнем поддереве.
Полученная куча по-прежнему соответствует свойству кучи, в то время как исходная куча уничтожается (стирается). Исходные кучи могут быть уничтожены, потому что вся информация, которой они владеют, все еще находится в новой куче.
Основные операции с кучей
find_max (find_min)
Это означает найти максимальное значение в массиве max-heap и вернуть копию или найти минимальное значение в массиве min-heap и вернуть копию. Массив кучи по определению уже удовлетворяет свойству кучи. Итак, просто верните копию первого элемента массива.
вставлять
Это означает добавление нового элемента в массив кучи и изменение порядка массива таким образом, чтобы свойство кучи диаграммы сохранялось (удовлетворялось). Алгоритм этого для обоих типов куч следующий:
- Предположим полное двоичное дерево. Это означает, что при необходимости массив должен быть заполнен в конце пустыми ячейками. Общее количество узлов в полной куче - 1, 3, 7, 15 или 31 и т. Д.; продолжайте удваивать и добавлять 1.
- Поместите узел в наиболее подходящее пустое место по величине, ближе к концу кучи (к концу массива кучи). Если пустого места нет, начните новую строку снизу слева.
- При необходимости просеивайте, пока свойство кучи не будет удовлетворено.
extract_max (экстракт_мин)
Найдите максимальное значение в массиве max-heap, удалите и верните его; или найдите минимальное значение в массиве min-heap, удалите и верните его. Алгоритм extract_max (extract_min) выглядит следующим образом:
- Удалите корневой узел.
- Возьмите (удалите) крайний нижний правый узел (последний узел в массиве) и поместите в корень.
- Просеивайте по мере необходимости, пока свойство кучи не будет удовлетворено.
delete_max (delete_min)
Найдите корневой узел max-heap, который является первым элементом массива max-heap, удалите его, не обязательно возвращая его; или найдите корневой узел минимальной кучи, который является первым элементом массива минимальной кучи, удалите его, не обязательно возвращая его. Алгоритм удаления корневого узла следующий:
- Удалите корневой узел.
- Возьмите (удалите) крайний нижний правый узел (последний узел в массиве) и поместите в корень.
- Просеивайте по мере необходимости, пока свойство кучи не будет удовлетворено.
заменять
Найдите корневой узел любой кучи, удалите его и замените новым. Неважно, будет ли возвращен старый рут. При необходимости просеивайте, пока свойство кучи не будет удовлетворено.
Операции с внутренней кучей
Увеличить_кей (уменьшить_кей)
Увеличьте значение любого узла для максимальной кучи и переставьте так, чтобы сохранялось свойство кучи, или уменьшите значение любого узла для минимальной кучи и измените порядок, чтобы сохранить свойство кучи. Просеивайте вверх или вниз по мере необходимости, пока свойство кучи не будет удовлетворено.
Удалить
Удалите интересующий узел, затем переставьте так, чтобы свойство кучи сохранялось для max-heap или min-heap. Алгоритм удаления узла следующий:
- Удалите интересующий узел.
- Возьмите (удалите) самый нижний правый узел (последний узел в массиве) и поместите его в индекс удаленного узла. Если удаленный узел находится в последней строке, то в этом нет необходимости.
- Просеивайте вверх или вниз по мере необходимости, пока свойство кучи не будет удовлетворено.
сдвигаются вверх
Перемещайте узел вверх в max-heap или min-heap столько, сколько необходимо, меняя порядок для сохранения свойства кучи - просеивайте вверх.
перейти вниз
Переместите узел вниз в max-heap или min-heap на столько, сколько необходимо, переставляя для сохранения свойства кучи - просеять вниз.
Осмотр кучи
размер
См. Выше!
пустой
См. Выше!
Другие классы куч
Кучу, описанную в этой статье, можно рассматривать как основную (общую) кучу. Есть и другие классы куч. Тем не менее, два, которые вы должны знать помимо этого, - это двоичная куча и д-арная куча.
Двоичная куча
Двоичная куча похожа на эту основную, но с большим количеством ограничений. В частности, двоичная куча должна быть полным деревом. Не путайте полное дерево с полным деревом.
д-арная куча
Бинарная куча - это двухзначная куча. Куча, в которой каждый узел имеет 3 дочерних узла, представляет собой 3-местную кучу. Куча, в которой каждый узел имеет 4 дочерних узла, представляет собой 4-местную кучу и т. Д. У дурацкой кучи есть другие ограничения.
Заключение
Куча - это полное или почти полное двоичное дерево, удовлетворяющее свойству кучи. Свойство heap имеет 2 альтернативы: для max-heap родительский элемент должен быть равен или больше по значению, чем непосредственные дочерние элементы; для минимальной кучи родительский элемент должен иметь значение, равное или меньшее, чем непосредственные дочерние элементы. Куча может быть представлена в виде дерева или массива. Когда он представлен в массиве, корневой узел является первым узлом массива; и если узел находится в индексе n, его первый дочерний элемент в массиве имеет индекс 2n + 1, а его следующий дочерний элемент находится в индексе 2n + 2. В куче есть определенные операции, которые выполняются с массивом.
Chrys
