Devo fare un progetto: Coda di priorità rappresentata nella struttura di ricerca binaria. È per la mia classe di algoritmi. Non sono sicuro di come useresti un albero di ricerca binario come coda prioritaria. Tutti gli esempi che ho trovato su Internet riguardavano un sacco e che "mai e poi mai dovresti implementare una coda prioritaria in un bst ma solo in heap". Qualcuno potrebbe spiegarmi cosa devo fare esattamente? Grazie!
risposte:
0 per risposta № 1Come suggerimento, una coda di priorità deve essere efficientesupporta l'inserimento di elementi, la lettura del valore più piccolo (o il più grande, in una coda con priorità massima) e la rimozione del valore più piccolo. Un BST supporta già inserimenti rapidi ed eliminazioni. Quindi, se tutti gli elementi nella coda di priorità fossero archiviati in un BST, come troveresti il valore più piccolo? Verifica se puoi utilizzare il fatto che il BST memorizza i suoi elementi in ordine ordinato per trovare un algoritmo molto rapido per trovare il valore più piccolo.