Посібник із Heaps у Python

Вступ

Уявіть гамірний аеропорт, де щохвилини злітають і приземляються рейси. Подібно до того, як авіадиспетчери визначають пріоритет рейсів на основі терміновості, купи допомагають нам керувати та обробляти дані на основі певних критеріїв, гарантуючи, що найбільш «термінові» або «важливі» дані завжди доступні у верхній частині.

У цьому посібнику ми вирушимо в подорож, щоб зрозуміти купи з нуля. Ми почнемо з демістифікації того, що таке купи та їхні властивості. З цього моменту ми зануримося у власну реалізацію куп у Python heapq модуль і досліджуйте його багатий набір функцій. Отже, якщо ви коли-небудь задавалися питанням, як ефективно керувати динамічним набором даних, де часто потрібен елемент із найвищим (або найнижчим) пріоритетом, вас чекає задоволення.

Що таке Heap?

Перше, що ви хотіли б зрозуміти, перш ніж занурюватися в використання куп що таке купа. Купа виділяється у світі структур даних як електростанція на основі дерева, особливо вправна підтримання порядку та ієрархії. Хоча для недосвідченого ока воно може нагадувати двійкове дерево, нюанси в його структурі та керівних правилах чітко виділяють його.

Однією з визначальних характеристик купи є її природа як a повне двійкове дерево. Це означає, що кожен рівень дерева, крім, можливо, останнього, повністю заповнений. На цьому останньому рівні вузли заповнюються зліва направо. Така структура гарантує, що купи можуть бути ефективно представлені та маніпулювати ними за допомогою масивів або списків, при цьому позиція кожного елемента в масиві відображає його розташування в дереві.

Однак справжня сутність купи полягає в її замовлення. У макс, значення будь-якого заданого вузла перевищує або дорівнює значенням його дочірніх вузлів, розміщуючи найбільший елемент прямо в корені. З іншого боку, а хв. хв працює за протилежним принципом: значення будь-якого вузла менше або дорівнює значенням дочірніх вузлів, гарантуючи, що найменший елемент знаходиться в корені.

У міру просування ми глибше зануримося в те, як ці невід’ємні властивості купи забезпечують ефективні операції та як Python heapq модуль плавно інтегрує купи в наші спроби кодування.

Характеристики та властивості відвалів

Купи з їх унікальною структурою та принципами впорядкування дають набір відмінних характеристик і властивостей, які роблять їх безцінними в різних обчислювальних сценаріях.

Перш за все, це купи за своєю суттю ефективний. Їх деревоподібна структура, зокрема повний двійковий формат дерева, гарантує, що такі операції, як вставка та витяг елементів пріоритету (максимального або мінімального), можуть виконуватися за логарифмічний час, як правило O (журнал n). Ця ефективність є благом для алгоритмів і програм, які потребують частого доступу до пріоритетних елементів.

Іншою помітною властивістю куп є їх ефективність пам'яті. Оскільки купи можуть бути представлені за допомогою масивів або списків без необхідності явних покажчиків на дочірні або батьківські вузли, вони економлять місце. Позиція кожного елемента в масиві відповідає його розташуванню в дереві, що забезпечує передбачуваний і простий обхід і маніпуляції.

Властивість упорядкування куп, будь то максимальна чи мінімальна купа, гарантує це корінь завжди містить елемент з найвищим пріоритетом. Таке послідовне впорядкування забезпечує швидкий доступ до елемента з найвищим пріоритетом без необхідності пошуку по всій структурі.

Крім того, купи є різнобічний. У той час як двійкові купи (де кожен батько має не більше двох дітей) є найпоширенішими, купи можна узагальнити, щоб мати більше двох дітей, відомих як d-арні купи. Ця гнучкість дозволяє виконувати тонке налаштування на основі конкретних випадків використання та вимог до продуктивності.

Нарешті, купи є самоналагоджувальна. Кожного разу, коли елементи додаються або видаляються, структура перебудовується, щоб зберегти свої властивості. Це динамічне балансування гарантує, що купа залишається оптимізованою для своїх основних операцій у будь-який час.

