Struktura podataka Heap: Što je Heap?

Što je struktura podataka Heap?

Heap je specijalizirana struktura podataka temeljena na stablu. Struktura podataka Heap sastoji se od najvišeg čvora koji se naziva korijen (roditelj). Njegov drugi čvor je lijevo dijete korijena, dok je treći čvor desno dijete korijena. Sljedeći čvorovi popunjavaju se slijeva nadesno. Ključ roditeljskog čvora uspoređuje se s ključem njegovog potomka tako da se postiže pravilan raspored. Stablo je lako vizualizirati gdje se svaki entitet naziva čvorom, a svaki čvor ima jedinstveni ključ za identifikaciju.

Jednostavno rečeno, Heap je potpuno binarno stablo koje zadovoljava svojstvo heapa: svaki roditelj je konzistentno uređen u odnosu na svoju djecu, što ga čini idealnim za redove prioriteta i Heap sortiranje.

Zašto vam je potrebna Heap Data Structure?

Evo glavnih razloga za korištenje Heap-a:

• Struktura podataka Heap omogućuje brisanje i umetanje u logaritamskom vremenu – O(log₂ne).
• Podaci u stablu su poredani određenim redoslijedom. Osim ažuriranja ili ispitivanja vrijednosti poput maksimuma ili minimuma, programer može pronaći odnose između roditelja i potomka.
• Možete primijeniti koncept Model objekta dokumenta kako bismo vam pomogli vizualno razumjeti strukturu podataka Heap.
• Heaps podržavaju učinkovite operacije s prioritetnim redovima, koje su ključne za grafovske algoritme poput Dijkstrinog najkraćeg puta i Primovog minimalnog razapinjućeg stabla.

Vrste gomila

Struktura podataka Heap ima različite algoritme za rukovanje umetanjem i uklanjanjem elemenata, uključujući red prioriteta, binarni heap, binomni heap i Sortiranje po hrpi.

• Red prioriteta: To su trbušnjacitract struktura podataka koja sadrži objekte s prioritetom. Svaki objekt ili stavka ima unaprijed određen prioritet. Stoga objekt ili stavka kojoj je dodijeljen viši prioritet dobiva uslugu prije ostalih.
• Binarna hrpa: Binarni heapovi su prikladni za jednostavne operacije s heapovima poput brisanja i umetanja. Oni su zadana implementacija iza većine standardnih redova prioriteta biblioteka.
• Binomna hrpa: Binomni hrpa sastoji se od niza kolekcija binomnih stabala koja čine hrpu. Binomno hrpasto stablo nije obično stablo jer je rigorozno definirano. Ukupan broj elemenata u binomnom stablu uvijek je jednak 2.ⁿ čvorovi.
• Sortiranje hrpe: Za razliku od većine algoritama za sortiranje, Heap Sort koristi O(1) prostora za svoju operaciju sortiranja. To je algoritam sortiranja temeljen na usporedbi gdje se sortiranje odvija u rastućem redoslijedu tako da se prvo ulaz pretvori u Max-Heap. Heap Sort možete promatrati kao nadograđeno binarno stablo pretraživanja.

Tipično, struktura podataka tipa Heap koristi dvije strategije. Za ulaz 12 – 8 – 4 – 2 i 1:

• Min-Heap – najmanja vrijednost na vrhu
• Max-Heap – najviša vrijednost na vrhu

Min-Heap

U Min-Heap strukturi, korijenski čvor ima vrijednost jednaku ili manju od djece tog čvora. Korijen Min-Heapa stoga sadrži minimalnu vrijednost. Min-Heap je također potpuno binarno stablo.

Nakon što imate Min-Heap u stablu, svi listovi su održivi kandidati za maksimalnu vrijednost. Međutim, morate ispitati svaki list kako biste dobili točnu vrijednost Max-Heap.

Primjer Min-Heap-a

Na gornjem dijagramu možete primijetiti jasan slijed od korijena do najnižeg čvora.

Pretpostavimo da elemente pohranjujete u niz Array_N[12, 2, 8, 1, 4]. Kao što možete vidjeti iz niza, korijenski element krši prioritet Min-Heap. Da biste održali svojstvo Min-Heap, morate izvršiti operacije min-heapify kako biste zamijenili elemente dok se ne zadovolje pravila Min-Heap.

Max-Heap

U strukturi Max-Heap, roditeljski ili korijenski čvor ima vrijednost jednaku ili veću od svojih potomaka. Ovaj čvor sadrži maksimalnu vrijednost. To je potpuno binarno stablo, tako da možete izgraditi Max-Heap iz kolekcije vrijednosti u vremenu O(n).

Evo nekoliko metoda koje se obično koriste prilikom implementacije Java Max-Heap:

