Куча (структура данных)
В этой статье вы узнаете, что из себя представляет структура данных под названием куча.
Что такое куча
Куча (структура данных) — это полное двоичное дерево, удовлетворяющее свойству кучи: если узел A — это родитель узла B, то ключ узла A ≥ ключ узла B.
- Если любой узел всегда больше дочернего узла (узлов), а ключ корневого узла является наибольшим среди всех остальных узлов, это max-куча.
- Если любой узел всегда меньше дочернего узла (узлов), а ключ корневого узла является наименьшим среди всех остальных узлов, это min-куча.
Этот тип структуры данных также называют двоичной кучей.
Операции над кучей
Давайте разберем несколько основных операций, которые можно производить над кучей, и посмотрим на алгоритмы этих операций.
Создание кучи (heapify)
Heapify — это метод для создания кучи из двоичного дерева. Он используется для создания min-кучи или max-кучи.
Шаг 1. Пусть у нас есть такой массив с 6 элементами:
Шаг 2. Создаем полное двоичное дерево из этого массива:
Шаг 3. Начнем с первого нелистового узла, его индекс равен n/2 - 1
. В нашем случае индекс равен 2:
Шаг 4. Пусть текущий элемент с индексом i
будет наибольшим. Значит, i — это индекс наибольшего узла (largest
).
Шаг 5. Индекс левого дочернего элемента (leftChild
) равен 2i + 1
, а правого (rightChild
) — 2i + 2
.
- Если
leftChild
больше, чемcurrentElement
(т.е. элемент с индексомi
), leftChildIndex — индекс наибольшего узла (largest
). - Если
rightChild
больше, чем элемент с индексомlargest
, rightChildIndex — индекс наибольшего узла (largest
).
Шаг 6. Обменяем значения largest
и currentElement
.
Шаг 7. Повторяем шаги 3–7 до тех пор, пока поддеревья также не станут кучами.
Алгоритм
Heapify(array, size, i)
присвоим largest значение i
leftChild = 2i + 1
rightChild = 2i + 2
если leftChild > array[largest]
присвоим largest значение leftChildIndex
если rightChild > array[largest]
присвом largest значение rightChildIndex
обменяем array[i] и array[largest]
Для создания max-кучи:
MaxHeap(array, size)
цикл от первого индекса нелистового узла до 0
вызов heapify
Для создания min-кучи:
То же самое, только leftChild
и rightChild
должны быть меньше родителя для всех узлов.
Добавление элемента
Шаг 1. Вставьте новый элемент в конец дерева.
Шаг 2. Примените метод heapify к дереву.
Алгоритм для max-кучи
если нет узла создать newNode иначе если узел уже существует вставить newNode в конец дерева
применить heapify к массиву
Алгоритм для min-кучи
Всё то же самое, но parentNode всегда должен быть меньше newNode.
Удаление элемента
Шаг 1. Выбираем элемент, который необходимо удалить.
Шаг 2. Обменяем этот элемент с последним.
Шаг 3. Удаляем посдений элемент.
Шаг 4. Применяем метод heapify к дереву.
Алгоритм для max-кучи
если nodeToBeDeleted это leafNode удалить nodeToBeDeleted
иначе обменять nodeToBeDeleted с lastLeafNode удалить noteToBeDeleted
применить heapify к массиву
Алгоритм для min-кучи
Всё то же самое, только оба дочерних узла childNodes
должны быть больше, чем текущий узел currentNode
.
Поиск максимального и минимального (peek)
Операция peek возвращает максимальный элемент из max-кучи и минимальный элемент из min-кучи без удаления узла.
Для max-кучи и min-кучи — одинаково:
вернуть rootNode
Извлечение максимального и минимального
- Извлечение максимального: возвращает узел с максимальным значением после удаления его из max-кучи.
- Извлечение минимального: возвращает узел с минимальным значением после удаления его из min-кучи.
Где применяются
- Для реализации приоритетной очереди.
- Алгоритм Дейкстры.
- Пирамидальная сортировка.
Реализация на языках программирования
Python
# Реализация max-кучи на Python
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i]
heapify(arr, n, largest)
def insert(array, newNum):
size = len(array)
if size == 0:
array.append(newNum)
else:
array.append(newNum);
for i in range((size//2)-1, -1, -1):
heapify(array, size, i)
def deleteNode(array, num):
size = len(array)
i = 0
for i in range(0, size):
if num == array[i]:
break
array[i], array[size-1] = array[size-1], array[i]
array.remove(num)
for i in range((len(array)//2)-1, -1, -1):
heapify(array, len(array), i)
arr = []
insert(arr, 3)
insert(arr, 4)
insert(arr, 9)
insert(arr, 5)
insert(arr, 2)
print ("Массив max-кучи: " + str(arr))
deleteNode(arr, 4)
print("После удаления элемента: " + str(arr))
Java
// Реализация max-кучи на Java
import java.util.ArrayList;
class Heap {
void heapify(ArrayList<Integer> hT, int i) {
int size = hT.size();
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < size && hT.get(l) > hT.get(largest))
largest = l;
if (r < size && hT.get(r) > hT.get(largest))
largest = r;
if (largest != i) {
int temp = hT.get(largest);
hT.set(largest, hT.get(i));
hT.set(i, temp);
heapify(hT, largest);
}
}
void insert(ArrayList<Integer> hT, int newNum) {
int size = hT.size();
if (size == 0) {
hT.add(newNum);
} else {
hT.add(newNum);
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(hT, i);
}
}
}
void deleteNode(ArrayList<Integer> hT, int num)
{
int size = hT.size();
int i;
for (i = 0; i < size; i++)
{
if (num == hT.get(i))
break;
}
int temp = hT.get(i);
hT.set(i, hT.get(size-1));
hT.set(size-1, temp);
hT.remove(size-1);
for (int j = size / 2 - 1; j >= 0; j--)
{
heapify(hT, j);
}
}
void printArray(ArrayList<Integer> array, int size) {
for (Integer i : array) {
System.out.print(i + " ");
}
System.out.println();
}
public static void main(String args[]) {
ArrayList<Integer> array = new ArrayList<Integer>();
int size = array.size();
Heap h = new Heap();
h.insert(array, 3);
h.insert(array, 4);
h.insert(array, 9);
h.insert(array, 5);
h.insert(array, 2);
System.out.println("Массив max-кучи: ");
h.printArray(array, size);
h.deleteNode(array, 4);
System.out.println("После удаления элемента ");
h.printArray(array, size);
}
}
C
// Реализация max-кучи на Си
#include <stdio.h>
int size = 0;
void swap(int *a, int *b)
{
int temp = *b;
*b = *a;
*a = temp;
}
void heapify(int array[], int size, int i)
{
if (size == 1)
{
printf("Один элемент в куче");
}
else
{
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < size && array[l] > array[largest])
largest = l;
if (r < size && array[r] > array[largest])
largest = r;
if (largest != i)
{
swap(&array[i], &array[largest]);
heapify(array, size, largest);
}
}
}
void insert(int array[], int newNum)
{
if (size == 0)
{
array[0] = newNum;
size += 1;
}
else
{
array[size] = newNum;
size += 1;
for (int i = size / 2 - 1; i >= 0; i--)
{
heapify(array, size, i);
}
}
}
void deleteRoot(int array[], int num)
{
int i;
for (i = 0; i < size; i++)
{
if (num == array[i])
break;
}
swap(&array[i], &array[size - 1]);
size -= 1;
for (int i = size / 2 - 1; i >= 0; i--)
{
heapify(array, size, i);
}
}
void printArray(int array[], int size)
{
for (int i = 0; i < size; ++i)
printf("%d ", array[i]);
printf("\n");
}
int main()
{
int array[10];
insert(array, 3);
insert(array, 4);
insert(array, 9);
insert(array, 5);
insert(array, 2);
printf("Массив max-кучи: ");
printArray(array, size);
deleteRoot(array, 4);
printf("После удаления элемента: ");
printArray(array, size);
}
C++
// Реализация max-кучи на C++
#include <iostream>
#include <vector>
using namespace std;
void swap(int *a, int *b)
{
int temp = *b;
*b = *a;
*a = temp;
}
void heapify(vector<int> &hT, int i)
{
int size = hT.size();
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < size && hT[l] > hT[largest])
largest = l;
if (r < size && hT[r] > hT[largest])
largest = r;
if (largest != i)
{
swap(&hT[i], &hT[largest]);
heapify(hT, largest);
}
}
void insert(vector<int> &hT, int newNum)
{
int size = hT.size();
if (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();
int i;
for (i = 0; i < size; i++)
{
if (num == hT[i])
break;
}
swap(&hT[i], &hT[size - 1]);
hT.pop_back();
for (int i = size / 2 - 1; i >= 0; i--)
{
heapify(hT, i);
}
}
void printArray(vector<int> &hT)
{
for (int i = 0; i < hT.size(); ++i)
cout << hT[i] << " ";
cout << "\n";
}
int main()
{
vector<int> heapTree;
insert(heapTree, 3);
insert(heapTree, 4);
insert(heapTree, 9);
insert(heapTree, 5);
insert(heapTree, 2);
cout << "Массив max-кучи: ";
printArray(heapTree);
deleteNode(heapTree, 4);
cout << "После удаления элемента: ";
printArray(heapTree);
}