Pourquoi tas de tri a une complexité de O(1)?

Je comprends que, à la fois rapide tri et la fusion de tri besoin O(n) espace auxiliaire temporaire par les sous-ensembles qui sont construits, et en place rapide de tri nécessite O(log n) espace auxiliaire pour la pile récursive des cadres. Mais pour des tas de tri, il me semble qu'il a aussi un pire des cas de O(n) auxiliaire de l'espace pour construire le temporaire tas, même si les nœuds sont juste des pointeurs vers les éléments réels.

Je suis tombé sur ce explication :

Seulement O(1) de l'espace supplémentaire est nécessaire parce que le segment est construit à l'intérieur du tableau à trier.

Mais je pense que cela signifie que le tableau d'origine forcément déjà eu à être mis en œuvre comme une sorte d'arbre? Si le tableau d'origine est juste un vecteur, il semble de mémoire pour un tas pourrait encore être affecté.

  • ce n'est pas la fonction de tri rapide si elle n'est pas en place. Et vous pouvez fusionner en place.
  • C'est une sorte de possible de faire un tri rapide constante avec les auxiliaires de l'espace, mais il est assez étrange que de nombreux programmeurs question si c'est encore un quicksort.
InformationsquelleAutor Herman Tran | 2014-03-06
  1. 30

    Données dans un tableau peut être réaménagé en un tas, en place. L'algorithme pour ce est en fait étonnamment simple., mais je ne vais pas entrer dans les ici.

    Pour un tas de tri permet d'organiser les données, de sorte qu'il forme un tas en place, avec le plus petit élément à l'arrière (std::make_heap). Ensuite, vous échangez le dernier élément du tableau (le plus petit élément dans le tas), avec le premier élément du tableau (un largish nombre), et ensuite mélanger que les grandes élément vers le bas le tas jusqu'à ce qu'il est dans une nouvelle position correcte et le segment est encore un nouveau min tas, avec le plus petit élément restant dans le dernier élément du tableau. (std::pop_heap)

    data:         1 4 7 2 5 8 9 3 6 0

make_heap:   [8 7 9 3 4 5 6 2 1 0] <- this is a min-heap, smallest on right

pop_heap(1): [0 7 9 3 4 5 6 2 1 8] <- swap first and last elements
pop_heap(2): 0 [7 9 3 4 8 6 2 5 1] <- shuffle the 8 down the heap

pop_heap(1): 0 1 [9 3 4 8 6 2 5 7] <- swap first and last elements
pop_heap(2): 0 1 [9 7 4 8 6 3 5 2] <- shuffle the 7 down the heap

etc

    Donc pas de données doit être stocké n'importe où ailleurs, sauf peut-être pendant le swap étape.

    Pour la visualisation, voici que les originaux des tas montré dans un formulaire standard

    make_heap 
           0
     2           1
  3     4     5     6
               8   7 9
pop_heap
           8                           1                           1
     2           1               2           8               2           5 
  3     4     5     6    ->   3     4     5     6    ->   3     4     8     6 
                   7 9                         7 9                         7 9
    • Merci pour l'explication et exemple!
    • Excellente réponse et de visualisation. Sauvé!
    InformationsquelleAutor Mooing Duck
  2. 2

    La cool truc c'est que depuis le tas est un arbre binaire complet, vous pouvez simplement utiliser un simple tableau, et pour le point i, sa mère serait l'élément i/2.

    • Cette réponse est très pas clair
    • Je suis d'accord avec vous. Bien que celui qui connaît la réponse figure en une seconde.
    • vous pouvez comprendre la récursivité vous devez d'abord comprendre la récursivité"
    • Merci, c'est aussi utile
    • Ceci ne répond pas à la question.
    InformationsquelleAutor Ziyao Wei