Структура даних купи

У цьому підручнику ви дізнаєтеся, що таке структура даних купи. Крім того, ви знайдете робочі приклади операцій з купою на C, C ++, Java та Python.

Структура даних купи - це повне двійкове дерево, яке задовольняє властивості купи . Його також називають двійковою купою .

Повне двійкове дерево - це спеціальне двійкове дерево, в якому

  • кожен рівень, крім можливо останнього, заповнюється
  • всі вузли максимально ліві

Властивість купи - це властивість вузла, в якому

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

Операції з купою

Деякі важливі операції, що виконуються над купою, описані нижче разом із їх алгоритмами.

Посилити

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. Посилити дерево.

Для Мін Heap, вище алгоритм змінюється таким чином, що обидва childNodesбільше , менше currentNode.

Заглянути (знайти макс. / Хв.)

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

І для 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); )

Додаток до структури даних купи

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

Цікаві статті...