UN Mucchio è una struttura dati ad albero binario completa che soddisfa la proprietà heap: per ogni nodo, il valore dei suoi figli è inferiore o uguale al proprio valore. Gli heap vengono solitamente utilizzati per implementare code di priorità, dove l'elemento più piccolo (o più grande) è sempre alla radice dell'albero.

Struttura dei dati heap

Tabella dei contenuti

• Tipi di cumuli
• Operazioni sull'heap
• Cos'è la struttura dei dati heap?

  UN mucchio è una struttura dati binaria basata su albero che soddisfa la proprietà heap: il valore di ciascun nodo è maggiore o uguale al valore dei suoi figli. Questa proprietà garantisce che il nodo radice contenga il file massimo O minimo valore (a seconda del tipo di heap) e i valori diminuiscono o aumentano man mano che ci si sposta lungo l'albero.

  media vs media

  Tipi di cumuli

  Esistono due tipi principali di heap:

  
  
  
  

  cos'è la rom

  • Heap massimo: Il nodo radice contiene il valore massimo e i valori diminuiscono man mano che si scende nell'albero.
  • Heap minimo: Il nodo radice contiene il valore minimo e i valori aumentano man mano che ci si sposta lungo l'albero.

  Operazioni sull'heap

  Le operazioni heap comuni sono:

  • Inserire : Aggiunge un nuovo elemento all'heap mantenendo la proprietà dell'heap.
  • Estrai massimo/minimo: Rimuove l'elemento massimo o minimo dall'heap e lo restituisce.
  • Heapify : Converte un albero binario arbitrario in un heap.

  Gli heap vengono comunemente utilizzati per implementare code di priorità, in cui gli elementi vengono recuperati in base alla loro priorità (valore massimo o minimo).

• Heapsort è un algoritmo di ordinamento che utilizza un heap per ordinare un array in ordine crescente o decrescente.
• Gli heap vengono utilizzati negli algoritmi grafici come Algoritmo di Dijkstra E Algoritmo di Prim per trovare i percorsi più brevi e gli alberi di copertura minimi.

Heap binario

Applicazioni, vantaggi e svantaggi di Heap

Complessità temporale della creazione di un heap

Confronto tra Heap e Albero

Quando si costruisce un Heap, la struttura dell'Heap è unica?

Mucchio di Fibonacci

Mucchio di sinistra

K-ary Heap

Ordinamento heap

Controlla se un dato albero binario è heap

Come verificare se un determinato array rappresenta un heap binario?

Ordinamento heap iterativo

K'esimo elemento più grande in un array

K'esimo elemento più piccolo/più grande nell'array non ordinato | Insieme 1

Altezza di un albero binario completo (o Heap) con N nodi

Heap Ordina in ordine decrescente utilizzando l'heap minimo

Stampa tutti i nodi inferiori a un valore x in un Heap minimo.

Albero del torneo (albero del vincitore) e heap binario

Collega n corde con un costo minimo

Numero massimo di elementi distinti dopo aver rimosso k elementi

K combinazioni di somma massima da due array

Mediana del flusso di numeri interi in esecuzione utilizzando STL

Mediana in un flusso di numeri interi (interi in esecuzione)

K'esimo elemento più grande in un flusso

Prodotto tripletta più grande in un flusso

Trova k numeri con il maggior numero di occorrenze nell'array specificato

Converti heap minimo in heap massimo

Dato l'attraversamento dell'ordine di livello di un albero binario, controlla se l'albero è un Min-Heap

Unisci k array ordinati | Insieme 1

Ordina i numeri memorizzati su macchine diverse

Il più piccolo squilibrio di sequenza

Il più grande squilibrio di una sequenza

Differenza massima tra due sottoinsiemi di m elementi

Converti BST in Heap minimo

Unisci due Max Heap binari

K-esimo sottoarray contiguo con somma più grande

Prodotto minimo di k interi in un array di interi positivi

Riorganizzare i caratteri in una stringa in modo tale che non ce ne siano due adiacenti uguali

Somma di tutti gli elementi compresi tra k1'esimo e k2'esimo elemento più piccolo

Somma minima di due numeri formati da cifre di un array

Link veloci:

• Problemi pratici sull'heap
• Consigliato:
  • Impara la struttura dei dati e gli algoritmi | Tutorial DSA