Коли ми глибше заглибимося в реалізацію та практичні застосування Python, перед нами розкриється справжній потенціал куп.

Типи куп

Не всі купи однакові. Залежно від порядку та структурних властивостей купи можна класифікувати на різні типи, кожен з яких має власний набір застосувань і переваг. Є дві основні категорії макс та хв. хв.

Найбільш відмінною рисою a макс полягає в тому, що значення будь-якого заданого вузла більше або дорівнює значенням його дочірніх вузлів. Це гарантує, що найбільший елемент у купі завжди знаходиться в корені. Така структура особливо корисна, коли є потреба часто звертатися до максимального елемента, як у певних реалізаціях пріоритетної черги.

Відповідник максимальної купи, a хв. хв гарантує, що значення будь-якого даного вузла менше або дорівнює значенням його дочірніх вузлів. Це позиціонує найменший елемент купи в корені. Мінімальні купи є неоціненними в сценаріях, де найменший елемент має першочергове значення, наприклад, в алгоритмах, які мають справу з обробкою даних у реальному часі.

Окрім цих основних категорій, купи також можна виділити на основі їхнього фактора розгалуження:

Хоча бінарні купи є найпоширенішими, у яких кожен із батьків має щонайбільше двох дочірніх елементів, концепцію купи можна розширити до вузлів, які мають більше двох дочірніх елементів. В д-арна купа, кожен вузол має не більше d дітей. Цю варіацію можна оптимізувати для конкретних сценаріїв, наприклад, зменшити висоту дерева для прискорення певних операцій.

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

Названа на честь знаменитої послідовності Фібоначчі Купа Фібоначчі пропонує кращу амортизацію часу виконання багатьох операцій порівняно з бінарними або біноміальними купами. Вони особливо корисні в алгоритмах оптимізації мережі.

Реалізація купи Python – The heapq Модулі

Python пропонує вбудований модуль для операцій із купою – the heapq модуль. Цей модуль надає набір функцій, пов’язаних із купою, які дозволяють розробникам перетворювати списки на купи та виконувати різноманітні операції з купою без необхідності спеціальної реалізації. Давайте зануримося в нюанси цього модуля та в те, як він дає вам силу купи.

Команда heapq модуль не надає окремого типу даних купи. Натомість він пропонує функції, які працюють зі звичайними списками Python, перетворюючи та розглядаючи їх як бінарні купи.

Цей підхід ефективно використовує пам’ять і легко інтегрується з існуючими структурами даних Python.

Це означає, що це купи представлені у вигляді списків in heapq. Краса цього представлення полягає в його простоті – система індексів списку від нуля служить неявним бінарним деревом. Для будь-якого даного елемента в позиції i, його:

• Ліва дитина на позиції 2*i + 1
• Права дитина на позиції 2*i + 2
• Батьківський вузол знаходиться на позиції (i-1)//2

Ця неявна структура гарантує відсутність потреби в окремому представленні бінарного дерева на основі вузлів, що робить операції простими та мінімальним використанням пам’яті.

Важливо відзначити, що heapq Модулі за замовчуванням створює мінімальні купи. Це означає, що найменший елемент завжди знаходиться в корені (або першій позиції в списку). Якщо вам потрібна максимальна купа, вам доведеться інвертувати порядок, помноживши елементи на -1 або скористайтеся спеціальною функцією порівняння.

Пітона heapq Модуль надає набір функцій, які дозволяють розробникам виконувати різноманітні операції із купою зі списками.

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

Як перетворити список на купу

Команда heapify() функція є відправною точкою для багатьох завдань, пов’язаних із купою. Він приймає iterable (як правило, список) і переставляє його елементи на місці, щоб задовольнити властивості min heap:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

Це виведе переупорядкований список, який представляє дійсну мінімальну купу:

