Structura datelor Heap: Ce este Heap-ul?

Ce este o structură de date Heap?

Un Heap este o structură de date specializată, bazată pe arbore. Structura de date Heap cuprinde un nod superior numit rădăcină (părinte). Al doilea nod este copilul stâng al rădăcinii, în timp ce al treilea nod este copilul drept al rădăcinii. Nodurile succesive sunt completate de la stânga la dreapta. Cheia nodului părinte se compară cu cea a urmașilor săi, astfel încât să se producă o aranjare corectă. Arborele este ușor de vizualizat, fiecare entitate fiind numită nod, iar fiecare nod are o cheie unică pentru identificare.

În termeni simpli, un Heap este un arbore binar complet care satisface proprietatea heap: fiecare părinte este ordonat consecvent în raport cu copiii săi, ceea ce îl face ideal pentru cozi de prioritate și sortare în Heap.

De ce aveți nevoie de Heap Data Structure?

Iată principalele motive pentru utilizarea unui Heap:

• Structura de date Heap permite ștergerea și inserarea în timp logaritmic – O(log₂nu).
• Datele din arbore sunt aranjate într-o anumită ordine. Pe lângă actualizarea sau interogarea valorilor precum un maxim sau un minim, programatorul poate găsi relații între părinte și urmaș.
• Puteți aplica conceptul de Model de obiect document pentru a vă ajuta să înțelegeți vizual structura de date Heap.
• Heap-urile acceptă operații eficiente în coada de prioritate, care sunt esențiale pentru algoritmi grafici, cum ar fi cea mai scurtă cale a lui Dijkstra și arborele de acoperire minim al lui Prim.

Tipuri de grămezi

Structura de date Heap are diverși algoritmi pentru gestionarea inserțiilor și eliminarea elementelor, inclusiv coada de prioritate, heap binară, heap binomială și Sortare în grămadă.

• Coada prioritară: Este un abdomentracStructura de date t conține obiecte prioritizate. Fiecare obiect sau element are o prioritate prestabilită. Prin urmare, obiectul sau elementul căruia i se atribuie prioritatea mai mare primește serviciul înaintea celorlalte.
• Heap binar: Heap-urile binare sunt potrivite pentru operațiuni simple de heap, cum ar fi ștergerile și inserțiile. Acestea reprezintă implementarea implicită din spatele majorității cozilor de prioritate standard ale bibliotecilor.
• Grămadă binomială: Un heap binomial constă dintr-o serie de colecții de arbori binomiali care alcătuiesc heap-ul. Un arbore heap binomial nu este un arbore obișnuit, deoarece este riguros definit. Numărul total de elemente dintr-un arbore binomial este întotdeauna egal cu 2.ⁿ noduri.
• Sortare în heap: Spre deosebire de majoritatea algoritmilor de sortare, Heap Sort utilizează spațiul O(1) pentru operația sa de sortare. Este un algoritm de sortare bazat pe comparații în care sortarea are loc în ordine crescătoare prin transformarea mai întâi a intrării într-un Max-Heap. Puteți considera Heap Sort ca un arbore binar de căutare îmbunătățit.

De obicei, o structură de date Heap folosește două strategii. Pentru intrările 12 – 8 – 4 – 2 și 1:

• Min-Heap – cea mai mică valoare în partea de sus
• Max-Heap – cea mai mare valoare din vârf

Min-Heap

În structura Min-Heap, nodul rădăcină are o valoare fie egală, fie mai mică decât copiii acelui nod. Prin urmare, rădăcina unui Min-Heap deține valoarea minimă. Min-Heap este, de asemenea, un arbore binar complet.

Odată ce ai un Min-Heap într-un arbore, toate frunzele sunt candidați viabili pentru valoarea maximă. Cu toate acestea, trebuie să examinezi fiecare frunză pentru a obține valoarea exactă a Max-Heap.

Exemplu de Min-Heap

În diagrama de mai sus, puteți observa o secvență clară de la rădăcină până la nodul cel mai de jos.

Să presupunem că stocați elementele în matricea Array_N[12, 2, 8, 1, 4]. După cum puteți vedea din matrice, elementul rădăcină încalcă prioritatea Min-Heap. Pentru a menține proprietatea Min-Heap, trebuie să efectuați operațiile min-heapify pentru a schimba elementele până când regulile Min-Heap sunt îndeplinite.

Max-Heap

În structura Max-Heap, nodul părinte sau rădăcină are o valoare egală sau mai mare decât fiii săi. Acest nod deține valoarea maximă. Este un arbore binar complet, deci puteți construi un Max-Heap dintr-o colecție de valori într-un timp O(n).

Iată câteva metode utilizate în mod obișnuit la implementarea unui Java Max-Heap:

