DOMANDA Implementare un heap binario in c

Mr. Coder

Nuovo Utente
43
10
Vorrei implementare un heap binario in c (ho appena finito di studiare la parte di teoria dal libro di algoritmi). Ho definito il seguente header:
C:
typedef struct max_heap_t *max_heap_ptr;

max_heap_ptr max_heap_create(size_t element_size, size_t key_size, int (*key_compare)(void *a, void *b));
size_t max_heap_get_nitems(max_heap_ptr heap);
void max_heap_insert(max_heap_ptr heap, void *element_ptr, void *key_ptr);
void max_heap_max(max_heap_ptr heap, void *element_ptr);
void max_heap_extract_max(max_heap_ptr heap, void *element_ptr);
void max_heap_increase_key(max_heap_ptr heap, void *element_ptr, void *new_key_ptr);
void max_heap_free(max_heap_ptr heap);
La struttura dati che ho usato per implementare l'albero dell'heap è un'array (come nel libro) in cui il figlio sinistro del nodo i si trova in posizione (2*i + 1) e il figlio destro in posizione (2*i + 2).
Ho implementato correttamente tutte le operazioni tranne max_heap_increase_key.
Dal libro vedo che questa operazione può essere implementata nel seguente modo:
  1. Trova il nodo contenente l'elemento e.
  2. Incrementa la chiave di tale nodo a k
  3. Richiama la procedura per ripristinare la proprietà di un heap tramite scambi ripetuti tra nodi (che ho implementato correttamente)
Questa procedura deve essere implementata con costo O(log n). Il mio problema sta al passo 1... Non so come trovare il nodo contenente l'elemento e senza usare una ricerca lineare (che impiegherebbe O(n)). Devo usare necessariamente una mappa per mantenere la corrispondenza tra elementi e posizione nell'array? Vorrei evitare... Esiste un altro modo?
 

BAT00cent

Moderatore
Staff Forum
Utente Èlite
4,161
1,893
CPU
Neurone solitario
Dissipatore
Ventaglio azionato a mano
Scheda Madre
Casalinga
RAM
Molto molto volatile
Scheda Video
Binoculare integrata nel cranio
Alimentatore
Pastasciutta, pollo e patatine al forno
Internet
Segnali di fumo e/o tamburi
Sistema Operativo
Windows 10000 BUG
la ricerca con costo logaritmico è per forza una ricerca binaria, il che significa che devi pensare a come è strutturato l'heap (immagino che sia ordinato secondo qualche criterio, altrimenti la ricerca binaria non si può fare) e ricercare di conseguenza. Per esempio negli alberi binari di ricerca i nodi a sinistra del nodo padre sono minori, quelli a destra sono maggiori, il principio credo sia lo stesso.
 
Ultima modifica:

Mr. Coder

Nuovo Utente
43
10
In un heap binario (vedi qui) ogni nodo ha chiave maggiore o uguale alle chiavi dei due figli. Si potrebbe creare una procedura di search, ma richiederebbe nel caso peggiore sempre O(n).
 

BAT00cent

Moderatore
Staff Forum
Utente Èlite
4,161
1,893
CPU
Neurone solitario
Dissipatore
Ventaglio azionato a mano
Scheda Madre
Casalinga
RAM
Molto molto volatile
Scheda Video
Binoculare integrata nel cranio
Alimentatore
Pastasciutta, pollo e patatine al forno
Internet
Segnali di fumo e/o tamburi
Sistema Operativo
Windows 10000 BUG
ti serve uno fresco di studi...
spiega con un'immagine cosa fa questa max_heap_increase_key
 

Entra

oppure Accedi utilizzando

Discussioni Simili