Einen Heap in O (n) Zeit in eine BST konvertieren?

Question

Einen Heap in O (n) Zeit in eine BST konvertieren?

7

Ich denke, dass ich die Antwort kenne und die minimale Komplexität ist O (nlogn) .

Aber gibt es eine Möglichkeit, einen binären Suchbaum aus einem Haufen in O (n) Komplexität zu machen?

algorithm data-structures big-o binary-search-tree binary-heap

user1940350 31.12.2012, 23:37

quelle

1 Antwort

Tags und Links algorithm data-structures big-o binary-search-tree binary-heap

Django: Verwenden von Annotate, Count und Distinct in einem Queryset So finden Sie den Zeilenindex, wenn Sie auf eine Schaltfläche in der Tabelle klicken

score 19 · Accepted Answer

Es gibt keinen Algorithmus zum Erstellen einer BST von einem Heap in O (n) -Zeit. Der Grund dafür ist, dass Sie in o (n) -Zeit aus n Elementen einen Haufen bilden können. Wenn Sie eine BST für eine Reihe von Werten haben, können Sie sie in O (n) -Zeit sortieren, indem Sie eine Inorder-Traversierung durchführen. Wenn Sie in O (n) Zeit eine BST von einem Heap erstellen könnten, könnten Sie dann einen O (n) Sortieralgorithmus von

haben

Den Heap in O (n) Zeit erstellen,
Konvertieren des Heap in eine BST in O (n) Zeit und
Gehen Sie die BST in O (n) Zeit, um eine sortierte Sequenz zu erhalten.

Daher ist es nicht möglich, einen Heap in O (n) -Zeit (oder in o (n log n) -Zeit) in eine BST zu konvertieren, wobei o little-o Notation ).

Es ist jedoch möglich, einen BST von einem Heap in O (n log n) -Zeit zu erstellen, indem der Maximalwert aus dem BST wiederholt entfernt und als der am weitesten rechts liegende Knoten in den Baum eingefügt wird. (Sie müssen dort einen Zeiger für den schnellen Zugriff speichern; nur das wiederholte Einfügen an der Wurzel würde O (n ²) Zeit benötigen.)

Hoffe, das hilft!