Structura de date Heap: Ce este Heap? Heap min și maxim (exemplu)

Ce este un Heap?

Heap este o structură de date arborescentă specializată. Heap-ul cuprinde cel mai de sus nodul numit rădăcină (părinte). Al doilea copil este copilul stâng al rădăcinii, în timp ce al treilea nod este copilul drept al rădăcinii. Nodurile succesive sunt umplute de la stânga la dreapta. Cheia nodului părinte se compară cu cea a descendenților săi și are loc o aranjare adecvată. Arborele este ușor de vizualizat unde fiecare entitate este numită nod. Nodul are chei unice pentru identificare.

De ce aveți nevoie de Heap Data Structure?

Iată principalele motive pentru a utiliza Heap Data Structure:

Structura de date heap permite ștergerea și inserarea în timp logaritmic – O(log₂nu).
Datele din arbore sunt modelate într-o anumită ordine. Pe lângă actualizarea sau interogarea lucrurilor, cum ar fi un maxim sau minim, programatorul poate găsi relații între părinte și urmași.
Puteți aplica conceptul de Model de obiect document pentru a vă ajuta să înțelegeți structura de date heap.

Tipuri de grămezi

Structura de date heap are diverși algoritmi pentru gestionarea inserărilor și eliminarea elementelor dintr-o structură de date heap, inclusiv Priority-Queue, Binary-Heap, Binomial Heap și Heap-Sort.

Prioritate-coadă: Este o structură de date abstractă care conține obiecte prioritizate. Fiecare obiect sau articol are o prioritate pre-aranjată pentru el. Prin urmare, obiectul sau elementul căruia i se atribuie o prioritate mai mare primește serviciul înainte de restul.
Heap binar: Heapurile binare sunt potrivite pentru operațiuni heap simple, cum ar fi ștergeri și inserări.
Binom-Heap: O grămadă binomială constă dintr-o serie de colecții de arbori binomi care alcătuiesc grămada. Arborele binomial Heap nu este un arbore obișnuit, deoarece este definit riguros. Numărul total de elemente dintr-un arbore binom posedă întotdeauna 2ⁿ noduri.
Sortare în grămada: Spre deosebire de majoritatea algoritmilor de sortare, heap-sort folosește spațiul O(1) pentru operația de sortare. Este un algoritm de sortare bazat pe comparație în care sortarea are loc în ordine crescătoare, transformându-l mai întâi într-un heap maxim. Puteți privi un Heapsort ca pe un arbore de căutare binar de calitate îmbunătățită.

De obicei, o structură de date heap utilizează două strategii. Pentru intrarea 12 – 8 – 4 – 2 și 1

Min Heap – cea mai mică valoare în partea de sus
Max Heap – cea mai mare valoare în partea de sus

Min Heap

În structura Min Heap, nodul rădăcină are o valoare fie egală, fie mai mică decât copiii de pe acel nod. Acest nod heap al unui Min Heap deține valoarea minimă. Una peste alta, structura sa min-heap este una completă arbore binar.

Odată ce aveți o grămadă Min într-un copac, toate frunzele sunt candidați viabili. Cu toate acestea, trebuie să examinați fiecare dintre frunze pentru a obține valoarea exactă Max-heap.

Exemplu min Heap

În diagramele de mai sus, puteți observa o secvență clară de la rădăcină la cel mai de jos nod.

Să presupunem că stocați elementele în Array 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țiunile min-heapify pentru a schimba elementele până când sunt îndeplinite proprietățile min heap.

Max Heap

În structura lui Max Heap, nodul părinte sau rădăcină are o valoare egală sau mai mare decât copiii săi din nod. Acest nod deține valoarea maximă. Mai mult, este un arbore binar complet, astfel încât să puteți construi un heap maxim dintr-o colecție de valori și să îl rulați în timpul O(n).

Iată câteva metode pentru implementarea unui heap java max

Adăuga (): plasați un nou element într-o grămadă. Dacă utilizați o matrice, 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 după stânga la dreapta.
Elimina (): Această metodă vă permite să eliminați primul element din lista de matrice. Deoarece elementul nou adăugat nu mai este cel mai mare, metoda Sift-Down îl împinge întotdeauna în noua sa locație.
Cernere în jos (): Această metodă compară un obiect rădăcină cu copilul său și apoi împinge nodul nou adăugat în poziția potrivită.
Cernere (): dacă utilizați metoda matrice pentru a adăuga un element nou inserat într-o matrice, atunci metoda Sift-Up ajută nodul nou adăugat să se mute în noua sa poziție. Elementul nou inserat este mai întâi comparat cu părintele 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 din față 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 o mulțime de operațiuni de bază heap, cum ar fi găsirea, ștergerea și inserarea. Deoarece elementele vor veni și dispar în mod constant, trebuie 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 grămezilor este cunoscut sub denumirea de creare a grămezilor. Având în vedere o listă de chei, programatorul face un heap gol și apoi inserează alte chei pe rând folosind operațiunile heap de bază.

Deci, să începem să construim un min-heap folosind metoda lui Willaim inserând valorile 12,2,8,1 și 4 într-un heap. Puteți construi heap-ul cu n elemente, începând cu un heap gol și apoi umplendu-l succesiv cu alte elemente folosind O (nlogn) timp.

Heapify: în algoritmul de inserare, care ajută la inserarea elementelor într-un heap. Se verifică dacă structura de date heap de proprietate este evidențiată.
De exemplu, un max heapify ar verifica dacă valoarea părintelui este mai mare decât descendenții acestuia. Elementele pot fi apoi sortate folosind metode precum schimbarea.

Merge: Având în vedere că aveți două heap-uri de combinat într-unul singur, utilizați merge heaps pentru a aduce împreună valorile din cele două heap-uri. Cu toate acestea, mormanele originale sunt încă păstrate.

Inspectați grămezi

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

Este important să inspectați grămezile ca sortare sau coadă de elemente. Verificarea dacă aveți elemente de procesat folosind Is-Empty() este importantă. Dimensiunea heap-ului va ajuta la localizarea maxim-heap sau min-heap. Deci, trebuie să cunoașteți elementele care urmează proprietății heap.

Mărimea – returnează mărimea sau lungimea grămezii. Puteți spune câte elemente sunt în ordine sortată.
Este gol – dacă heap-ul este NULL, returnează TRUE în caz contrar, 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.
Operating Echilibrarea sarcinii sistemului și compresia datelor.
Găsiți ordinea în statistici.
Implementați cozi prioritare în care puteți căuta articole dintr-o listă în timp logaritmic.
Structura de date heap utilizată și pentru sortare.
Simularea clienților pe o linie.
Întrerupeți manipularea Operating System.
În codarea lui Huffman pentru compresia datelor.

Proprietăți de coadă prioritară heap

În grămezi prioritare, elementele de date din listă sunt comparate între ele pentru a determina elementul mai mic.
Un element este plasat într-o coadă și apoi eliminat.
Fiecare element din coada de priorități are un număr unic asociat cu acesta, identificat ca prioritate.
La ieșirea dintr-o coadă de prioritate, elementul cu prioritate principală iese primul.

Pași pentru implementarea cozii prioritare heap în Java

Heap Sort în JAVA cu Exemplu de cod

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

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 cu Exemplu de cod

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)