Учебное пособие по структуре данных кучи

Данные — это набор значений. Данные можно собирать и помещать в строку, в столбец, в таблицу или в виде дерева. Структура данных — это не только размещение данных в любой из этих форм. В вычислениях структура данных представляет собой любой из этих форматов, плюс взаимосвязь между значениями, плюс операции (функции), выполняемые над значениями. У вас уже должны быть базовые знания о древовидной структуре данных, прежде чем вы сюда приедете, так как содержащиеся в нем концепции будут использоваться здесь с небольшими пояснениями или без них. Если у вас нет этих знаний, прочитайте учебное пособие под названием «Учебное пособие по древовидной структуре данных для начинающих» по ссылке https://linuxhint.com/tree_data_structure_tutorial_beginners/. После этого продолжайте читать это руководство. Структура данных кучи представляет собой полное или почти полное двоичное дерево, в котором дочерний элемент каждого узла равен или меньше по значению, чем значение его родительского элемента. В качестве альтернативы, это такое дерево, в котором значение родителя равно или меньше значения любого из его дочерних элементов. Значение (датум) дерева также называется ключом.

Иллюстрация структур данных кучи

Существует два типа кучи: максимальная куча и минимальная куча. В структуре с максимальной кучей максимальное значение является корнем, а значения становятся меньше по мере спуска по дереву; любой родитель равен или больше по значению, чем любой из его непосредственных потомков. В структуре 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

В этой ситуации три ячейки пусты. Однако формулы по-прежнему применимы.

Операции

Структура данных — это формат данных (например, дерево), плюс взаимосвязь между значениями, плюс операции (функции) выполняют над значениями. Для кучи отношение, которое проходит через всю кучу, состоит в том, что родительский элемент должен быть равен или больше по значению, чем дочерние элементы, для максимальной кучи; а родительский элемент должен быть равен или меньше по значению, чем дочерние элементы, для минимальной кучи. Это отношение называется свойством кучи. Операции с кучей сгруппированы под заголовками «Создание», «Базовое», «Внутреннее» и «Проверка». Сводка операций с кучей приводится ниже:

Сводка операций с кучей

Существуют определенные программные операции, общие для кучи, а именно:

Создание кучи

create_heap: Создание кучи означает формирование объекта, представляющего кучу. В языке C вы можете создать кучу с типом объекта struct. Одним из членов структуры будет массив кучи. Остальные члены будут функциями (операциями) для кучи. Create_heap означает создание пустой кучи.

Heapify: массив кучи представляет собой частично отсортированный (упорядоченный) массив. Heapify означает предоставление массива кучи из несортированного массива — подробности см. Ниже.

Слияние: это означает формирование кучи объединения из двух разных куч — подробности см. Ниже. Две кучи должны быть как max-heap, так и min-heap. Новая куча соответствует свойству кучи, в то время как исходные кучи сохраняются (не стираются).

Объединение: это означает, что соединение двух куч одного типа для формирования новой, сохраняя дубликаты — подробности см. ниже. Новая куча соответствует свойству кучи, в то время как исходная куча уничтожается (стирается). Основное различие между объединением и объединением заключается в том, что для объединения одно дерево подходит как поддерево к корню другого дерева, что позволяет дублировать значения в новом дереве, а для объединения формируется новое дерево кучи, удаляя дубликаты.. Нет необходимости поддерживать две исходные кучи с помощью объединения.

Основные операции с кучей

find_max (find_min): найдите максимальное значение в массиве max-heap и вернуть копию или найти минимальное значение в массиве min-heap и вернуть копию.

Insert: добавить новый элемент в массив кучи и переупорядочить массив так, чтобы свойство heap для диаграмма поддерживается.

extract_max (extract_min): Найдите максимальное значение в массиве max-heap, удалите и верните его; или найдите минимальное значение в массиве min-heap, удалите и верните его.

delete_max (delete_min): Найдите корневой узел max-heap, который является первым элементом max- массив кучи, удалите его, не обязательно возвращая; или найдите корневой узел минимальной кучи, который является первым элементом массива минимальной кучи, удалите его, не обязательно возвращая его;

