Keon tietorakenne: Mikä on keko?

Mikä on kekotietorakenne?

Keko on erikoistunut puupohjainen tietorakenne. Keon tietorakenne käsittää ylimmän solmun, jota kutsutaan juureksi (vanhemmaksi). Sen toinen solmu on juuren vasen lapsi, kun taas kolmas solmu on juuren oikea lapsi. Peräkkäiset solmut täytetään vasemmalta oikealle. Vanhemman solmun avain vertautuu jälkeläisensä avainta, jotta syntyy oikea järjestys. Puu on helppo visualisoida, jossa kutakin yksikköä kutsutaan solmuksi ja jokaisella solmulla on yksilöllinen avain tunnistamista varten.

Yksinkertaisesti sanottuna keko on täydellinen binääripuu, joka täyttää keko-ominaisuuden: jokainen vanhempi on järjestetty johdonmukaisesti lastensa suhteen, mikä tekee siitä ihanteellisen prioriteettijonoihin ja kekolajitteluun.

Miksi tarvitset Keon tietorakennetta?

Tässä ovat tärkeimmät syyt Heapin käyttöön:

• Keon tietorakenne mahdollistaa poiston ja lisäyksen logaritmisessa ajassa – O(log₂ei).
• Puun tiedot on järjestetty tiettyyn järjestykseen. Arvojen, kuten maksimin tai minimin, päivittämisen tai kyselyn lisäksi ohjelmoija voi löytää suhteita vanhemman ja jälkeläisen välillä.
• Voit soveltaa käsitettä Asiakirjaobjektimalli auttaakseen sinua ymmärtämään keon tietorakennetta visuaalisesti.
• Keot tukevat tehokkaita prioriteettijonojen toimintoja, jotka ovat kriittisiä graafialgoritmeille, kuten Dijkstran lyhin polku ja Primin pienin virittävä puu.

Kasojen tyypit

Keon tietorakenteessa on useita algoritmeja elementtien lisäysten käsittelyyn ja poistamiseen, mukaan lukien prioriteettijono, binaarikeo, binomikeo ja Keon lajittelu.

• Prioriteettijono: Se on vatsalihastract-tietorakenne, joka sisältää priorisoituja objekteja. Jokaisella objektilla tai alkiolla on ennalta määrätty prioriteetti. Siksi korkeamman prioriteetin saanut objekti tai alkio saa palvelun ennen muita.
• Binäärikeo: Binäärikeot soveltuvat yksinkertaisiin kekotoimintoihin, kuten poistoihin ja lisäyksiin. Ne ovat oletusarvoinen toteutus useimpien standardikirjastojen prioriteettijonojen takana.
• Binomikerä: Binomikeko koostuu sarjasta kokoelmia binomipuita, jotka muodostavat keon. Binomikekopuu ei ole tavallinen puu, koska se on tarkasti määritelty. Binomipuun elementtien kokonaismäärä on aina 2.ⁿ solmuja.
• Keon lajittelu: Toisin kuin useimmat lajittelualgoritmit, Heap Sort käyttää lajitteluoperaatiossaan O(1)-avaruutta. Se on vertailuun perustuva lajittelualgoritmi, jossa lajittelu tapahtuu nousevassa järjestyksessä muuttamalla syöte ensin Max-Heap-keoksi. Voit tarkastella Heap Sortia päivitettynä binäärisenä hakupuuna.

Keon tietorakenteessa käytetään tyypillisesti kahta strategiaa. Syötteille 12 – 8 – 4 – 2 ja 1:

• Min-Heap – pienin arvo ylhäällä
• Max-Heap – korkein arvo ylhäällä

Min-Heap

Min-Heap-rakenteessa juurisolmun arvo on joko yhtä suuri tai pienempi kuin kyseisen solmun lapsisolmuilla. Min-Heapin juuri sisältää siis pienimmän arvon. Min-Heap on myös täydellinen binääripuu.

Kun puussa on Min-Heap, kaikki lehdet ovat sopivia ehdokkaita maksimiarvon saamiseksi. Sinun on kuitenkin tutkittava jokainen lehti erikseen saadaksesi tarkan Max-Heap-arvon.

Min-keon esimerkki

Yllä olevassa kaaviossa voit huomata selkeän järjestyksen juuresta alimpaan solmuun.

Oletetaan, että tallennat elementit taulukkoon Array_N[12, 2, 8, 1, 4]. Kuten taulukosta näkyy, juurielementti rikkoo Min-Heap-prioriteettia. Min-Heap-ominaisuuden ylläpitämiseksi sinun on suoritettava min-heapify-operaatioita elementtien vaihtamiseksi, kunnes Min-Heap-säännöt täyttyvät.

Max-Heap

Max-Heap-rakenteessa pääsolmun arvo on yhtä suuri tai suurempi kuin sen lapsisolmun. Tämä solmu sisältää suurimman arvon. Se on täydellinen binääripuu, joten voit rakentaa Max-Heapin joukosta arvoja O(n) ajassa.

Tässä on muutamia yleisesti käytettyjä menetelmiä toteutuksessa Java Max-keko:

