Przewodnik po stertach w Pythonie

Wprowadzenie

Wyobraź sobie tętniące życiem lotnisko, na którym co minutę startują i lądują samoloty. Podobnie jak kontrolerzy ruchu lotniczego ustalają priorytety lotów w oparciu o pilność, sterty pomagają nam zarządzać danymi i przetwarzać je w oparciu o określone kryteria, zapewniając, że najbardziej „pilne” lub „ważne” dane są zawsze dostępne na górze.

W tym przewodniku wyruszymy w podróż, aby zrozumieć stosy od podstaw. Zaczniemy od wyjaśnienia, czym są kopce i jakie są ich nieodłączne właściwości. Następnie zajmiemy się implementacją stert w Pythonie, czyli heapq modułu i poznaj jego bogaty zestaw funkcjonalności. Jeśli więc kiedykolwiek zastanawiałeś się, jak efektywnie zarządzać dynamicznym zestawem danych, w którym często potrzebny jest element o najwyższym (lub najniższym) priorytecie, czeka Cię prawdziwa przyjemność.

Co to jest sterta?

Pierwszą rzeczą, którą chciałbyś zrozumieć, zanim zagłębisz się w użycie stert, jest to co to jest kupa. Kopiec wyróżnia się w świecie struktur danych jako potęga oparta na drzewach, w której szczególnie specjalizuje się utrzymanie porządku i hierarchii. Choć dla niewprawnego oka może przypominać drzewo binarne, niuanse w jego strukturze i rządzących zasadach wyraźnie go wyróżniają.

Jedną z cech definiujących stertę jest jej natura pełne drzewo binarne. Oznacza to, że każdy poziom drzewa, z wyjątkiem być może ostatniego, jest całkowicie wypełniony. Na tym ostatnim poziomie węzły wypełniają się od lewej do prawej. Taka struktura zapewnia efektywne reprezentowanie stert i manipulowanie nimi za pomocą tablic lub list, przy czym pozycja każdego elementu w tablicy odzwierciedla jego położenie w drzewie.

Jednak prawdziwa istota sterty leży w jej zamawiania, W maksymalna sterta, wartość dowolnego węzła jest większa lub równa wartościom jego dzieci, umieszczając największy element bezpośrednio u korzenia. Z drugiej strony A min sterta działa na odwrotnej zasadzie: wartość dowolnego węzła jest mniejsza lub równa wartościom jego dzieci, zapewniając, że najmniejszy element znajduje się w korzeniu.

W miarę postępów będziemy zagłębiać się w to, jak te nieodłączne właściwości stert umożliwiają wydajne operacje i jak Python heapq Moduł bezproblemowo integruje sterty z naszymi wysiłkami związanymi z kodowaniem.

Charakterystyka i właściwości kopców

Sterty, dzięki swojej unikalnej strukturze i zasadom porządkowania, zapewniają zestaw odrębnych cech i właściwości, które czynią je nieocenionymi w różnych scenariuszach obliczeniowych.

Przede wszystkim są to stosy z natury skuteczny. Ich struktura oparta na drzewie, w szczególności pełny format drzewa binarnego, zapewnia, że ​​operacje takie jak wstawianie i wyodrębnianie elementów priorytetowych (maksimum lub minimum) mogą być wykonywane w czasie logarytmicznym, zwykle O (log n). Ta wydajność jest dobrodziejstwem dla algorytmów i aplikacji wymagających częstego dostępu do priorytetowych elementów.

Inną godną uwagi właściwością stert jest ich wydajność pamięci. Ponieważ sterty można reprezentować za pomocą tablic lub list bez potrzeby stosowania jawnych wskaźników do węzłów podrzędnych lub nadrzędnych, oszczędzają one miejsce. Pozycja każdego elementu w tablicy odpowiada jego położeniu w drzewie, co pozwala na przewidywalne i proste poruszanie się i manipulację.

Zapewnia to właściwość porządkowania stert, czy to jako sterty maksymalnej, czy minimalnej root zawsze przechowuje element o najwyższym priorytecie. To spójne uporządkowanie pozwala na szybki dostęp do najważniejszego elementu bez konieczności przeszukiwania całej konstrukcji.

Co więcej, jest mnóstwo wszechstronny. Podczas gdy najpowszechniejsze są kopce binarne (gdzie każdy z rodziców ma co najwyżej dwoje dzieci), można uogólnić, że kopce mają więcej niż dwoje dzieci, co jest tzw. kupy d-ary. Ta elastyczność pozwala na precyzyjne dostrojenie w oparciu o konkretne przypadki użycia i wymagania wydajnościowe.

Wreszcie jest mnóstwo samoregulujący. Za każdym razem, gdy elementy są dodawane lub usuwane, struktura zmienia się, aby zachować swoje właściwości. To dynamiczne równoważenie gwarantuje, że sterta będzie przez cały czas zoptymalizowana pod kątem swoich podstawowych operacji.

Gdy zagłębimy się w implementację Pythona i jego praktyczne zastosowania, prawdziwy potencjał stert ujawni się przed nami.

Rodzaje stosów

