Un heap è una struttura dati ad albero specializzata che rispetta la cosiddetta proprietà di heap:
🗼
Se P è il nodo genitore di C, allora il valore di P è maggiore o uguale (in un max-heap) o minore o uguale (in un min-heap) al valore di C.
Un esempio di max-heap con 8 nodi
Esistono due principali tipologie di heap:
Max Heap: Il valore del nodo genitore deve essere maggiore o uguale a quello dei suoi nodi figli.
Min Heap: Il valore del nodo genitore deve essere minore o uguale a quello dei suoi nodi figli.
Ci concentreremo sul max-heap perché la maggior parte delle librerie standard implementa un max-heap per le code con priorità. In un max-heap, la radice dell’albero è l’elemento più grande, mentre le foglie sono le più piccole. Inoltre, non esiste un ordine specifico per i nodi foglia. Quindi l’unica garanzia è che il nodo radice sia il maggiore e che i suoi nodi figli abbiano valori minori o uguali al suo.
Da notare che l’ultima riga dell’heap è sempre riempita da sinistra a destra. Quindi la foglia più a sinistra è assegnata prima e quella più a destra per ultima, come mostrato nella figura sopra.
Implementation
Un heap può essere implementato come un array, dove il primo elemento dell’array rappresenta il nodo radice. Poiché ogni nodo ha soltanto 2 figli, possiamo definire l’indicizzazione nel seguente modo:
L’elemento radice ha indice 1.
I figli sinistro e destro di un nodo con indice i si trovano rispettivamente a 2i e 2i+1.
Il nodo genitore di un elemento di indice i si trova a i // 2.
L’heap mostrato in precedenza può essere rappresentato in una lista come segue:
# Leggere semplicemente ogni riga nell'immagine e scrivere i numeri uno accanto all'altro
heap = [None, 8, 5, 7, 1, 1, 6, 3, 1]
# Oppure, per visualizzarlo meglio
heap = [None, # Saltiamo l'indice [0] per avere un'indicizzazione più semplice
8, # Indice [1]
5, 7, # Indici [2, 3]
1, 1, 6, 3, # Indici [4, 5, 6, 7]
1] # Indice [8]
Challenge: Check if the binary tree is a heap
Dato un albero binario rappresentato da un array di n numeri (con l’indicizzazione descritta sopra), occorre verificare se l’albero soddisfa le proprietà di un max-heap.
Input
La prima riga dell’input contiene un singolo intero n (1 ≤ n ≤ 100 000).
La riga successiva contiene n numeri separati da spazio () che rappresentano i valori degli elementi nell’heap.
Output
Il programma deve stampare Yes se l’albero binario fornito rispetta la proprietà di max-heap, altrimenti deve stampare No.
Examples
Input
Output
8
8 5 7 1 1 6 3 1
Yes
7
8 5 7 1 9 6 3
No
Explanation
Example 1
All the parent nodes have a value larger than or equal to their child nodes. Therefore, the heap property is satisfied.
Example 2
The node with a value of 9 is larger than its parent node. Therefore, the heap property is not satisfied.
