Как реализовать кучу в структуре данных

Введение

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

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

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

Структура данных в куче — наиболее часто задаваемый вопрос на собеседованиях. Разнообразные вопросы возникают из кучи. Давайте подробно разберемся с концепцией и реализацией структуры данных кучи.

Типы структуры данных кучи

Существует два типа структуры данных кучи

• Max heap - Из названия становится ясно, что корневой узел будет больше, чем дочерние узлы. Все родительские узлы больше, чем их соответствующие дочерние узлы. Следовательно, в максимальной куче самый верхний корневой узел больше среди дочерних.

• Мин куча - В минимальной куче корневой узел меньше дочерних узлов. Родительский узел меньше соответствующего дочернего узла. Следовательно, самый верхний корневой узел является наименьшим среди дочерних.

Операции со структурой данных кучи

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

Операция вставки

Возьмем массив A с элементами 10, 8, 5, 15. Выполните указанные шаги, чтобы сформировать максимальную кучу

• Создайте бинарное дерево и добавьте первый элемент 10 в дерево.

• Чтобы добавить следующий элемент 8, сравните его с 10 и, если он больше, поменяйте местами оба значения. В этом случае никаких изменений не происходит.

• Выполните тот же шаг для 5. Заполните дерево слева направо.

• В итоге мы получаем 15, что больше 8. Поскольку мы строим максимальную кучу, мы поменяем 15 на 8, чтобы сформировать максимальную кучу.

• Снова 15 больше, чем 10, поэтому мы меняем 10 на 15, чтобы сформировать максимальную кучу.

Алгоритм построения максимальной кучи

Шаг 1 — Создайте новый узел в конце кучи.
Шаг 2 −Назначить новое значение узлу.
Шаг 3 −Сравните значение этого дочернего узла со значением его родителя.
Шаг 4 −Если значение родительского элемента меньше, чем значение дочернего, то поменять их местами.
Шаг 5 − Повторяйте шаги 3 и 4, пока свойство кучи не будет сохранено.

Примечание:

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

Количество сравнений зависит от высоты дерева, которая оказывается временной сложностью O (nlogn).

Heapify — это процесс, в котором мы можем уменьшить количество сравнений, когда элементы сначала добавляются в дерево, а затем отправляются для сравнения. Процесс переупорядочивания элементов дерева для сохранения свойств структуры данных кучи называется heapify или heapification. Это восходящее сравнение элементов снижает временную сложность всего алгоритма.

Операция удаления

Возьмем массив A с элементами 10, 8, 5, 15. Выполните указанные шаги, чтобы сформировать операцию удаления в структуре данных кучи.

• Допустим, элемент, который нужно удалить из дерева, равен 10.

• Поменять местами последний дочерний элемент дерева на 10, т. е. поменять местами 10 на 5.

• Удалить последний элемент из дерева.

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

• Дерево теперь содержит свойства максимальной кучи, а элемент 10 удален.
  

CPP Программа реализации структуры данных кучи

#include <iostream> #include <vector> с использованием пространства имен std;

void swap(int *a, int *b) // функция для замены значений узлов { int temp = *b; // взять временную переменную *b = *a; *а = температура; } void heapify(vector<int> &hT, int i) // выполнить кучификацию { int size = hT.size(); // вычисляем размер дерева intlarge = i; интервал л = 2 * я + 1; // формируем левый узел int r = 2 * i + 2; // формируем правый узел if (l < size && hT[l] > hT[largest]) наибольший = l; if (r < size && hT[r] > hT[наибольшее]) наибольшее = r;

if (самый большой != i) { swap(&hT[i], &hT[самый большой]); // поменять местами значения heapify(hT, наибольший); } } void insert(vector<int> &hT, int newNum) // выполнить вставку в максимальную кучу { int size = hT.size(); если (размер == 0) { hT.push_back (newNum); // добавить новый узел в дерево } else { hT.push_back(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); // выполнить операцию кучи } } } void deleteNode(vector<int> &hT, int num) // удалить узел в куче { int size = hT.size(); инт я; for (i = 0; i < size; i++) { if (num == hT[i]) break; } swap(&hT[i], &hT[размер - 1]);

hT.pop_back(); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); // выполнить heapify } } void printArray(vector<int> &hT) // вывести массив в виде дерева { for (int i = 0; i < hT.size(); ++i) cout << hT [я] << " "; cout <<
"; }

int main() { vector<int> h; // массив вставить(h, 10); вставить (ч, 8); вставить (ч, 5); вставить (ч, 15); cout << "Макс. массив кучи: "; распечататьмассив(ч); удалитьУзел(ч, 5); cout << "После удаления элемента: "; распечататьмассив(ч); // напечатать массив }

Вывод:

Максимальный массив кучи: 10 8 5 15

После удаления элемента: 15 8 10

Программа C реализации структуры данных кучи

#include <stdio.h> int size = 0; void swap(int *a, int *b) // функция для замены двух значений узлов { int temp = *b; // поменять местами с помощью временной переменной *b = *a; *а = температура; } void heapify(int array[], int size, int i) // выполнить операцию heapify { if (size == 1) // размер 1 означает один элемент в куче { printf("Один элемент в куче"); } иначе { int наибольший = я; интервал л = 2 * я + 1; интервал г = 2 * я + 2; если (l < размер && массив [l] > массив [самый большой]) самый большой = l; если (r < размер && массив [r] > массив [самый большой]) самый большой = r; если (самый большой != i) { swap(&массив[i], &массив[самый большой]); // поменять местами наибольшее и текущее значение массива heapify(array, size, наибольший); // вызов функции heapify } } } void insert(int array[], int newNum) // вставка в максимальную кучу { if (size == 0) { array[0] = newNum; размер += 1; // увеличить размер кучи } else { array[size] = newNum; размер += 1; for (int i = size / 2 - 1; i >= 0; i--) { heapify (массив, размер, i); // выполнить heapify } } } void deleteRoot(int array[], int num) // удалить элемент из кучи { int i; for (i = 0; i < size; i++) { if (num == array[i]) break; }

swap(&массив[i], &массив[размер - 1]); размер -= 1; for (int i = size / 2 - 1; i >= 0; i--) { heapify (массив, размер, i); // выполнить heapify } } void printArray(int array[], int size) { for (int i = 0; i < size; ++i) printf("%d ", array[i]); printf(
"); } int main() { int h[10]; вставка (ч, 10); вставка (ч, 8); вставка (ч, 5); вставка (ч, 15); printf("Max-Heap array: "); printArray(h, size); deleteRoot(h, 5); printf("После удаления элемента: "); printArray(h, size); // распечатать массив }

Выход:

Максимальный массив кучи: 15 10 5 8

После удаления элемента: 15 10 8

Заключение

• A куча — это древовидная структура данных, имеющая форму полного двоичного дерева.

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

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

• Время сборки составляет O(nlogn), где O(logn) времени требуется для процесса heapify и O(n) времени для создания кучи.

• Очереди с внутренним приоритетом реализуют структуру данных кучи, поскольку она поддерживает операции вставки(), удаления() и извлеченияmax(), уменьшения ключа() за время O(logn).

Приятного чтения!

Ссылка: [Темы масштабирования] (https://www.scaler.com/topics/heap-data-structure/)