Минимальная структура данных кучи – полная реализация в Python

В этой статье мы узнаем больше о минимальной куче (известной как очередь кучи в Python). Мы уже узнали о Куча и его библиотечные функции (в модуле Heapq) в Python Отказ Теперь мы узнаем о мин-куче и его реализации, а затем посмотрите на код Python для реализации Хипифирование , Heapppush и Heappop функционирует сами. Давайте сделаем быстрое повторение.

Что такое минимальная куча?

Минимальная куча – это полное двоичное дерево (полное двоичное дерево – это дерево, которое полностью заполнено, за исключением правых узлов в самом глубоком/последнем уровне), в котором каждый узел меньше или равен всему его детям. Следовательно, корневой узел кучи – самый маленький элемент. Структура данных Min-Heap обычно используется для представления очереди приоритета.

Как кучи представлены в массивах?

Мы уже видели, как куча представлена в памяти в виде массива, просто быстрое напоминание о том, что:

Корневой элемент будет на нулевой позиции массива, то есть куча [0].
Для любого другого узла, скажем, куча [I], у нас есть следующее:
- Родительский узел дан: Heap [(I -1)/2]
- Левый узел дочернего ребенка дан: Heap [(2 * I) + 1]
- Правый узел дочернего ребенка дан: Куча [(2 * I) + 2]

Понимание функций, используемых при реализации Min Heap

1. Функция Min-HealPify

Эта функция делает узел и все его потомки (дочерние узлы и их ребенок) следуют в собственности кучи. Он переставляет узлы, подняв их так, чтобы сделать данную кучу наименьшего узла в своем поддереве, после его собственности.

Эта функция сначала находит узел с наименьшим значением среди данного узла и его детей. Затем он сворачивает данный узел, (скажем, I) с установленным узлом минимального значения (скажем, j), а затем вызывает функцию min-halpify (рекурсивно) по узлу j, чтобы убедиться, что новое значение, назначенное для узла j, делает Не сломайте свойство кучи в своем поддереве.

Так как не более того, он должен пройти через глубину дерева, его временной сложность является O (d), где d – глубина, или с точки зрения количества узлов, o (log n), n – число элементы в куче.

2. Функция сборки-кучи

Эта функция строит кучу из произвольного списка (или любого другого илетного), то есть требуется список и переставляет каждый элемент, чтобы удовлетворить свойство кучи. Это может быть просто реализовано, применяя мин-Хипифирование на каждый узел несколько раз. Сложность времени этой функции выходит O (n), где n – количество элементов в куче.

3. Функция Heappop

Эта функция выскакивает минимальное значение (корневой элемент) кучи.

Это на самом деле сделано путем замены корневого узла с последним узлом и удалением последнего узла (содержащего минимальное значение), а затем вызовов Min-HealPify для корневого узла, чтобы поддерживать свойство кучи после изменения из-за замены.

Поскольку нам нужно только иметь дело с потомками, то временная сложность является O (log n), где n – количество элементов, или o (h), где h – высота дерева, который является журналом N, как это является Полное дерево.

4. Функция Heappush

Эта функция нажимает новый элемент в кучу и устраняет его в правильном положении, поддерживая свойство кучи.

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

Аналогичным образом как Heappop, момент сложности вот O (log n), поскольку нам нужно только пройти высоту поддерева.

5. Функция Extractmin

Эта функция возвращает наиболее приоритет (корневой элемент) из кучи. Поскольку нам просто нужно вернуть значение корня и без изменений в кучу, а корню доступен в o (1) время, поэтому момент времени сложности функции является O (1).

Полный Python внедрение структуры данных Min Heap

Ниже приведена полная программа для реализации Min Heap в Python.

import sys

#defining a class min_heap for the heap data structure

class min_heap: 
    def __init__(self, sizelimit):
        self.sizelimit = sizelimit
        self.cur_size = 0
        self.Heap = [0]*(self.sizelimit + 1)
        self.Heap[0] = sys.maxsize * -1
        self.root = 1


    # helper function to swap the two given nodes of the heap
    # this function will be needed for heapify and insertion to swap nodes not in order
    def swapnodes(self, node1, node2):
        self.Heap[node1], self.Heap[node2] = self.Heap[node2], self.Heap[node1]
 
    # THE MIN_HEAPIFY FUNCTION
    def min_heapify(self, i):
 
        # If the node is a not a leaf node and is greater than any of its child
        if not (i >= (self.cur_size//2) and i <= self.cur_size):
            if (self.Heap[i] > self.Heap[2 * i]  or  self.Heap[i] > self.Heap[(2 * i) + 1]): 
                if self.Heap[2 * i] < self.Heap[(2 * i) + 1]:
     # Swap the node with the left child and then call the min_heapify function on it
                    self.swapnodes(i, 2 * i)
                    self.min_heapify(2 * i)
 
                else:
                # Swap the node with right child and then call the min_heapify function on it
                    self.swapnodes(i, (2 * i) + 1)
                    self.min_heapify((2 * i) + 1)
 


    # THE HEAPPUSH FUNCTION
    def heappush(self, element):
        if self.cur_size >= self.sizelimit :
            return
        self.cur_size+= 1
        self.Heap[self.cur_size] = element 
        current = self.cur_size
        while self.Heap[current] < self.Heap[current//2]:
            self.swapnodes(current, current//2)
            current = current//2
 
 
    # THE HEAPPOP FUNCTION
    def heappop(self):
        last = self.Heap[self.root]
        self.Heap[self.root] = self.Heap[self.cur_size]
        self.cur_size -= 1
        self.min_heapify(self.root)
        return last
 
 
    # THE BUILD_HEAP FUNCTION
    def build_heap(self): 
        for i in range(self.cur_size//2, 0, -1):
            self.min_heapify(i)
 
 
    # helper function to print the heap
    def print_heap(self):
        for i in range(1, (self.cur_size//2)+1):
            print("Parent Node is "+ str(self.Heap[i])+" Left Child is "+ str(self.Heap[2 * i]) +                  " Right Child is "+ str(self.Heap[2 * i + 1]))
 
 
# Driver Code
minHeap = min_heap(10)
minHeap.heappush(15)
minHeap.heappush(7)
minHeap.heappush(9)
minHeap.heappush(4)
minHeap.heappush(13)
minHeap.print_heap()

Выход:

Parent Node is 4 Left Child is 7 Right Child is 9
Parent Node is 7 Left Child is 15 Right Child is 13

Заключение

В этой статье мы узнали о минимальной куче. Мы изучали, как функции для Хипифирование , Heapppush и Heappop Работа. Мы также реализовали структуру данных Min Heap с нуля в Python с нуля. Оставайтесь настроиться на более информативные статьи.

Счастливое обучение!