Mi sono ricordato che l'heap può essere utilizzato per cercare se un elemento è in esso o meno con O (logN) complessità temporale. Ma improvvisamente non riesco a ottenere i dettagli. Posso solo trovare getmin delete add e così via.Cerca un elemento in un heap
Qualcuno può dare un suggerimento?
È necessario cercare attraverso ogni elemento nell'heap per determinare se un elemento è all'interno.
Un'ottimizzazione è possibile, tuttavia (assumiamo un heap massimo qui). Se hai raggiunto un nodo con un valore inferiore rispetto all'elemento che stai cercando, non devi cercare ulteriormente da quel nodo. Tuttavia, anche con questa ottimizzazione, la ricerca è ancora O (N) (è necessario verificare in media N/2 nodi).
Penso che quello che stai cercando sia un BST (albero di ricerca binario).
Non utile se si dispone già di una coda di priorità e si desidera verificare se contiene un determinato elemento. – finnw
È tutto vero? Prendi il seguente Heap come esempio: '[5, 4, 1, 3]' Se cerco questo heap (sotto forma di array) per il numero 3, premo 1 e, in base al tuo algoritmo, fermati qui concludere che non è nel mucchio quando in realtà è? Mi sto perdendo qualcosa qui? –
Con l'ottimizzazione, la sottostruttura con radice 1 non verrà ricercata ulteriormente, poiché non può contenere 3. 3 è in un'altra sottostruttura. Sono d'accordo che una ricerca lineare (al contrario di una ricorsiva) può dare una risposta sbagliata. –
@JamesSanders È vero in tutti i casi, anche per una ricerca lineare. L'albero binario completo avrà il valore 3 come figlio sinistro di 4, e 1 sarà alla stessa altezza di 4. Anche se stai facendo una ricerca lineare, l'ottimizzazione dice che 4> 3, quindi devi, al minimo , confronta i figli di 4, in aggiunta a tutti gli altri elementi alla stessa altezza di 4. – lee