Struktura podataka hrpe: Što je hrpa? Min. i maks. hrpa (primjer)

Što je Heap?

Heap je specijalizirana struktura podataka stabla. Hrpa se sastoji od najvišeg čvora koji se naziva korijen (roditelj). Njegovo drugo dijete je lijevo dijete korijena, dok je treći čvor desno dijete korijena. Uzastopni čvorovi popunjavaju se s lijeva na desno. Ključ nadređenog čvora uspoređuje se s ključem njegovog potomka i dolazi do odgovarajućeg rasporeda. Stablo je lako vizualizirati gdje se svaki entitet naziva čvor. Čvor ima jedinstvene ključeve za identifikaciju.

Zašto vam je potrebna Heap Data Structure?

Evo glavnih razloga za korištenje Heap Data Structure:

Struktura podataka hrpe omogućuje brisanje i umetanje u logaritamskom vremenu – O(log₂ne).
Podaci u stablu oblikovani su određenim redoslijedom. Osim ažuriranja ili postavljanja upita o stvarima kao što su maksimum ili minimum, programer može pronaći odnose između roditelja i potomaka.
Možete primijeniti koncept Model objekta dokumenta da vam pomogne u razumijevanju strukture podataka hrpe.

Vrste gomila

Struktura podataka gomile ima različite algoritme za rukovanje umetanjima i uklanjanjem elemenata u strukturi podataka gomile, uključujući red čekanja prioriteta, binarnu gomilu, binomnu gomilu i Heap-Sort.

Prioritet-red: To je apstraktna struktura podataka koja sadrži prioritetne objekte. 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: Binarne gomile su prikladne za jednostavne operacije gomile kao što su brisanja i umetanja.
Binomna gomila: Binomna hrpa sastoji se od niza kolekcija binomnih stabala koja čine hrpu. Binomno Heap stablo nije obično stablo jer je strogo definirano. Ukupan broj elemenata u binomnom stablu uvijek ima 2ⁿ čvorovi.
Sortiranje gomile: Za razliku od većine algoritama sortiranja, heap-sort koristi O(1) prostor za svoju operaciju sortiranja. To je algoritam za sortiranje temeljen na usporedbi gdje se sortiranje odvija rastućim redoslijedom tako da se prvo pretvori u najveću hrpu. Na Heapsort možete gledati kao na nadograđeno kvalitetno stablo binarnog pretraživanja.

Tipično, struktura podataka gomile koristi dvije strategije. Za unos 12 – 8 – 4 – 2 i 1

Min Heap – najmanja vrijednost na vrhu
Max Heap – najveća vrijednost na vrhu

Min. gomila

U strukturi Min Heap, korijenski čvor ima vrijednost jednaku ili manju od djece na tom čvoru. Ovaj čvor hrpe minimalne hrpe ima minimalnu vrijednost. Sve u svemu, njegova min-heap struktura je potpuna binarno stablo.

Nakon što imate Min heap u stablu, svi listovi su održivi kandidati. Međutim, trebate ispitati svaki od listova kako biste dobili točnu vrijednost Max-heap.

Primjer minimalne hrpe

Na gornjim dijagramima možete primijetiti jasan slijed od korijena do najnižeg čvora.

Pretpostavimo da pohranjujete elemente u Array Array_N[12,2,8,1,4]. Kao što možete vidjeti iz niza, root element krši prioritet Min Heap. Da biste održali svojstvo Min heap, morate izvršiti operacije min-heapify da zamijenite elemente dok se ne ispune svojstva Min heap.

Max Heap

U Max Heap strukturi, nadređeni ili korijenski čvor ima vrijednost jednaku ili veću od svoje djece u čvoru. Ovaj čvor sadrži najveću vrijednost. Štoviše, to je potpuno binarno stablo, tako da možete izgraditi maksimalnu hrpu iz kolekcije vrijednosti i pokrenuti je na O(n) vremena.

Evo nekoliko metoda za implementaciju java max hrpe

