Keon tietorakenne: mikä on kasa? Min & Max Heap (esimerkki)

Mikä on kasa?

Keko on erikoistunut puutietorakenne. Kasa käsittää ylimmän solmun, jota kutsutaan juuriksi (emo). Sen toinen lapsi on juuren vasen lapsi, kun taas kolmas solmu on juuren oikea lapsi. Peräkkäiset solmut täytetään vasemmalta oikealle. Vanhemman solmun avainta verrataan sen jälkeläisiin, ja oikea järjestely tapahtuu. Puu on helppo visualisoida, missä kutakin entiteettiä kutsutaan solmuksi. Solmulla on yksilölliset avaimet tunnistamista varten.

Miksi tarvitset Keon tietorakennetta?

Tässä ovat tärkeimmät syyt Keon tietorakenteen käyttämiseen:

Keon tietorakenne mahdollistaa poistamisen ja lisäämisen logaritmisessa ajassa – O(log₂ei).
Puun tiedot on muotoiltu tietyssä järjestyksessä. Sen lisäksi, että ohjelmoija päivittää tai kyselee asioita, kuten maksimi tai minimi, hän voi löytää suhteita vanhemman ja jälkeläisen välillä.
Voit soveltaa käsitettä Asiakirjaobjektimalli auttaa sinua ymmärtämään keon tietorakennetta.

Kasojen tyypit

Keon tietorakenteessa on erilaisia algoritmeja lisäysten käsittelemiseen ja elementtien poistamiseen keon tietorakenteessa, mukaan lukien Priority-Queue, Binary-Heap, Binomial Heap ja Kasa-lajittelu.

Priority-jono: Se on abstrakti tietorakenne, joka sisältää prioriteettikohteita. Jokaiselle esineelle tai kohteelle on ennalta sovittu prioriteetti. Siksi kohde tai kohde, jolle on määritetty korkeampi prioriteetti, saa palvelun ennen muita.
Binäärikeko: Binäärikekot soveltuvat yksinkertaisiin kasatoimintoihin, kuten poistoihin ja lisäyksiin.
Binomi-keko: Binominen kasa koostuu sarjasta binomipuita, jotka muodostavat kasan. Binomiaalinen kasapuu ei ole tavallinen puu, koska se on tarkasti määritelty. Binomipuun elementtien kokonaismäärässä on aina 2ⁿ solmuja.
Keon lajittelu: Toisin kuin useimmat lajittelualgoritmit, kasalajittelu käyttää O(1)-tilaa lajitteluoperaatiossaan. Se on vertailuun perustuva lajittelualgoritmi, jossa lajittelu tapahtuu kasvavassa järjestyksessä muuttamalla se ensin maksimikasoksi. Voit tarkastella Heapsortia parannetun laadun binaarihakupuuna.

Tyypillisesti kasatietorakenne käyttää kahta strategiaa. Syöttöille 12 – 8 – 4 – 2 ja 1

Min Heap – vähiten arvo yläosassa
Max Heap – korkein arvo yläosassa

Min kasa

Min Heap -rakenteessa juurisolmun arvo on joko sama tai pienempi kuin kyseisen solmun lapsilla. Tällä Min-keon keon solmulla on vähimmäisarvo. Kaiken kaikkiaan sen min-keon rakenne on täydellinen binaaripuu.

Kun puussa on Min-kasa, kaikki lehdet ovat kelvollisia. Sinun on kuitenkin tutkittava jokainen lehti saadaksesi tarkan Max-keon arvon.

Minimikeon esimerkki

Yllä olevissa kaavioissa voit huomata selkeän sekvenssin juuresta alimpaan solmuun.

Oletetaan, että tallennat elementit taulukkoon Taulukko_N[12,2,8,1,4]. Kuten taulukosta näkyy, juurielementti rikkoo Min Heap -prioriteettia. Min-keon ominaisuuden ylläpitämiseksi sinun on suoritettava min-keapify-operaatiot elementtien vaihtamiseksi, kunnes Min-keon ominaisuudet täyttyvät.

Max Heap

Max Keon rakenteessa emo- tai juurisolmun arvo on yhtä suuri tai suurempi kuin sen alat solmussa. Tällä solmulla on enimmäisarvo. Lisäksi se on täydellinen binääripuu, joten voit rakentaa maksimikeon arvokokoelmasta ja suorittaa sen O(n) ajan.

Tässä on muutamia menetelmiä Java max -keon toteuttamiseen

