ИТ Блог. Администрирование серверов на основе Linux (Ubuntu, Debian, CentOS, openSUSE)
Суббота, 7 декабря, 2024
Сегодня у нас 1 праздник:
7 декабря 2004 года вышел в свет Thunderbird версии 1.0, хотя его корни уходят в 2003 год, когда он отделился от проекта Mozilla. Изначально программа была призвана разрушить монополию проприетарных почтовых клиентов, предложив альтернативу с открытым исходным кодом, безопасную и настраиваемую.

Руководство по структуре данных кучи

Руководство по структуре данных кучи

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

 

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

Есть два типа кучи: максимальная и минимальная куча. Структура максимальной кучи — это когда максимальное значение является корнем, а значения становятся меньше по мере спуска дерева; любой родитель равен или больше по значению, чем любой из его непосредственных потомков. В структуре min-heap минимальным значением является корень, а значения становятся больше по мере спуска дерева; любой родитель равен или меньше по значению, чем любой из его непосредственных потомков. На следующих диаграммах первая — это максимальная куча, а вторая — минимальная куча:

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

 

Представление кучи в массиве

Чтобы программное обеспечение могло легко использовать кучу, куча должна быть представлена в виде массива. Максимальная куча выше, представленная в виде массива:

89,   85,   87,   84,   82,   79, 73,  80,   81,   ,   ,  65,   69prediv>

Это делается, начиная с корневого значения в качестве первого значения для массива. Значения размещаются непрерывно путем чтения дерева слева направо, сверху вниз. Если элемент отсутствует, его позиция в массиве пропускается. У каждого узла есть двое потомков. Если узел находится в индексе (позиции) 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 означает создание пустой кучи.

 

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

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

 

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

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

 

Осмотр кучи

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

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

 

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

Есть отсеивание и отсеивание:

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

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

 

Нагромождение

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 свободны. Это означает, что у него также нет дочерних элементов на новой древовидной диаграмме. Исходные две кучи не следует удалять, поскольку их информация на самом деле не находится в новой куче (новом массиве). Базовый алгоритм объединения куч одного типа следующий:

 

meld

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

 

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

 

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

 

find_max (find_min)

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

 

insert

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

 

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

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

 

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

increase_key (decrease_key)

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

delete

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

 

shift_up

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

 

shift_down

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

 

Осмотр кучи

size

См. Выше!

is_empty

См. Выше!

 

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

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

 

Binary Heap

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

 

d-ary Heap

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

 

Вывод

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

Exit mobile version