• Adăugați (): Plasează un element nou într-o matrice (heap). Dacă utilizați o matrice (array), obiectele sunt adăugate la sfârșitul matricei, în timp ce în arborele binar, obiectele sunt adăugate de sus în jos și apoi de la stânga la dreapta.
• Eliminare (): Această metodă vă permite să eliminați primul element din lista de matrice. Deoarece elementul nou promovat nu mai este cel mai mare, metoda Sift-Down îl mută întotdeauna în noua sa locație.
• Cernere (): Această metodă compară un obiect rădăcină cu copiii săi și apoi împinge nodul relocat în poziția sa corectă.
• Cernere (): Dacă utilizați metoda matricei pentru a adăuga un element nou inserat într-o matrice, atunci metoda Sift-Up ajută nodul nou adăugat să se mute în poziția corectă. Noul element este mai întâi comparat cu părintele său prin simularea structurii de date arborescente.

  Aplicați formula Parent_Index = Child_Index / 2. Continuați să faceți acest lucru până când elementul maxim se află în partea de sus a matricei.

Heap de bază Operații

Pentru a găsi cele mai mari și cele mai mici valori dintr-un set de date, aveți nevoie de câteva operațiuni heap de bază, cum ar fi găsirea, inserarea și ștergerea. Deoarece elementele apar și dispar constant, ar trebui să știți cum să:

• Găsi – Căutați un articol în grămada.
• Insera – Adăugați un nou copil în grămada.
• Șterge – Ștergeți un nod dintr-un heap.

Creați grămezi

Procesul de construire a heap-urilor este cunoscut sub numele de creare a heap-urilor. Având o listă de chei, programatorul creează o heap goală și apoi introduce celelalte chei pe rând folosind operațiile de bază ale heap-urilor.

Așadar, să începem să construim un Min-Heap folosind metoda lui William prin inserarea valorilor 12, 2, 8, 1 și 4. Puteți construi heap-ul cu n elemente începând cu un heap gol și apoi umplându-l succesiv cu alte elemente folosind timpul O(n log n).

• Îngrămădire: O rutină de inserare care ajută la inserarea elementelor într-o heap, păstrând în același timp proprietatea heap.

  De exemplu, o operație max-heapify verifică dacă valoarea elementului părinte este mai mare decât cea a elementului urmaș. Elementele pot fi apoi sortate folosind metode precum swapping.

• Combina: Când aveți două heap-uri de combinat într-una singură, utilizați operația de îmbinare pentru a aduce împreună valorile din cele două heap-uri. Heap-urile originale sunt în continuare păstrate.

Inspectați grămezi

Inspectarea heap-urilor se referă la verificarea numărului de elemente din structura de date a heap-ului și la validarea dacă heap-ul este gol.

Este important să inspectați heap-urile în timp ce sortați sau puneți elementele în coadă. Verificarea dacă există elemente de procesat folosind Is-Empty() este importantă. Dimensiunea heap-ului va ajuta la localizarea rădăcinilor Max-Heap sau Min-Heap, așa că trebuie să știți câte elemente urmează proprietatea heap.

• Mărimea – returnează magnitudinea sau lungimea heap-ului. Vă spune câte elemente sunt stocate în ordine sortată.
• Este gol – returnează TRUE dacă heap-ul este nul, altfel returnează FALSE.

Aici, imprimați toate elementele din prioritateQ buclă și apoi verificând că priorityQ nu este goală.

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

Utilizări ale structurii de date Heap

Structura de date Heap este utilă în multe aplicații de programare din viața reală, cum ar fi:

• Ajută la filtrarea spamului.
• Implementarea algoritmilor grafici precum Dijkstra și Prim.
• Operaechilibrarea încărcării sistemului ting și compresia datelor.
• Găsirea statisticilor de ordine, cum ar fi al k-lea cel mai mic element.
• Implementarea cozilor de prioritate în care puteți căuta elemente dintr-o listă în timp logaritmic.
• Structura de date Heap este utilizată și pentru sortarea prin Heap Sort.
• Simularea clienților la coadă.
• Gestionarea întreruperilor în Operating System.
• În codarea Huffman pentru compresia datelor.
• Îmbunătățirea căutării de tip „cel mai bun primul” și a euristicilor A* în planificarea traseelor ​​prin inteligență artificială.

Proprietăți de coadă prioritară heap

Următoarele proprietăți descriu cum se comportă coada de priorități construită pe o heap:

• În heap-urile cu prioritate, elementele de date din listă sunt comparate între ele pentru a determina care este elementul mai mic sau mai mare.
• Un element este plasat într-o coadă și apoi eliminat în ordinea priorității.
• Fiecare element din coada de priorități are un număr unic asociat, identificat ca prioritate.
• La ieșirea dintr-o coadă de prioritate, elementul cu prioritate maximă iese primul.

Pași pentru implementarea cozii de prioritate Heap în Java

Următoarea secțiune se mută într-o zonă betonată Java implementare care transformă aceste reguli în cod funcțional.

Sortare în grămada Java implementate cu Code Exemplu

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

producție

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

Sortare în grămada Python implementate cu Code Exemplu

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)

producție

[1, 3, 4, 7, 9]

În continuare, veți afla despre Metoda Bisecției.

Întrebări frecvente