Analyse du pire cas de Heapsort, exactement

Résumé Cet article complète l'analyse du temps d'exécution dans le pire des cas de Heapsort mesuré par le nombre de comparaisons de clés effectuées lors du tri. Une dérivation d'une formule exacte pour le nombre maximum de comparaisons de clés effectuées par Heapsort sur n'importe quel tableau de taille N 2 est présentée. Il est égal à align N 2 ^ N - 4 \\4pt 0 sinon. tableau. align La formule ci-dessus permet de décider, en O (N N) temps, si un tableau à N éléments donné est un tableau de pire cas pour Heapsort. Sa preuve fournit un algorithme pour la construction, en O (N N) temps, de tableaux de pire cas de tailles arbitraires N 2 pour Heapsort.