0
Pour le tri de tas, si nous voulons trier un tableau dans un ordre croissant, alors le tas devrait-il être converti en un tas maximum ou un tas minimum?Type de tas, min-tas à utiliser ou max?
A
Répondre
3
L'une ou l'autre approche peut être mise au travail. Généralement, vous utiliseriez un tas maximum ordonné de sorte que l'élément le plus grand se trouve à l'extrême gauche du tableau. Ainsi, lorsque vous supprimez et supprimez les éléments du tas pour les placer dans leur position finale, vous pouvez les placer de droite à gauche (dans l'ordre décroissant) sur le côté éloigné du tableau sans passer par-dessus les autres éléments du tas. . En principe, vous pouvez également construire un tas min avec l'élément minimum dans la position la plus à droite, puis déquiler les petits éléments et les déplacer vers l'extrême gauche, même si je n'ai jamais vu cela auparavant.
J'ai également vu le code qui utilise un min-heap, déqueues à l'arrière, puis fait une inversion O (n) du tableau, après le processus. Je n'ai jamais compris pourquoi le programmeur l'a écrit de cette façon. Généralement, j'ai vu le max-heap utilisé. Oh, et j'ai * vu * la méthode "min-tas à l'arrière" utilisée. Encore une fois, je ne sais pas pourquoi il l'a fait de cette façon. –
Merci beaucoup @templatetypedef et @ jim-mischel! –