Lisätä (): aseta uusi elementti kasaan. 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ällä menetelmällä voit poistaa ensimmäisen elementin taulukkoluettelosta. Koska juuri lisätty elementti ei ole enää suurin, Sift-Down -menetelmä työntää sen aina uuteen paikkaansa.
Sift-down (): Tämä menetelmä vertaa juuriobjektia sen aliobjektiin ja työntää sitten vasta lisätyn solmun sen oikeaan paikkaan.
Sift-up (): jos käytät taulukkomenetelmää äskettäin lisätyn elementin lisäämiseen taulukkoon, Sift-Up-menetelmä auttaa juuri lisättyä solmua siirtymään uuteen paikkaansa. Äskettäin lisättyä alkiota verrataan ensin emo-elementtiin simuloimalla puutietorakennetta.
Käytä kaavaa Parent_Index=Child_Index/2. Jatka tätä, kunnes suurin elementti on taulukon etuosassa.

Peruskasa OperaTIONS

Jotta voit löytää tietojoukon suurimmat ja pienimmät arvot, tarvitset monia peruskekotoimintoja, kuten etsi, poista ja lisää. Koska elementtejä tulee ja menee jatkuvasti, sinun on:

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

Luo kasoja

Kasojen rakentamisprosessi tunnetaan kasojen luomisena. Avainluettelon perusteella ohjelmoija tekee tyhjän kasan ja lisää sitten muita avaimia yksi kerrallaan käyttämällä peruskekotoimintoja.

Aloitetaan siis Min-keon rakentaminen Willaimin menetelmällä lisäämällä arvot 12,2,8,1 ja 4 kasaan. Voit rakentaa keon, jossa on n elementtiä aloittamalla tyhjästä kasasta ja täyttämällä sen sitten peräkkäin muilla elementeillä käyttämällä O (nlogn) -aikaa.

Keko: lisäysalgoritmissa, joka auttaa lisäämään elementtejä kasaan. Tarkistetaan, onko ominaisuuskeon tietorakenne korostettu, seurataan.
Esimerkiksi max heapify tarkistaisi, onko vanhemman arvo suurempi kuin sen jälkeläisen. Elementit voidaan sitten lajitella menetelmillä, kuten vaihtamalla.

Yhdistä: Koska sinulla on kaksi kasaa yhdistettäväksi yhdeksi, yhdistä kahden kasan arvot yhdistämiskasoilla. Alkuperäiset kasat ovat kuitenkin säilyneet.

Tarkista kasat

Kasojen tarkastaminen tarkoittaa keon tietorakenteen elementtien lukumäärän tarkistamista ja sen tarkistamista, onko kasa tyhjä.

On tärkeää tarkastaa kasoja elementtien lajitteluna tai jonotuksena. On tärkeää tarkistaa, onko sinulla prosessoitavia elementtejä Is-Empty():llä. Kasan koko auttaa paikantamaan maksimi- tai min-keon. Joten sinun on tiedettävä kason ominaisuutta seuraavat elementit.

Koko – palauttaa keon suuruuden tai pituuden. Voit kertoa kuinka monta elementtiä on järjestetty järjestykseen.
On tyhjä – jos kasa on NULL, se palauttaa TRUE, muuten se palauttaa EPÄTOSI.

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 tietorakenne on hyödyllinen monissa ohjelmointisovelluksissa tosielämässä, kuten:

Auttaa roskapostin suodatuksessa.
Graafialgoritmien toteuttaminen.
Operajärjestelmän kuormituksen tasapainotus ja tietojen pakkaus.
Etsi järjestys tilastoista.
Ota käyttöön Priority-jonot, joissa voit etsiä kohteita luettelosta logaritmisajassa.
Keon tietorakennetta käytetään myös lajitteluun.
Simuloi asiakkaita linjalla.
Keskeytä käsittely Operating System.
Huffmanin koodauksessa tietojen pakkaamiseen.

Keon prioriteettijonon ominaisuudet

Prioriteettikasoissa luettelon tietokohteita verrataan toisiinsa pienemmän elementin määrittämiseksi.
Elementti asetetaan jonoon ja poistetaan sen jälkeen.
Jokaisella prioriteettijonon elementillä on siihen liittyvä yksilöllinen numero, joka on tunnistettu prioriteetiksi.
Poistuessaan prioriteettijonosta ylimmän prioriteetin elementti poistuu ensin.

Kason prioriteettijonon käyttöönottovaiheet Java

Keon lajittelu JAVA:ssa koodiesimerkillä

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 the root and the largest element 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 koodiesimerkillä

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)