• Lisää (): Sijoittaa uuden elementin kekoon. Jos käytät taulukkoa, objektit lisätään taulukon loppuun, kun taas binääripuussa objektit lisätään ylhäältä alas ja sitten vasemmalta oikealle.
• Poista (): Tämän metodin avulla voit poistaa ensimmäisen alkion taulukkoluettelosta. Koska äskettäin ylennetty alkio ei ole enää suurin, Sift-Down-metodi siirtää sen aina uuteen sijaintiinsa.
• Seulonta (): Tämä metodi vertaa juuriobjektia sen lapsiin ja siirtää sitten uudelleensijoitetun solmun oikeaan paikkaan.
• Seulonta (): Jos käytät taulukkometodia lisätäksesi uuden alkion taulukkoon, Sift-Up-metodi auttaa uutta solmua siirtymään oikeaan paikkaan. Uutta alkiota verrataan ensin vanhempaan solmuun simuloimalla puutietorakennetta.

  Käytä kaavaa Parent_Index = Child_Index / 2. Jatka tätä, kunnes suurin alkio on taulukon alussa.

Peruskasa OperaTIONS

Jotta löydät tietojoukon suurimmat ja pienimmät arvot, tarvitset muutamia peruskeon operaatioita, kuten etsinnän, lisäämisen ja poistamisen. Koska alkioita tulee ja menee jatkuvasti, sinun tulisi tietää miten:

• Löytää – Etsi tavaraa kasasta.
• liite – Lisää uusi lapsi kasaan.
• Poista – Poista solmu kasasta.

Luo kasoja

Keojen rakentamisprosessia kutsutaan kekojen luomiseksi. Saatuaan listan avaimia ohjelmoija luo tyhjän keon ja lisää sitten muut avaimet yksi kerrallaan käyttämällä peruskeon toimintoja.

Aloitetaan siis Min-keon rakentaminen Williamin menetelmällä lisäämällä arvot 12, 2, 8, 1 ja 4. Voit rakentaa n-alkion keon aloittamalla tyhjästä keosta ja täyttämällä sen sitten peräkkäin muilla elementeillä käyttäen O(n log n) aikaa.

• Heapify: Lisäysrutiini, joka auttaa lisäämään elementtejä kekoon säilyttäen samalla keon ominaisuuden.

  Esimerkiksi max-heapify-operaatio tarkistaa, että vanhemman arvo on suurempi kuin sen jälkeläisen arvo. Elementit voidaan sitten lajitella käyttämällä menetelmiä, kuten swapping.

• Yhdistää: Kun sinulla on yhdistettävänä kaksi kekoa, käytä yhdistämisoperaatiota yhdistääksesi kahden keon arvot. Alkuperäiset keot säilyvät edelleen.

Tarkista kasat

Keojen tarkastaminen tarkoittaa keon tietorakenteen elementtien lukumäärän tarkistamista ja sen varmistamista, että keko on tyhjä.

Keojen tarkastaminen on tärkeää elementtien lajittelun tai jonotuksen aikana. On tärkeää tarkistaa Is-Empty()-funktiolla, että käsiteltäviä elementtejä on olemassa. Keon koko auttaa paikantamaan Max-Heap- tai Min-Heap-juuret, joten sinun on tiedettävä, kuinka monta elementtiä heap-ominaisuuden jälkeen on.

• Koko – palauttaa keon koon tai pituuden. Se kertoo, kuinka monta elementtiä on tallennettu lajitellussa järjestyksessä.
• On tyhjä – palauttaa arvon TRUE, jos keko on null, muuten palauttaa arvon FALSE.

Tässä tulostat kaikki elementit prioriteettiQ silmukan ja tarkista sitten, että prioriteettiQ ei ole tyhjä.

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

Keon tietorakenteen käyttötarkoitukset

Keon tietorakenteesta on hyötyä monissa ohjelmointisovelluksissa tosielämässä, kuten:

• Auttaa roskapostin suodatuksessa.
• Graafialgoritmien, kuten Dijkstran ja Primin, toteuttaminen.
• Operajärjestelmän kuormituksen tasapainottaminen ja datan pakkaaminen.
• Järjestystilastojen, kuten k:nneksi pienimmän elementin, löytäminen.
• Prioriteettijonojen toteuttaminen, joissa voit hakea listan kohteita logaritmisessa ajassa.
• Keon tietorakennetta käytetään myös lajitteluun keon lajittelun avulla.
• Asiakkaiden simulointi jonossa.
• Keskeytysten käsittely Operating System.
• Huffman-koodauksessa datan pakkaamiseen.
• Paras ensin -haun ja A*-heuristiikkojen tehostaminen tekoälypolkujen suunnittelussa.

Keon prioriteettijonon ominaisuudet

Seuraavat ominaisuudet kuvaavat, miten keolle rakennettu prioriteettijono käyttäytyy:

• Prioriteettikeoissa listan tietoja verrataan toisiinsa pienemmän tai suuremman alkion määrittämiseksi.
• Elementti asetetaan jonoon ja poistetaan sitten prioriteettijärjestyksessä.
• Jokaisella prioriteettijonon elementillä on siihen liittyvä yksilöllinen numero, joka on tunnistettu prioriteetiksi.
• Prioriteettijonosta poistuttaessa korkeimman prioriteetin omaava elementti poistuu ensin.

Keon prioriteettijonon toteuttamisen vaiheet Java

Seuraava osa siirtyy betoniin Java toteutus, joka muuttaa nämä säännöt toimivaksi koodiksi.

Kasa Lajittele Java Code esimerkki

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

ulostulo

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

Kasa Lajittele Python Code esimerkki

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)

ulostulo

[1, 3, 4, 7, 9]

Seuraavaksi opit lisää mm. Bisektiomenetelmä.

UKK