Nie wszystkie kopce są sobie równe. W zależności od ich uporządkowania i właściwości strukturalnych, hałdy można podzielić na różne typy, każdy z własnym zestawem zastosowań i zalet. Dwie główne kategorie to maksymalna sterta i min sterta.

Najbardziej charakterystyczną cechą A maksymalna sterta jest to, że wartość dowolnego węzła jest większa lub równa wartościom jego dzieci. Dzięki temu największy element sterty zawsze znajduje się w korzeniu. Taka struktura jest szczególnie użyteczna, gdy istnieje potrzeba częstego dostępu do maksymalnego elementu, jak w niektórych implementacjach kolejek priorytetowych.

Odpowiednik maksymalnej sterty, a min sterta zapewnia, że ​​wartość dowolnego węzła jest mniejsza lub równa wartościom jego dzieci. Spowoduje to umieszczenie najmniejszego elementu sterty w korzeniu. Minimalne sterty są nieocenione w scenariuszach, w których najważniejszy jest najmniejszy element, na przykład w algorytmach zajmujących się przetwarzaniem danych w czasie rzeczywistym.

Poza tymi podstawowymi kategoriami, kopce można również rozróżnić na podstawie ich współczynnika rozgałęzienia:

Chociaż najpowszechniejsze są kopce binarne, w których każdy rodzic ma co najwyżej dwoje dzieci, koncepcję stert można rozszerzyć na węzły mające więcej niż dwoje dzieci. W sterta d-ary, każdy węzeł ma co najwyżej d dzieci. Tę odmianę można zoptymalizować pod kątem określonych scenariuszy, takich jak zmniejszenie wysokości drzewa w celu przyspieszenia niektórych operacji.

Kupa dwumianowa to zbiór drzew dwumianowych zdefiniowanych rekurencyjnie. Sterty dwumianowe są używane w implementacjach kolejek priorytetowych i oferują wydajne operacje scalania.

Nazwany na cześć słynnego ciągu Fibonacciego Kupa Fibonacciego oferuje lepiej amortyzowane czasy wykonywania wielu operacji w porównaniu ze stertami binarnymi lub dwumianowymi. Są szczególnie przydatne w algorytmach optymalizacji sieci.

Implementacja sterty w Pythonie – The sterta Moduł

Python oferuje wbudowany moduł do operacji na stertach – heapq moduł. Moduł ten udostępnia zbiór funkcji związanych ze stertami, które umożliwiają programistom przekształcanie list w sterty i wykonywanie różnych operacji na stertach bez potrzeby niestandardowej implementacji. Zanurzmy się w niuanse tego modułu i w jaki sposób zapewnia on moc stosów.

Połączenia heapq moduł nie zapewnia odrębnego typu danych sterty. Zamiast tego oferuje funkcje, które działają na zwykłych listach Pythona, przekształcając je i traktując jako stosy binarne.

Takie podejście oszczędza pamięć i bezproblemowo integruje się z istniejącymi strukturami danych Pythona.

Oznacza to, że sterty są reprezentowane jako listy in heapq. Piękno tej reprezentacji polega na jej prostocie – system indeksowania list oparty na zerach służy jako ukryte drzewo binarne. Dla dowolnego elementu na pozycji i, jego:

• Lewe dziecko jest na pozycji 2*i + 1
• Prawe dziecko jest na swoim miejscu 2*i + 2
• Węzeł nadrzędny znajduje się na pozycji (i-1)//2

Ta niejawna struktura gwarantuje, że nie ma potrzeby tworzenia oddzielnej reprezentacji drzewa binarnego opartej na węzłach, dzięki czemu operacje są proste, a zużycie pamięci minimalne.

Należy pamiętać, że heapq moduł domyślnie tworzy minimalne sterty. Oznacza to, że najmniejszy element zawsze znajduje się w korzeniu (lub na pierwszej pozycji na liście). Jeśli potrzebujesz maksymalnej sterty, musisz odwrócić kolejność, mnożąc elementy przez -1 lub użyj niestandardowej funkcji porównania.

Pythona heapq moduł udostępnia zestaw funkcji umożliwiających programistom wykonywanie różnych operacji na stertach na listach.

W kolejnych sekcjach zagłębimy się w każdą z tych podstawowych operacji, badając ich mechanikę i przypadki użycia.

Jak przekształcić listę w stertę

Połączenia heapify() Funkcja jest punktem wyjścia dla wielu zadań związanych ze stertą. Pobiera iterowalną (zwykle listę) i przestawia jej elementy w miejscu, aby spełnić właściwości minimalnej sterty:

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

Spowoduje to wyświetlenie listy o zmienionej kolejności, która reprezentuje prawidłową min. stertę:

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

Jak dodać element do sterty

Połączenia heappush() funkcja umożliwia wstawienie nowego elementu do sterty przy zachowaniu właściwości sterty:

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

Uruchomienie kodu wyświetli listę elementów utrzymujących właściwość min heap:

[3, 5, 7]

Jak usunąć i zwrócić najmniejszy element ze sterty

Połączenia heappop() funkcja wyodrębnia i zwraca najmniejszy element ze sterty (korzeń w minimalnej stercie). Po usunięciu zapewnia, że ​​lista pozostanie prawidłową stertą:

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

Spowoduje to wyświetlenie najmniejszego elementu i pozostałej listy:

1
[3, 7, 5, 9]

Tutaj, 1 jest najmniejszym elementem z heap, a pozostała lista zachowała właściwość sterty, nawet po jej usunięciu 1.

Jak wypchnąć nowy przedmiot i wybić najmniejszy przedmiot

Połączenia heappushpop() funkcja to łączona operacja, która wypycha nowy element na stertę, a następnie wyskakuje i zwraca najmniejszy element ze sterty:

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

Spowoduje to wyjście 3, najmniejszy element i wydrukuj nowy heap lista, która obecnie obejmuje 4 zachowując właściwość sterty:

3
[4, 5, 7, 9]

Jak wymienić najmniejszy przedmiot i wcisnąć nowy przedmiot

Połączenia heapreplace() funkcja wyskakuje najmniejszy element i wypycha nowy element na stertę, a wszystko to w jednej wydajnej operacji:

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

To drukuje 1, najmniejszy element, a lista zawiera teraz 4 i zachowuje właściwość sterty:

1
[4, 5, 7, 9]

Znajdowanie wielu ekstremów na stercie Pythona

nlargest(n, iterable[, key]) i nsmallest(n, iterable[, key]) Funkcje służą do pobierania wielu największych lub najmniejszych elementów z obiektu iterowalnego. Mogą być bardziej wydajne niż sortowanie całej iteracji, gdy potrzebujesz tylko kilku wartości ekstremalnych. Załóżmy na przykład, że masz następującą listę i chcesz znaleźć na niej trzy najmniejsze i trzy największe wartości:

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

Tutaj, nlargest() i nsmallest() funkcje mogą się przydać:

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

Otrzymasz dwie listy – jedna zawiera trzy największe wartości, a druga zawiera trzy najmniejsze wartości z data lista:

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

Jak zbudować niestandardową stertę

Podczas gdy Python heapq moduł zapewnia solidny zestaw narzędzi do pracy ze stertami, istnieją scenariusze, w których domyślne zachowanie minimalnej sterty może nie wystarczyć. Niezależnie od tego, czy chcesz zaimplementować maksymalną stertę, czy potrzebujesz sterty działającej w oparciu o niestandardowe funkcje porównawcze, odpowiedzią może być zbudowanie niestandardowej sterty. Przyjrzyjmy się, jak dostosować sterty do konkretnych potrzeb.

Implementacja maksymalnej sterty przy użyciu heapq

Domyślnie heapq tworzy min. stosy. Jednak za pomocą prostej sztuczki możesz użyć jej do zaimplementowania maksymalnej sterty. Pomysł polega na odwróceniu kolejności elementów poprzez pomnożenie ich przez -1 przed dodaniem ich do sterty:

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]

Dzięki takiemu podejściu największa liczba (w wartości bezwzględnej) staje się najmniejszą, co pozwala heapq funkcje utrzymujące maksymalną strukturę sterty.

Sterty z niestandardowymi funkcjami porównawczymi

Czasami możesz potrzebować sterty, która nie tylko porównuje na podstawie naturalnej kolejności elementów. Na przykład, jeśli pracujesz ze złożonymi obiektami lub masz określone kryteria sortowania, niestandardowa funkcja porównania staje się niezbędna.

Aby to osiągnąć, możesz zawinąć elementy w klasę pomocniczą, która zastępuje operatory porównania:

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

Dzięki tej konfiguracji możesz zdefiniować dowolną niestandardową funkcję komparatora i używać jej ze stertą.

Wnioski

Sterty oferują przewidywalną wydajność dla wielu operacji, co czyni je niezawodnym wyborem w przypadku zadań opartych na priorytetach. Należy jednak wziąć pod uwagę specyficzne wymagania i charakterystykę danej aplikacji. W niektórych przypadkach modyfikacja implementacji sterty lub nawet wybranie alternatywnych struktur danych może zapewnić lepszą wydajność w świecie rzeczywistym.

Jak już się przekonaliśmy, sterty to coś więcej niż kolejna struktura danych. Reprezentują połączenie wydajności, struktury i zdolności adaptacyjnych. Od ich podstawowych właściwości po implementację w Pythonie heapq moduł, sterty oferują solidne rozwiązanie niezliczonych wyzwań obliczeniowych, zwłaszcza tych skupionych wokół priorytetów.

• Dystrybucja treści i PR oparta na SEO. Uzyskaj wzmocnienie już dziś.
• PlatoData.Network Pionowe generatywne AI. Wzmocnij się. Dostęp tutaj.
• PlatoAiStream. Inteligencja Web3. Wiedza wzmocniona. Dostęp tutaj.
• PlatonESG. Węgiel Czysta technologia, Energia, Środowisko, Słoneczny, Gospodarowanie odpadami. Dostęp tutaj.
• Platon Zdrowie. Inteligencja w zakresie biotechnologii i badań klinicznych. Dostęp tutaj.
• Źródło: https://stackabuse.com/guide-to-heaps-in-python/