Úvod do triedenia haldy v Pythone

Ktorýkoľvek z programovacích jazykov poskytuje rôzne funkcie na základe preddefinovaných funkcií. Využitím preddefinovaných metód a funkcií ponúkaných programovacím jazykom je možné vyvinúť komplexnú aplikáciu. Keď hovoríme o transformácii hodnôt zoznamu do zoradenej formy, prístup sa nazýva triedenie. Aj keď je výstup triedenia rovnaký bez ohľadu na prístup triedenia, najlepší prístup zaisťuje účinnosť triediacich údajov. Pokiaľ ide o triedenie pomocou programovacieho jazyka python, máme metódu sort (), ktorá dokáže hodnotu jednoducho prijať a zoradiť vzostupne. V tomto článku sa naučíme, ako zoradiť údaje z poľa vo vzostupnom poradí pomocou triedenia haldy a pomocou programovacieho jazyka python vykonať kódovú implementáciu haldy.

Ako funguje triedenie haldy v Pythone?

  • Pred vysvetlením fungovania Pythonu je dôležité porozumieť tomu, čo v skutočnosti je a ako sa líši od iných triediacich algoritmov. Heapsort možno považovať za prístup k triedeniu, pri ktorom sa maximálna hodnota zo zoznamu zaznamená a posunie na poslednú z polí a proces sa opakuje, kým sa zoznam nepremení na triedený zoznam. spôsob, ktorým sa odlišuje od ostatných metód triedenia, nie je nič iné ako len postup, ktorý sleduje, aby zoradil všetky hodnoty poľa. Pozostáva z rekurzívneho procesu, ktorý trvá, kým hodnoty v poli nie sú usporiadané vzostupne.
  • Teraz pomocou príkladu pochopíme, ako funguje triedenie haldy. Predpokladajme, že arr je pole, ktoré drží hodnoty ako 9, 5, 2. Na začiatku nie sú hodnoty poľa usporiadané usporiadaným spôsobom, ale po vykonaní triedenia haldy sa zmení na vzostupné. Keď sa na toto pole použije algoritmus triedenia haldy, bude to prvá vec, ktorá nájde našu najväčšiu hodnotu v poli. Pretože 9 je najväčšia hodnota, presunie sa do posledného indexu zoznamu a všetky ostatné hodnoty sa posunú o jeden krok doľava, aby sa vytvoril priestor na zadržanie najväčšej hodnoty. Akonáhle sa 9 posunie na posledný index alebo pole, zoznam hodnôt bude vyzerať ako 5, 2, 9.
  • Teraz pole stále nie je usporiadané, čo naznačuje, že ten istý proces sa musí opakovať znova. Teraz, keď sa nájde najväčšia hodnota zo zoznamu nespracovaných hodnôt, 5 sa vyberie ako druhá najväčšia hodnota a presunie sa do druhého posledného indexu. Po posunutí 5 v druhej poslednej polohe sa pole zmení na zoradené pole a hodnoty sa usporiadajú v zostave vzostupne ako 2, 5, 9. Takto funguje triedenie haldy. V skutočnosti to identifikuje maximálnu hodnotu a presúva ju na koniec poľa a pokračuje vo vykonávaní rovnakého procesu, kým sa pole nezmení na zoradené pole.

Príklady implementácie triedenia haldy v Pythone

Aby sme sa naučili koncepciu haldy, pochopme ju pomocou skutočného príkladu. Implementujeme algoritmus triedenia haldy pomocou jazyka python. Na vývoj programu použijeme slučku for, aby priniesla rekurzný mechanizmus, a na overenie podmienok použijeme kontrolu podmienok. V nižšie uvedenom kóde je funkcia perform_heapsort funkciou, ktorá prijíma tri argumenty: val_arr, num a count, kde var_arr je pole, zatiaľ čo num a count sú celočíselného typu údajov. Myšlienka nižšie uvedeného kódu je nájsť najväčšie číslo a dočasne ho držať v premennej max_val, kým sa nedostane na koniec poľa. Ak sa použil príkaz na zabezpečenie toho, aby sa najväčšia hodnota dostávala na príslušné miesto a že táto pozícia je blokovaná v aktualizácii najbližšou najväčšou hodnotou v zozname. Program zopakuje prístup k nájdeniu najväčšej hodnoty a jej posunutím na koniec, kým zoznam nenaladí zoradenú hodnotu.

kód:

def perform_heapsort(val_arr, num, count):
max_val = count
counter1 = 2 * count + 1
counter2 = 2 * count + 2
if counter1 < num and val_arr(count) < val_arr(counter1):
max_val = counter1
if counter2 < num and val_arr(max_val) < val_arr(counter2):
max_val = counter2
if max_val != count:
val_arr(count), val_arr(max_val) = val_arr(max_val), val_arr(count) perform_heapsort(val_arr, num, max_val)
def heapSort(val_arr):
num = len(val_arr)
for count in range(num, -1, -1):
perform_heapsort(val_arr, num, count)
for count in range(num-1, 0, -1):
val_arr(count), val_arr(0) = val_arr(0), val_arr(count) # swap
perform_heapsort(val_arr, count, 0)
val_arr = ( 52, 91, 64, 252, 36, 91, 5, 35, 28) heapSort(val_arr)
num = len(val_arr)
print ("Values after performing heapsort")
for count in range(num):
print ("%d" %val_arr(count)),

V tomto programe boli hodnoty priradené manuálne pomocou kódu. Var_arr je pole, ktoré uchováva hodnoty. V tomto príklade sme k poli priradili 9 hodnôt. Hodnoty v poli sa odovzdajú metóde s názvom perform_heapsort. Akonáhle hodnoty vstúpia do metódy, bude spracovaná a program začne vyhľadávať najväčšiu hodnotu zo zoznamu. Maximálna hodnota v tomto poli je 252, takže sa posunie na koniec poľa a tento proces sa bude uplatňovať na všetky hodnoty, kým sa pole nezmení na zoradené pole. Keď je pole zoradené podľa programu, výstup sa zobrazí na výstupe.

Výkon:

záver

Heapsort je jedným z rôznych triediacich algoritmov. Prípadným výstupom tohto algoritmu je triedený zoznam, ktorý má dáta usporiadané vzostupne. Pretože sa proces opakuje a zakaždým, keď sa všetky hodnoty posunú doľava, aby sa upravila maximálna hodnota zoznamu na konci poľa, považuje sa to za menej efektívny algoritmus triedenia. Tento prístup k triedeniu môže byť využitý v aplikácii, ktorá má spracovať malý počet hodnôt.

Odporúčané články

Toto je príručka pre triedenie haldy v Pythone. Tu diskutujeme úvod do triedenia haldy v Pythone, Ako funguje triedenie haldy v Pythone a príklady na implementáciu triedenia haldy v Pythone. Viac informácií nájdete aj v ďalších navrhovaných článkoch.

  1. Čo je to informatika?
  2. Čo je to strojové učenie?
  3. Zabezpečenie webových aplikácií
  4. Funkcie Pythonu
  5. Sprievodca triedením algoritmov v Pythone

Kategórie:

Vývoj softvéru