А Макс-Хіп це повне бінарне дерево, у якому значення в кожному внутрішньому вузлі більше або дорівнює значенням у дочірніх вузлах. Відображення елементів купи в масив є тривіальним: якщо вузол зберігає індекс k, то його лівий дочірній елемент зберігається за індексом 2k+1 і його правий дочірній елемент в індексі 2k+2 .
Приклади Max Heap:
Як представлено Max Heap?
Максимальна купа — це повне бінарне дерево. Максимальна купа зазвичай представляється у вигляді масиву. Кореневий елемент буде в Arr[0]. У таблиці нижче показано індекси інших вузлів для i-го вузла, тобто Arr[i]:
- Arr[(i-1)/2] Повертає батьківський вузол.
- Arr[(2*i)+1] Повертає лівий дочірній вузол.
- Arr[(2*i)+2] Повертає правий дочірній вузол.
Операції над максимальною купою:
- getMax() : повертає кореневий елемент Max Heap. Час Складність цієї операції становить О(1) .
- extractMax() : видаляє максимальний елемент із MaxHeap. Часова складність цієї операції становить O(log n) оскільки ця операція потребує підтримки властивості купи (за допомогою виклику heapify()) після видалення кореня.
- вставити() : Вставлення нового ключа займає O(log n) час. Додаємо новий ключ у кінці дерева. Якщо новий ключ менший за батьківського, нам не потрібно нічого робити. В іншому випадку нам потрібно перейти вгору, щоб виправити порушену властивість купи.
Примітка: У наведеній нижче реалізації ми виконуємо індексацію з індексу 1, щоб спростити реалізацію.
Python
перетворення рядка в json у java
баш сон
# Python3 implementation of Max Heap> import> sys> class> MaxHeap:> >def> __init__(>self>, maxsize):> > >self>.maxsize>=> maxsize> >self>.size>=> 0> >self>.Heap>=> [>0>]>*> (>self>.maxsize>+> 1>)> >self>.Heap[>0>]>=> sys.maxsize> >self>.FRONT>=> 1> ># Function to return the position of> ># parent for the node currently> ># at pos> >def> parent(>self>, pos):> > >return> pos>/>/> 2> ># Function to return the position of> ># the left child for the node currently> ># at pos> >def> leftChild(>self>, pos):> > >return> 2> *> pos> ># Function to return the position of> ># the right child for the node currently> ># at pos> >def> rightChild(>self>, pos):> > >return> (>2> *> pos)>+> 1> ># Function that returns true if the passed> ># node is a leaf node> >def> isLeaf(>self>, pos):> > >if> pos>>=> (>self>.size>/>/>2>)>and> pos <>=> self>.size:> >return> True> >return> False> ># Function to swap two nodes of the heap> >def> swap(>self>, fpos, spos):> > >self>.Heap[fpos],>self>.Heap[spos]>=> (>self>.Heap[spos],> >self>.Heap[fpos])> ># Function to heapify the node at pos> >def> maxHeapify(>self>, pos):> ># If the node is a non-leaf node and smaller> ># than any of its child> >if> not> self>.isLeaf(pos):> >if> (>self>.Heap[pos] <>self>.Heap[>self>.leftChild(pos)]>or> >self>.Heap[pos] <>self>.Heap[>self>.rightChild(pos)]):> ># Swap with the left child and heapify> ># the left child> >if> (>self>.Heap[>self>.leftChild(pos)]>> >self>.Heap[>self>.rightChild(pos)]):> >self>.swap(pos,>self>.leftChild(pos))> >self>.maxHeapify(>self>.leftChild(pos))> ># Swap with the right child and heapify> ># the right child> >else>:> >self>.swap(pos,>self>.rightChild(pos))> >self>.maxHeapify(>self>.rightChild(pos))> ># Function to insert a node into the heap> >def> insert(>self>, element):> > >if> self>.size>>=> self>.maxsize:> >return> >self>.size>+>=> 1> >self>.Heap[>self>.size]>=> element> >current>=> self>.size> >while> (>self>.Heap[current]>> >self>.Heap[>self>.parent(current)]):> >self>.swap(current,>self>.parent(current))> >current>=> self>.parent(current)> ># Function to print the contents of the heap> >def> Print>(>self>):> > >for> i>in> range>(>1>, (>self>.size>/>/> 2>)>+> 1>):> >print>(>'PARENT : '> +> str>(>self>.Heap[i])>+> >'LEFT CHILD : '> +> str>(>self>.Heap[>2> *> i])>+> >'RIGHT CHILD : '> +> str>(>self>.Heap[>2> *> i>+> 1>]))> ># Function to remove and return the maximum> ># element from the heap> >def> extractMax(>self>):> >popped>=> self>.Heap[>self>.FRONT]> >self>.Heap[>self>.FRONT]>=> self>.Heap[>self>.size]> >self>.size>->=> 1> >self>.maxHeapify(>self>.FRONT)> > >return> popped> # Driver Code> if> __name__>=>=> '__main__'>:> > >print>(>'The maxHeap is '>)> > >maxHeap>=> MaxHeap(>15>)> >maxHeap.insert(>5>)> >maxHeap.insert(>3>)> >maxHeap.insert(>17>)> >maxHeap.insert(>10>)> >maxHeap.insert(>84>)> >maxHeap.insert(>19>)> >maxHeap.insert(>6>)> >maxHeap.insert(>22>)> >maxHeap.insert(>9>)> >maxHeap.>Print>()> > >print>(>'The Max val is '> +> str>(maxHeap.extractMax()))> |
>
>Вихід
The maxHeap is PARENT : 84LEFT CHILD : 22RIGHT CHILD : 19 PARENT : 22LEFT CHILD : 17RIGHT CHILD : 10 PARENT : 19LEFT CHILD : 5RIGHT CHILD : 6 PARENT : 17LEFT CHILD : 3RIGHT CHILD : 9 The Max val is 84>
Використання функцій бібліотеки:
Ми використовуємо heapq клас для реалізації Heap у Python. За замовчуванням мінімальна купа реалізована цим класом. Але ми множимо кожне значення на -1, щоб ми могли використовувати його як MaxHeap.
Python3
об'єктивна java
# Python3 program to demonstrate working of heapq> from> heapq>import> heappop, heappush, heapify> # Creating empty heap> heap>=> []> heapify(heap)> # Adding items to the heap using heappush> # function by multiplying them with -1> heappush(heap,>->1> *> 10>)> heappush(heap,>->1> *> 30>)> heappush(heap,>->1> *> 20>)> heappush(heap,>->1> *> 400>)> # printing the value of maximum element> print>(>'Head value of heap : '> +> str>(>->1> *> heap[>0>]))> # printing the elements of the heap> print>(>'The heap elements : '>)> for> i>in> heap:> >print>((>->1>*>i), end>=>' '>)> print>(>'
'>)> element>=> heappop(heap)> # printing the elements of the heap> print>(>'The heap elements : '>)> for> i>in> heap:> >print>(>->1> *> i, end>=> ' '>)> |
sts завантажити
>
>Вихід
Head value of heap : 400 The heap elements : 400 30 20 10 The heap elements : 30 10 20>
Використання функцій бібліотеки з методом dunder для чисел, рядків, кортежів, об’єктів тощо
Ми використовуємо heapq клас для реалізації Heaps у Python. За замовчуванням мінімальна купа реалізована цим класом.
Щоб реалізувати MaxHeap, не обмежуючись лише числами, а будь-яким типом об’єкта (рядок, кортеж, об’єкт тощо), ми повинні
- Створіть клас Wrapper для елемента в списку.
- Перевизначити __lt__ метод dunder для отримання зворотного результату.
Нижче наведено реалізацію згаданого тут методу.
'abc's in numbers'
Python3
'''> Python3 program to implement MaxHeap Operation> with built-in module heapq> for String, Numbers, Objects> '''> from> functools>import> total_ordering> import> heapq>|_+_| |