Кучи

Специализированная древовидная структура данных, которая следует нескольким свойствам

В информатике куча - это специализированная древовидная структура данных, которая следует нескольким свойствам, что приводит к формированию кучи. В кучах все узлы расположены в определенном порядке, будь то порядок возрастания или убывания, что приводит к формированию двух типов куч. Куча - это, по сути, одна из максимально адекватных реализаций абстрактного типа данных, называемого приоритетной очередью, и на самом деле очереди с приоритетами часто вызываются как кучи, независимо от того, как они могли быть реализованы.

Например, если X является родительским узлом Y, то значение X следует определенному порядку относительно значения Y, и тот же порядок будет следовать по дереву. Это также объясняется на рисунке ниже.

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

В двоичной куче, если куча представляет собой полное двоичное дерево с N узлами, то она имеет наименьшую возможную высоту, равную log N.

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

1. Двоичное дерево: дерево обязательно должно быть двоичным деревом, то есть у него должно быть либо 0 дочерних узлов, либо 1 дочерний узел, либо не более 2 дочерних узлов.
2. Полное двоичное дерево: помимо того, что дерево является двоичным деревом, оно также должно соответствовать свойствам полного двоичного дерева, за исключением последнего уровня дерева, все уровни должны быть полностью заполнены. И на последнем уровне заполнение узлов выполняется слева направо, заполнение пустых узлов, чтобы сделать это дерево двоичным деревом.
3. Свойство порядка кучи: это означает, что дерево должно следовать порядку узлов, в котором они были заполнены, так как они должны быть в порядке увеличения или уменьшения значения узлов по всему дереву (подробно описано ниже)

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

1. Max Heap: в Max heap значение, присутствующее в корневом узле, должно быть самым большим среди всех узлов дерева, и аналогично родительский узел в поддереве должен быть самым большим из всех деревьев и так далее. По сути, сравнение значений выполняется между родительским узлом и его дочерним узлом, если все родительские узлы больше, чем его дочерний узел, то в конечном итоге это будет максимальная куча.
2. Минимальная куча: в минимальной куче ключ, присутствующий в корневом узле, должен быть меньше, чем все узлы, присутствующие в дереве кучи. Min heap - это полная противоположность Max Heap, если мы сравним ее с точки зрения расположения значений узлов. В этом случае также выполняется сравнение значений родительского узла и дочернего узла, единственная разница заключается в том, что значение родительского узла должно быть меньше, чем дочерний узел, и аналогично, если все узлы следуют этому свойству, это приведет к формированию мин. кучи.

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

Теперь давайте поговорим о том, передан ли нам массив и мы хотим преобразовать его в кучу, как мы это сделаем:

Предположим, что если мы сохраняем один элемент с индексом i в массиве Arr, то его родительский элемент будет сохранен с индексом i / 2 (если это не корень, поскольку у корня нет родителя) и может быть получен с помощью Arr [i / 2 ], а его левый дочерний элемент может быть получен с помощью Arr [2 ∗ i], а его правый дочерний элемент может быть получен с помощью Arr [2 ∗ i + 1]. Индекс корня в массиве будет равен 1.

Это можно лучше понять с помощью изображения, приведенного ниже.

Теперь давайте изучим способы, которыми мы можем преобразовать наше дерево в кучу, в которой все свойства, которые мы обсуждали ранее,

1. Upheapify () - эта функция выполняется в операции добавления узла в кучу, поскольку после добавления узла в нашу кучу дерево больше не остается кучей, тогда мы используем Upheapfiy, чтобы сделать его кучей. опять таки. Функция upheapify говорит сама за себя, если вы все еще не понимаете, что можете проверить ссылки. Код предназначен для общего типа данных, вы можете изменить его в соответствии с вашими потребностями.

Фрагмент кода с процессом добавления узла

public void add (элемент T) {
this.data.add (element);
this.upheapify (this.data.size () - 1);
}

частная пустота upheapify (int ci) {
if (ci == 0) {
return;
}

int pi = (ci-1) / 2;
if (! isLarger (pi, ci)) {
this.swap (pi, ci);
this.upheapify (pi);
}

}

приватный обмен пустыми (int pi, int ci) {
T ithitem = this.data.get (pi);
T jthitem = this.data.get (ci);

this.data.set (pi, jthitem);
this.data.set (ci, ithitem);
}

частное логическое значение isLarger (int pi, int ci) {
T ithitem = this.data.get (pi); // родитель
T jthitem = this.data.get (ci); // дочерний

if (this.isMin) {
return ithitem.compareTo (jthitem) ‹0;
} else {
return ithitem.compareTo (jthitem) ›0;
}
}

2. DownHeapify: эта функция используется, когда мы находимся в процессе удаления узла из дерева, аналогично добавлению при удалении узла из дерева, мы также нарушаем свойства кучи, чтобы получить обратно к правильной куче мы применяем функцию DownHeapify. Код для него также приведен ниже, просмотрите его, не требуя пояснений, и если вы хотите узнать о нем больше, вы можете просмотреть ссылки. Код предназначен для общего типа данных, вы можете изменить его в соответствии с вашими потребностями.

Фрагмент кода с процессом удаления узла

public T remove () {
T rv = this.data.get (0);
this.swap (0, this.data.size () - 1);
this.data .remove (this.data.size () - 1);
this.downheapify (0);
return rv;
}

private void downheapify (int pi) {
int lci = 2 * pi + 1;
int rci = 2 * pi + 2;
int mi = pi;

if (lci ‹ this.data.size () && this.isLarger (lci, mi)) {
mi = lci;
}

if (rci ‹this.data.size () && this .isLarger (rci, mi)) {
mi = rci;
}

if (mi! = pi) {
this.swap (mi, pi) ;
this.downheapify (mi);
}


}

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

Если вы нашли этот блог каким-либо образом полезным, не забудьте похлопать по нему. Вы также можете подписаться на меня на Medium и подписаться на мои страницы в социальных сетях, чтобы получать более информативный контент, подобный этому.

Использованная литература: