Структура данных кучи

В этом руководстве вы узнаете, что такое структура данных кучи. Также вы найдете рабочие примеры операций с кучей в C, C ++, Java и Python.

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

Полное двоичное дерево - это специальное двоичное дерево, в котором

  • каждый уровень, кроме, возможно, последнего, заполнен
  • все узлы как можно дальше слева

Свойство кучи - это свойство узла, в котором

  • (для максимальной кучи) ключ каждого узла всегда больше, чем его дочерний узел / ов, а ключ корневого узла является самым большим среди всех других узлов;
  • (для минимальной кучи) ключ каждого узла всегда меньше, чем дочерний узел / с, а ключ корневого узла является наименьшим среди всех других узлов.

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

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

Heapify

Heapify - это процесс создания структуры данных кучи из двоичного дерева. Он используется для создания Min-Heap или Max-Heap.

  1. Пусть входной массив будет
  2. Создайте полное двоичное дерево из массива
  3. Начните с первого индекса нелистового узла, индекс которого равен n/2 - 1.
  4. Установить текущий элемент iкак largest.
  5. Индекс левого потомка равен, 2i + 1а правого потомка - 2i + 2.
    Если leftChildбольше чем currentElement(т.е. элемент по ithиндексу), устанавливается leftChildIndexкак самый большой.
    Если rightChildбольше, чем элемент в largest, установить rightChildIndexкак largest.
  6. Заменить largestнаcurrentElement
  7. Повторяйте шаги 3-7, пока поддеревья также не будут скопированы в кучу.

Алгоритм

 Heapify(array, size, i) set i as largest leftChild = 2i + 1 rightChild = 2i + 2 if leftChild > array(largest) set leftChildIndex as largest if rightChild > array(largest) set rightChildIndex as largest swap array(i) and array(largest)

Чтобы создать Max-Heap:

 MaxHeap(array, size) loop from the first index of non-leaf node down to zero call heapify

Для Min-Heap оба leftChildи rightChildдолжны быть меньше родительского для всех узлов.

Вставить элемент в кучу

Алгоритм вставки в Max Heap

 If there is no node, create a newNode. else (a node is already present) insert the newNode at the end (last node from left to right.) heapify the array
  1. Вставьте новый элемент в конец дерева.
  2. Насыпьте дерево.

Для Min Heap приведенный выше алгоритм изменен так, что parentNodeон всегда меньше, чем newNode.

Удалить элемент из кучи

Алгоритм удаления в Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Выберите элемент, который нужно удалить.
  2. Поменяйте его местами с последним элементом.
  3. Удалите последний элемент.
  4. Насыпьте дерево.

Для Min Heap приведенный выше алгоритм изменен так, что оба childNodesзначения больше меньше чем currentNode.

Peek (Найдите макс. / Мин.)

Операция Peek возвращает максимальный элемент из Max Heap или минимальный элемент из Min Heap без удаления узла.

Для максимальной и минимальной кучи

 вернуть rootNode

Извлечение-Макс / Мин

Extract-Max возвращает узел с максимальным значением после его удаления из Max Heap, тогда как Extract-Min возвращает узел с минимальным значением после его удаления из Min Heap.

Примеры Python, Java, C / C ++

Python Java C C ++ 
 # Max-Heap data structure in 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-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr)) 
  // Max-Heap data structure in Java import java.util.ArrayList; class Heap ( void heapify(ArrayList hT, int i) ( int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (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 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 hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; j--) ( heapify(hT, j); ) ) void printArray(ArrayList array, int size) ( for (Integer i : array) ( System.out.print(i + " "); ) System.out.println(); ) public static void main(String args()) ( ArrayList array = new ArrayList(); 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-Heap array: "); h.printArray(array, size); h.deleteNode(array, 4); System.out.println("After deleting an element: "); h.printArray(array, size); ) )
 // Max-Heap data structure in C #include 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("Single element in the heap"); ) else ( int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (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  = 0; i--) ( heapify(array, size, i); ) ) void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); ) 
 // Max-Heap data structure in C++ #include #include using namespace std; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(vector &hT, int i) ( int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) void insert(vector &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 &hT, int num) ( int size = hT.size(); int i; for (i = 0; i  = 0; i--) ( heapify(hT, i); ) ) void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )

Приложения со структурой данных кучи

  • Куча используется при реализации приоритетной очереди.
  • Алгоритм Дейкстры
  • Сортировка кучи

Интересные статьи...