Bei Heap-Sortierung, wenn wir ein Array in aufsteigender Reihenfolge sortieren wollen, sollte der Heap dann in einen Max-Heap oder einen Min-Heap konvertiert werden?Heap sort, min-haufen verwendet werden oder max?
Jeder Ansatz kann gemacht werden, um zu arbeiten. In der Regel verwenden Sie einen Max-Heap, der so angeordnet ist, dass das größte Element ganz links im Array liegt. Wenn Sie die Elemente aus dem Heap entfernen und entfernen, um sie an ihren endgültigen Positionen zu platzieren, können Sie sie auf der anderen Seite des Arrays von rechts nach links (in absteigender Reihenfolge) platzieren, ohne auf die anderen Heap-Elemente zu wechseln .
Im Prinzip könnten Sie auch einen min-Heap mit dem minimalen Element in der rechten Position erstellen, dann kleine Elemente aus der Warteschlange entfernen und sie ganz links verschieben, obwohl ich das noch nie zuvor gesehen habe.
Ich habe auch Code gesehen, der einen Min-Heap verwendet, nach hinten herausnimmt und dann eine O (n) Umkehrung des Arrays nach dem Prozess ausführt. Ich habe nie verstanden, warum der Programmierer es so geschrieben hat. Im Allgemeinen habe ich den Max-Heap gesehen. Oh, und ich habe die Methode "Min-Heap im Rücken" gesehen. Ich weiß nicht, warum er es so gemacht hat. –
Vielen Dank @templatetypedef und @ jim-mischel! –