DOMANDA Implementare un heap binario in c

[Mr. Coder]

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:

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?

 

[BAT]

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.

 

[Mr. Coder]

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).

 

[BAT]

ti serve uno fresco di studi...
spiega con un'immagine cosa fa questa max_heap_increase_key