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

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

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

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

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

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

Корневой элемент будет на нулевой позиции массива, то есть куча [0].
Для любого другого узла, скажем, куча [I], у нас есть следующее:

Куча в Python по умолчанию Мин-куча и используется с помощью модуля Heapq Хипифирование , Heappop и Heapppush Функции.

Чтобы создать и использовать максимальную кучу с помощью функций библиотеки, мы можем умножить каждый элемент с -1, а затем использовать функцию библиотеки кучи, и, следовательно, она будет действовать как максимальная куча.

Давайте теперь понять, как работают функции Max-Heap и как мы можем написать код для реализации этих функций с нуля.

Понимание функций для реализации максимальной кучи

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

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

Сначала он находит узел с наибольшим значением среди данного узла и всех его детей. Затем он сворачивает данный узел, (скажем, I) с установленным узлом максимального значения (скажем, j), а затем вызывает Макс-Хипифирование Функция (рекурсивно) по узлу j, чтобы убедиться, что новое значение, назначенное узлу j, не нарушает свойство Max-Heap в его поддереве.

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

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

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

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

3. Функция Heappop

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

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

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

4. Функция Heappush

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

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

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

5. Функция ExtractMax

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

Полная реализация Python Max Heap

Теперь мы реализуем максимальную кучу в Python. Мы используем список [15, 7, 9, 4, 13] в коде и преобразуют его в максимальную кучу с помощью Build-Heap функция. Сделанная куча будет выглядеть так:

Выполнение:

import sys

#defining a class max_heap for the heap data structure

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


    # helper function to swap the two given nodes of the heap
    # this function will be needed for max-heapify and insertion 
    # in order to swap nodes which are not in order (not satisfy max-heap property)
    def swapnodes(self, node1, node2):
        self.Heap[node1], self.Heap[node2] = self.Heap[node2], self.Heap[node1]
 
    # THE MAX_HEAPIFY FUNCTION
    def max_heapify(self, i):
 
        # If the node is a not a leaf node and is lesser 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 call the max_heapify function on it
                    self.swapnodes(i, 2 * i)
                    self.max_heapify(2 * i)
 
                else:
                # Swap the node with right child and then call the max_heapify function on it
                    self.swapnodes(i, (2 * i) + 1)
                    self.max_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.max_heapify(self.root)
        return last
 
 
    # THE BUILD_HEAP FUNCTION
    def build_heap(self): 
        for i in range(self.cur_size//2, 0, -1):
            self.max_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]))
 
 

maxHeap = max_heap(10)
maxHeap.heappush(15)
maxHeap.heappush(7)
maxHeap.heappush(9)
maxHeap.heappush(4)
maxHeap.heappush(13)
maxHeap.print_heap()

Выход:

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

Выход можно проверить с иллюстрации, приведенной в примере изображения.

Заключение

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

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