Dodati (): smjestiti novi element u gomilu. Ako koristite niz, objekti se dodaju na kraj niza, dok se u binarnom stablu objekti dodaju odozgo prema dolje, a zatim slijeva nadesno.
Ukloni (): Ova metoda vam omogućuje da uklonite prvi element s popisa polja. Budući da novododani element više nije najveći, metoda Sift-Down uvijek ga gura na novu lokaciju.
Sift-Down (): Ova metoda uspoređuje korijenski objekt s njegovim potomkom i zatim gura novododani čvor na njegov pravi položaj.
Sift-Up (): ako koristite metodu niza za dodavanje novoumetnutog elementa u niz, tada metoda Sift-Up pomaže novododanom čvoru da se premjesti na svoju novu poziciju. Novo umetnuta stavka prvo se uspoređuje s nadređenom simulacijom podatkovne strukture stabla.
Primijenite formulu Parent_Index=Child_Index/2. To nastavljate raditi sve dok najveći element ne bude na početku niza.

Osnovna gomila Operama

Da biste pronašli najveće i najniže vrijednosti u skupu podataka, potrebno vam je mnogo osnovnih operacija gomile kao što su pronalaženje, brisanje i umetanje. Budući da će elementi stalno dolaziti i odlaziti, morate:

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

Stvorite gomile

Proces konstruiranja gomila poznat je kao stvaranje gomila. S obzirom na popis ključeva, programer stvara praznu hrpu i zatim umeće druge ključeve jednu po jednu koristeći osnovne operacije hrpe.

Pa počnimo graditi Min-heap pomoću Willaimove metode umetanjem vrijednosti 12,2,8,1 i 4 u hrpu. Možete izgraditi hrpu s n elemenata tako da započnete s praznom hrpom i zatim je uzastopno ispunite drugim elementima uz O (nlogn) vrijeme.

Heapify: u algoritmu za umetanje, koji pomaže u umetanju elemenata u gomilu. Provjerava je li praćena struktura podataka gomile svojstava.
Na primjer, max heapify bi provjerio je li vrijednost roditelja veća od njegovog potomka. Elementi se zatim mogu sortirati pomoću metoda kao što je zamjena.

Spajanje: s obzirom na to da imate dvije gomile za kombiniranje u jednu, upotrijebite gomile spajanja da biste objedinili vrijednosti iz dvije hrpe. Međutim, originalne gomile su još uvijek sačuvane.

Pregledajte gomile

Inspecting Heaps se odnosi na provjeru broja elemenata u strukturi podataka heapa i provjeru je li heap prazan.

Važno je pregledati gomile kao sortiranje ili postavljanje elemenata u red čekanja. Provjera imate li elemenata za obradu koristeći Is-Empty() je važna. Veličina hrpe pomoći će u lociranju maksimalne ili minimalne hrpe. Dakle, trebate znati elemente koji slijede svojstvo gomile.

Veličina – vraća veličinu ili duljinu gomile. Možete reći koliko je elemenata poredanih.
Prazno je – ako je gomila NULL, vraća TRUE, 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 gomile korisna je u mnogim programskim aplikacijama u stvarnom životu kao što su:

Pomaže u filtriranju neželjene pošte.
Implementacija graf algoritama.
OperaBalansiranje opterećenja sustava i kompresija podataka.
Pronađite redoslijed u statistici.
Implementirajte prioritetne redove gdje možete pretraživati stavke na popisu u logaritamskom vremenu.
Heap struktura podataka također se koristi za sortiranje.
Simulacija kupaca na liniji.
Upravljanje prekidom Operating sustav.
U Huffmanovom kodiranju za kompresiju podataka.

Svojstva reda čekanja prioriteta hrpe

U gomilama prioriteta, podatkovne stavke na popisu međusobno se uspoređuju kako bi se odredio manji element.
Element se stavlja u red čekanja i zatim uklanja.
Svaki pojedinačni element u redu čekanja prioriteta ima jedinstveni broj povezan s njim identificiran kao prioritet.
Nakon izlaska iz prioritetnog reda, prvi izlazi element s najvišim prioritetom.

Koraci za implementaciju reda čekanja prioriteta gomile Java

Heap sortiranje u JAVI s primjerom koda

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

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 s primjerom koda

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)