[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

Як додати елемент до купи

Команда heappush() функція дозволяє вставити новий елемент у купу, зберігаючи властивості купи:

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

Запуск коду дасть вам список елементів, які зберігають властивість min heap:

[3, 5, 7]

Як видалити та повернути найменший елемент із купи

Команда heappop() функція витягує та повертає найменший елемент із купи (корінь у min heap). Після видалення він гарантує, що список залишається дійсною купою:

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

Це виведе найменший елемент і список, що залишився:

1
[3, 7, 5, 9]

Тут, 1 є найменшим елементом з heap, а решта списку зберігає властивість купи навіть після видалення 1.

Як заштовхнути новий елемент і витягти найменший предмет

Команда heappushpop() функція — це комбінована операція, яка надсилає новий елемент у купу, а потім вириває та повертає найменший елемент із купи:

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

Це виведе 3, найменший елемент, і роздрукуйте новий heap список, який тепер включає 4 зберігаючи властивість купи:

3
[4, 5, 7, 9]

Як замінити найменший предмет і поставити новий

Команда heapreplace() функція витягує найменший елемент і виштовхує новий елемент у купу за одну ефективну операцію:

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

Це друкує 1, найменший елемент, і список тепер включає 4 і підтримує властивість купи:

1
[4, 5, 7, 9]

Пошук кількох екстремумів у купі Python

nlargest(n, iterable[, key]) та nsmallest(n, iterable[, key]) функції призначені для отримання кількох найбільших або найменших елементів із ітерованого. Вони можуть бути більш ефективними, ніж сортування всього ітерованого, коли вам потрібно лише кілька екстремальних значень. Наприклад, припустимо, що у вас є такий список і ви хочете знайти три найменших і три найбільших значення в списку:

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

Тут, nlargest() та nsmallest() функції можуть стати в нагоді:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

Це дасть вам два списки – один містить три найбільші значення, а інший містить три найменші значення з data список:

[9, 6, 5]
[1, 1, 2]

Як створити власну купу

Тоді як Python heapq Модуль надає надійний набір інструментів для роботи з купами, є сценарії, коли мінімальна поведінка купи за умовчанням може бути недостатньою. Незалежно від того, чи хочете ви реалізувати максимальну купу або вам потрібна купа, яка працює на основі спеціальних функцій порівняння, створення спеціальної купи може стати відповіддю. Давайте розберемося, як пристосувати купи до конкретних потреб.

Впровадження максимальної купи за допомогою heapq

За замовчуванням heapq створює хв купи. Однак за допомогою простого прийому ви можете використовувати його для реалізації максимальної купи. Ідея полягає в тому, щоб інвертувати порядок елементів, помноживши їх на -1 перш ніж додати їх до купи:

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

При такому підході найбільше число (за абсолютною величиною) стає найменшим, що дозволяє heapq функції для підтримки максимальної структури купи.

Купи з користувальницькими функціями порівняння

Іноді вам може знадобитися купа, яка не просто порівнює на основі природного порядку елементів. Наприклад, якщо ви працюєте зі складними об’єктами або маєте певні критерії сортування, необхідна настроювана функція порівняння.

Щоб досягти цього, ви можете обернути елементи в допоміжний клас, який перевизначає оператори порівняння:

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

За допомогою цього налаштування ви можете визначити будь-яку спеціальну функцію порівняння та використовувати її з купою.

Висновок

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

Купи, як ми з вами подорожували, це більше, ніж просто ще одна структура даних. Вони являють собою злиття ефективності, структури та адаптивності. Від основних властивостей до реалізації в Python heapq Модуль Heaps пропонує надійне рішення для безлічі обчислювальних проблем, особливо тих, що зосереджені навколо пріоритету.

• Розповсюдження контенту та PR на основі SEO. Отримайте посилення сьогодні.
• PlatoData.Network Vertical Generative Ai. Додайте собі сили. Доступ тут.
• PlatoAiStream. Web3 Intelligence. Розширення знань. Доступ тут.
• ПлатонЕСГ. вуглець, CleanTech, Енергія, Навколишнє середовище, Сонячна, Поводження з відходами. Доступ тут.
• PlatoHealth. Розвідка про біотехнології та клінічні випробування. Доступ тут.
• джерело: https://stackabuse.com/guide-to-heaps-in-python/