Replace: Найдите корневой узел любой кучи, удалите его и замените новым. Не имеет значения, будет ли возвращен старый корень.

Операции с внутренней кучей

Увеличить_ключ (уменьшить_ключ): увеличить значение любого узла для максимальной кучи и переупорядочить чтобы сохранить свойство кучи, или уменьшите значение любого узла для минимальной кучи и перегруппируйте так, чтобы сохранить свойство кучи.

Удалить: удалить любой узел, затем изменить порядок, чтобы свойство heap поддерживается для max-heap или min-heap.

shift_up: перемещать узел вверх в max-heap или min-heap на столько, сколько необходимо, переупорядочивая для поддержания кучи свойство.

shift_down: переместить узел вниз в max-heap или min-heap на столько, сколько необходимо, изменяя порядок для сохранения свойства heap.

Проверка a Куча

Размер: Возвращает количество ключей (значений) в куче; он не включает пустые места массива кучи. Куча может быть представлена ​​кодом, как на схеме, или массивом.

is_empty: Возвращает логическое значение true, если в куче нет узла или логическое значение false, если в куче есть хотя бы один узел.

Просеивание в куче

Выполняется просеивание вверх и просеивание вниз:

Sift-Up: это означает обмен узла с его родителем. Если свойство кучи не удовлетворено, замените родительский элемент на его собственный. Продолжайте этот путь по пути, пока свойство кучи не будет удовлетворено. Процедура может достичь корня.

Sift-Down: это означает обмен узла большого значения с меньшим из двух его дочерних элементов (или одним дочерним элементом для почти полная куча). Если свойство кучи не удовлетворяется, поменяйте местами нижний узел с меньшим узлом двух его собственных дочерних узлов. Продолжайте этот путь по пути, пока свойство кучи не будет удовлетворено. Процедура может достичь листа.

Heapifying

Heapify означает сортировку несортированного массива, чтобы свойство кучи было удовлетворено для max-heap или min-heap. Это означает, что в новом массиве могут быть пустые места.. Базовый алгоритм создания кучи max-heap или min-heap выглядит следующим образом:

— если корневой узел более крайний, чем любой из его дочерних узлов, то обменивается корнем с менее экстремальным дочерним узлом узел.

— повторите этот шаг с дочерними узлами в схеме обхода дерева предварительного заказа.

Окончательное дерево — это дерево кучи, удовлетворяющее свойству кучи. Куча может быть представлена ​​в виде древовидной диаграммы или массива. Полученная куча представляет собой частично отсортированное дерево, то есть частично отсортированный массив.

Подробности операции с кучей

В этом разделе статьи приводятся подробные сведения об операциях с кучей.

Создание подробностей кучи

create_heap

См. выше!

heapify

См. выше

merge

Если массивы кучи,

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 удаляет дубликаты, убедитесь, что узлы, у которых не было дочерних элементов в исходной куче, по-прежнему не имеют дочерних узлов в новой куче.

meld

Алгоритм объединения двух куч одного типа (либо двух максимальных, либо двух минимальных) выглядит следующим образом:

— Сравнить два корневых узла.

— Сделать менее крайний корень и остальную часть его дерева (поддерево) вторым дочерним элементом крайнего корня.

— Просеять случайный дочерний элемент корня теперь самого крайнего поддерева, вниз в крайнее поддерево.

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

Основные операции с кучей

find_max (find_min)

Это означает найти максимальное значение в массиве max-heap и вернуть копию или найти минимальное значение в массиве min-heap и верните копию. Массив кучи по определению уже удовлетворяет свойству кучи. Итак, просто верните копию первого элемента массива.

insert

Это означает добавление нового элемента в массив кучи и переставьте массив так, чтобы свойство кучи диаграммы сохранялось (удовлетворялось). Алгоритм этого для обоих типов куч следующий:

— Предположим, что полное двоичное дерево. Это означает, что при необходимости массив должен быть заполнен в конце пустыми ячейками. Общее количество узлов в полной куче — 1, или 3, или 7, или 15, или 31 и т. Д .; продолжайте удваивать и добавлять 1.

