Please enable JavaScript.
Coggle requires JavaScript to display documents.
CODE DI PRIORITÀ - Coggle Diagram
CODE DI PRIORITÀ
HEAP BINARIO
DEFINIZIONE
ALBERO BINARIO QUASI COMPLETO
UTILIZZIAMO MIN-HEAP
PADRE MINORE FIGLI
PROPRIETÀ HEAP ORDER
MINIMO SU T.ROOT
A[i]<A[2i] && A[i]<A[2i+1]
IMPLEMENTAZIONE CON ARRAY
NODO i
PADRE
i/2
FIGLI
2i
2i+1
PROBLEMA UNION
COMPLESSITÀ LINEARE
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
RADICI ORDINATE IN LISTA IN SENSO CRESCENTE
NODO
CHILD
PUNTATORE A FIGLIO PIÙ A SINISTRA
SIBLING
PUNTATORE A PRIMO FRATELLO A DESTRA
PARENT
PUNTATORE AL PADRE
KEY
VALORE NEL NODO
DEGREE
GRADO DEL NODO
UNIONE
BINOMIAL HEAP MERGE
INPUT: 2 LISTE DI RADICI
OUTPUT: LISTE FUSE IN 1 LISTA
COMPLESSITÀ O(log(n))
BINOMIAL HEAP UNION
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
CASO 1
X E NEXT-X HANNO GRADO DIVERSO
FACCIAMO AVANZARE X
PREV-X=X
X=NEXT-X
NEXT-X=X.SIBLING
NON ABBIAMO ALCUN PROBLEMA
CASO 2
NEXT-X.SIBLING.DEGREE=X.DEGREE
NON ABBIAMO ALCUN PROBLEMA
FACCIAMO AVANZARE X
X=NEXT-X
NEXT-X=X.SIBLING
PREV-X=X
CASO 3
X.KEY<=NEXT-X.KEY
CASO 4
BINOMIAL LINK
INPUT: 2 ALBERI BINOMIALI
OUTPUT: UN ALBERO CON I 2 ATTACCATI
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