Куча структура данных python

Куча (структура данных)

Этот тип структуры данных также называют двоичной кучей.

Операции над кучей

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

Создание кучи (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-кучи — одинаково:

Извлечение максимального и минимального

• Извлечение максимального: возвращает узел с максимальным значением после удаления его из 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(ArrayListhT, 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 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 < 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 array, int size) < for (Integer i : array) < System.out.print(i + " "); >System.out.println(); > public static void main(String args[]) < ArrayListarray = 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-кучи: "); h.printArray(array, size); h.deleteNode(array, 4); System.out.println("После удаления элемента "); h.printArray(array, size); > >

C

// Реализация max-кучи на Си #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("Один элемент в куче"); >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()

C++

// Реализация max-кучи на 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 < 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 &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 < 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 &hT) < for (int i = 0; i < hT.size(); ++i) cout int main() < vectorheapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout

Источник

Heap queue (or heapq) in Python

Heap data structure is mainly used to represent a priority queue. In Python, it is available using the “heapq” module. The property of this data structure in Python is that each time the smallest heap element is popped(min-heap). Whenever elements are pushed or popped, heap structure is maintained. The heap[0] element also returns the smallest element each time. Let’s see various Operations on the heap in Python.

Creating a simple heap

The heapify(iterable):- This function is used to convert the iterable into a heap data structure. i.e. in heap order.

Python3

The created heap is : [1, 3, 9, 7, 5]

Appending and Popping Items Efficiently

• heappush(heap, ele): This function is used to insert the element mentioned in its arguments into a heap. The order is adjusted, so that heap structure is maintained.
• heappop(heap): This function is used to remove and return the smallest element from the heap. The order is adjusted, so that heap structure is maintained.

Python3

The created heap is : [1, 3, 9, 7, 5] The modified heap after push is : [1, 3, 4, 7, 5, 9] The popped and smallest element is : 1

Appending and Popping simultaneously

• heappushpop(heap, ele):- This function combines the functioning of both push and pop operations in one statement, increasing efficiency. Heap order is maintained after this operation.
• heapreplace(heap, ele):- This function also inserts and pops elements in one statement, but it is different from the above function. In this, the element is first popped, then the element is pushed. i.e, the value larger than the pushed value can be returned. heapreplace() returns the smallest value originally in the heap regardless of the pushed element as opposed to heappushpop().

Python3

The popped item using heappushpop() is : 1 The popped item using heapreplace() is : 3

Find the largest and smallest elements from Heap in Python

• nlargest(k, iterable, key = fun): This function is used to return the k largest elements from the iterable specified and satisfy the key if mentioned.
• nsmallest(k, iterable, key = fun): This function is used to return the k smallest elements from the iterable specified and satisfy the key if mentioned.

Python3

The 3 largest numbers in list are : [10, 9, 8] The 3 smallest numbers in list are : [1, 3, 4]

Example:

Python3

Heap: [1, 4, 2, 7, 5, 3] Heap after push: [1, 4, 2, 7, 5, 3, 6] Smallest element: 1 Heap after pop: [2, 4, 3, 7, 5, 6] Smallest 3 elements: [2, 3, 4] Largest 2 elements: [7, 6]

This program creates a heap queue using the heapq module in Python and performs various operations such as converting a list into a heap, adding a new value to the heap, removing the smallest element from the heap, getting the n smallest and n largest elements from the heap.

Note that the heapq module in Python provides functions for performing heap operations on lists in-place, without creating a separate data structure for the heap. The heapq module is efficient and easy to use, making it a popular choice for implementing priority queues and other data structures in Python.

Advantages of using a heap queue (or heapq) in Python:

• Efficient: A heap queue is a highly efficient data structure for managing priority queues and heaps in Python. It provides logarithmic time complexity for many operations, making it a popular choice for many applications.
• Space-efficient: Heap queues are space-efficient, as they store elements in an array-based representation, minimizing the overhead associated with node-based data structures like linked lists.
• Easy to use: Heap queues in Python are easy to use, with a simple and intuitive API that makes it easy to perform basic operations like inserting, deleting, and retrieving elements from the heap.
• Flexible: Heap queues in Python can be used to implement various data structures like priority queues, heaps, and binary trees, making them a versatile tool for many applications.

Disadvantages of using a heap queue (or heapq) in Python:

• Limited functionality: Heap queues are primarily designed for managing priority queues and heaps, and may not be suitable for more complex data structures and algorithms.
• No random access: Heap queues do not support random access to elements, making it difficult to access elements in the middle of the heap or modify elements that are not at the top of the heap.
• No sorting: Heap queues do not support sorting, so if you need to sort elements in a specific order, you will need to use a different data structure or algorithm.
• Not thread-safe: Heap queues are not thread-safe, meaning that they may not be suitable for use in multi-threaded applications where data synchronization is critical.

Overall, heap queues are a highly efficient and flexible data structure for managing priority queues and heaps in Python, but may have limited functionality and may not be suitable for all applications.

Источник