— Поместите узел в наиболее подходящее пустое место по величине, ближе к концу кучи (ближе к концу массива кучи). Если пустого места нет, начните новую строку снизу слева.

— Просеивайте, если необходимо, пока свойство кучи не будет удовлетворено.

extract_max (extract_min)

Найдите максимальное значение в массиве max-heap, удалите и верните его; или найдите минимальное значение в массиве min-heap, удалите и верните его. Алгоритм для extract_max (extract_min) следующий:

— Удалить корневой узел.

— Взять (удалить) самый нижний правый узел (последний узел в массиве ) и поместите в корень.

— Просеивайте по мере необходимости, пока не будет выполнено свойство кучи.

delete_max (delete_min)

Найдите корневой узел max-heap, который является первым элементом массива max-heap, удалите его, не обязательно возвращая его; или найдите корневой узел min-heap, который является первым элементом массива min-heap, удалите его, не обязательно возвращая его. Алгоритм удаления корневого узла следующий:

— Удалить корневой узел.

— Взять (удалить) самый нижний правый узел (последний узел в массиве ) и поместите в корень.

— Просеивайте по мере необходимости, пока свойство кучи не будет удовлетворено.

replace

Найдите корневой узел любой кучи, удалите его и замените новым. Неважно, будет ли возвращен старый рут. Просеивайте, если необходимо, пока свойство кучи не будет удовлетворено.

Операции с внутренней кучей

Увеличить_ключ (уменьшить_ключ)

Увеличьте значение любого узла для максимальной кучи и измените порядок, чтобы сохранить свойство кучи, или уменьшите значение любого узла для минимальной кучи и перегруппируйте, чтобы сохранить свойство кучи. Просеивайте вверх или вниз по мере необходимости, пока свойство кучи не будет удовлетворено.

delete

Удалите интересующий узел, затем переставьте , так что свойство кучи сохраняется для максимальной или минимальной кучи. Алгоритм удаления узла следующий:

— Удалить интересующий узел.

— Взять (удалить) самый нижний правый узел (последний узел в массиве ) и поместите в индекс удаленного узла. Если удаленный узел находится в последней строке, то в этом нет необходимости.

— Просеивайте вверх или вниз по мере необходимости, пока не будет выполнено свойство кучи.

Перемещайте узел вверх в максимальной или минимальной куче на столько, сколько необходимо, изменяя порядок для сохранения свойства кучи — просеивание.

Перемещайте узел вниз в максимальной или минимальной куче на столько, сколько необходимо, переставляя свойство кучи — просеять.

Проверка кучи

size

См. выше!

См. выше!

Другие классы куч

Куча, описанная в этой статье, может рассматриваться как основная (общая) куча. Есть и другие классы куч. Однако два, которые вам следует знать помимо этого, — это двоичная куча и d-арная куча.

двоичная куча

Двоичная куча похожа на эту основную, но с большим количеством ограничений. В частности, двоичная куча должна быть полным деревом. Не путайте полное дерево с полным деревом.

d-ary Heap

Бинарная куча — это 2- ари куча. Куча, в которой каждый узел имеет 3 дочерних узла, представляет собой 3-элементную кучу. Куча, в которой каждый узел имеет 4 дочерних узла, представляет собой 4-местную кучу и т. Д. У динамической кучи есть и другие ограничения.

Заключение

Куча — это полное или почти полное двоичное дерево, удовлетворяющее свойству кучи. Свойство heap имеет 2 альтернативы: для max-heap родительский элемент должен быть равен или больше по значению, чем непосредственные дочерние элементы; для минимальной кучи родительский элемент должен иметь значение, равное или меньшее, чем непосредственные дочерние элементы. Куча может быть представлена ​​в виде дерева или массива. Когда он представлен в массиве, корневой узел является первым узлом массива; и если узел имеет индекс n, его первый дочерний элемент в массиве имеет индекс 2n + 1, а его следующий дочерний элемент находится в индексе 2n + 2. В куче есть определенные операции, которые выполняются с массивом.

Chrys

Оцените статью
nanomode.ru
Добавить комментарий