CODE DI PRIORITÀ
HEAP BINARIO
DEFINIZIONE
UTILIZZIAMO MIN-HEAP
PADRE MINORE FIGLI
PROPRIETÀ HEAP ORDER
MINIMO SU T.ROOT
ALBERO BINARIO QUASI COMPLETO
IMPLEMENTAZIONE CON ARRAY
NODO i
PADRE
FIGLI
i/2
2i
2i+1
A[i]<A[2i] && A[i]<A[2i+1]
ALBERI BINOMIALI
PER UN ALBERO Bk
2^k NODI
ALTEZZA ALBERO = K
(K i) Binomiale NODI ALL'ALTEZZA i
GRADO RADICE (NUMERO FIGLI RADICE) = K
HEAP BINOMIALI
PROPRIETÀ HEAP BINOMIALI
HA AL PIÙ log(n)+1 ALBERI BINOMIALI
HEAP BINOMIALE CON N NODI
DEFINIZIONE
INSIEME DI ALBERI BINOMIALI
SODDISFANO HEAP ORDER
RAPPRESENTAZIONE FIGLIO SINISTRO FRATELLO DESTRO
PROBLEMA UNION
COMPLESSITÀ LINEARE
RADICI ORDINATE IN LISTA IN SENSO CRESCENTE
NODO
CHILD
SIBLING
PARENT
KEY
DEGREE
PUNTATORE AL PADRE
PUNTATORE A FIGLIO PIÙ A SINISTRA
PUNTATORE A PRIMO FRATELLO A DESTRA
VALORE NEL NODO
GRADO DEL NODO
UNIONE
BINOMIAL HEAP MERGE
BINOMIAL HEAP UNION
BINOMIAL LINK
INPUT: 2 ALBERI BINOMIALI
OUTPUT: UN ALBERO CON I 2 ATTACCATI
INPUT: 2 LISTE DI RADICI
OUTPUT: LISTE FUSE IN 1 LISTA
COSTRUIAMO UN NUOVO HEAP H
INPUT: 2 HEAP BINOMIALI H1 H2
H.head = BINOMIAL_HEAP_MERGE(H1, H2)
INIZIALIZZAZIONE DI X
X=H.HEAD
NEXT-X=X.SIBLING
PREV-X=NIL
WHILE
COMPLESSITÀ O(log(n))
CASO 1
CASO 2
CASO 3
CASO 4
X E NEXT-X HANNO GRADO DIVERSO
FACCIAMO AVANZARE X
PREV-X=X
X=NEXT-X
NEXT-X=X.SIBLING
NON ABBIAMO ALCUN PROBLEMA
NEXT-X.SIBLING.DEGREE=X.DEGREE
NON ABBIAMO ALCUN PROBLEMA
FACCIAMO AVANZARE X
X=NEXT-X
NEXT-X=X.SIBLING
PREV-X=X
X.KEY<=NEXT-X.KEY