• Dodaj (): Smješta novi element u hrpu. Ako koristite niz, objekti se dodaju na kraj niza, dok se u binarnom stablu objekti dodaju od vrha prema dnu, a zatim s lijeva na desno.
• Ukloni (): Ova metoda vam omogućuje uklanjanje prvog elementa s popisa nizova. Budući da novo promovirani element više nije najveći, metoda Sift-Down uvijek ga pomiče na novu lokaciju.
• Prosijavanje (): Ova metoda uspoređuje korijenski objekt s njegovom djecom, a zatim premještani čvor pomiče na njegovu pravu poziciju.
• Prosijavanje (): Ako koristite metodu polja za dodavanje novo umetnutog elementa u polje, tada metoda Sift-Up pomaže novo dodanom čvoru da se premjesti na ispravnu poziciju. Novi element se prvo uspoređuje sa svojim roditeljem simulirajući strukturu podataka stabla.

  Primijenite formulu Roditeljski_indeks = Podređeni_indeks / 2. Nastavite to raditi sve dok maksimalni element ne bude na početku polja.

Osnovna gomila Operama

Da biste pronašli najviše i najniže vrijednosti u skupu podataka, potrebno vam je nekoliko osnovnih operacija na hrpi kao što su pronalaženje, umetanje i brisanje. Budući da elementi stalno dolaze i odlaze, trebali biste znati kako:

• naći – Potražite predmet na hrpi.
• umetak – Dodajte novo dijete u hrpu.
• Izbrisati – Brisanje čvora iz gomile.

Stvorite gomile

Proces konstruiranja hrpa poznat je kao stvaranje hrpa. S obzirom na popis ključeva, programer stvara praznu hrpu, a zatim ubacuje ostale ključeve jedan po jedan koristeći osnovne operacije s hrpom.

Dakle, započnimo s izgradnjom Min-Heapa koristeći Williamovu metodu umetanjem vrijednosti 12, 2, 8, 1 i 4. Heap možete izgraditi s n elemenata tako da započnete s praznim heapom, a zatim ga sukcesivno popunite drugim elementima koristeći vrijeme O(n log n).

• Heapify: Rutina za umetanje koja pomaže u umetanju elemenata u hrpu (heap) uz očuvanje svojstva hrpe.

  Na primjer, operacija max-heapify provjerava je li vrijednost roditelja veća od vrijednosti njegovog potomka. Elementi se zatim mogu sortirati metodama poput swapping.

• Sjediniti: Kada imate dvije hrpe koje želite spojiti u jednu, upotrijebite operaciju spajanja kako biste spojili vrijednosti iz dvije hrpe. Izvorne hrpe ostaju sačuvane.

Pregledajte gomile

Inspekcija hrpa odnosi se na provjeru broja elemenata u strukturi podataka hrpe i provjeru je li hrpa prazna.

Važno je pregledati hrpe prilikom sortiranja ili stavljanja elemenata u red čekanja. Važno je provjeriti postoje li elementi za obradu pomoću Is-Empty(). Veličina hrpe pomoći će u lociranju korijena Max-Heap ili Min-Heap, stoga morate znati koliko elemenata slijedi svojstvo hrpe.

• Veličina – vraća veličinu ili duljinu hrpe. Pokazuje koliko je elemenata pohranjeno sortiranim redoslijedom.
• Je prazno – vraća TRUE ako je heap null, inače vraća FALSE.

Ovdje ispisujete sve elemente u prioritetQ petlja i zatim provjera da priorityQ nije prazan.

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

Upotreba strukture podataka hrpe

Struktura podataka Heap korisna je u mnogim programskim primjenama u stvarnom životu, kao što su:

• Pomaže u filtriranju neželjene pošte.
• Implementacija grafovskih algoritama kao što su Dijkstra i Prim.
• Operauravnoteženje opterećenja sustava i kompresija podataka.
• Pronalaženje statistika reda kao što je k-ti najmanji element.
• Implementacija redova prioriteta gdje možete pretraživati ​​stavke na popisu u logaritamskom vremenu.
• Struktura podataka heap se također koristi za sortiranje putem heap sortiranja.
• Simuliranje kupaca u redu čekanja.
• Obrada prekida u Operating sustav.
• U Huffmanovom kodiranju za kompresiju podataka.
• Osnaživanje pretraživanja po principu "najbolje prvo" i A* heuristike u planiranju puta umjetne inteligencije.

Svojstva reda čekanja prioriteta hrpe

Sljedeća svojstva opisuju kako se ponaša red prioriteta izgrađen na hrpi:

• U prioritetnim hrpama, podatkovne stavke na popisu uspoređuju se jedna s drugom kako bi se odredio manji ili veći element.
• Element se stavlja u red čekanja, a zatim uklanja prema prioritetnom redoslijedu.
• Svaki element u redu prioriteta ima jedinstveni broj koji se odnosi na njega i identificiran je kao prioritet.
• Prilikom izlaska iz reda prioriteta, element s najvišim prioritetom izlazi prvi.

Koraci za implementaciju reda prioriteta gomile u Java

Sljedeći dio prelazi u beton Java implementacija koja ta pravila pretvara u funkcionalni kod.

Hrpa Sortiraj u Java sa Code Primjer

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);
        }
    }
}

Izlaz

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

Hrpa Sortiraj u Python sa Code Primjer

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)

Izlaz

[1, 3, 4, 7, 9]

Zatim ćete saznati više o Metoda bisekcije.

Pitanja i odgovori