Convertire un heap in un BST in tempo O (n)?

Question

Penso di conoscere la risposta e la complessità minima è O (nlogn).

Ma esiste un modo per creare una struttura di ricerca binaria da un heap nella complessità O (n)?

Answer 1

Non esiste alcun algoritmo per la costruzione di un BST da un heap nel tempo O (n). La ragione di ciò è che dato n elementi, puoi costruire un heap da loro in tempo O (n). Se hai un BST per un insieme di valori, puoi ordinarli in tempo O (n) eseguendo un traversal inorder. Se si potesse costruire un BST da un mucchio di O (n), si potrebbe quindi avere un O (n) algoritmo di ordinamento per

1. Costruire il mucchio in O (n),
2. Conversione del mucchio a un BST in O (n) ora, e
3. Camminare il BST in tempo O (n) per ottenere una sequenza ordinata.

Pertanto, non è possibile convertire un mucchio ad un BST in O (n) (o in O (n log n), dove o è little-o notation).

Tuttavia, è possibile creare un BST da un heap in tempo O (n log n) eliminando ripetutamente il valore massimo dal BST e inserendolo come il nodo più a destra nell'albero. (Dovresti memorizzare un puntatore lì per un accesso veloce, basta inserire ripetutamente alla radice richiederebbe O (n) tempo.)

Spero che questo aiuti!