Files d'attente Heapsort et Priority

Cette séance de cours couvre l'algorithme Heapsort, qui construit un max-heap à partir d'un tableau et le trie en O (n log n) temps. Il explique comment Heapsort fonctionne en rejetant à plusieurs reprises l'élément maximum. La séance de cours présente également des files d'attente prioritaires, des ensembles dynamiques d'éléments avec des valeurs associées et des opérations telles que INSERT, HEAP-MAXIMUM, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY et MAX-HEAP-INSERT. L'instructeur compare Heapsort à quicksort et souligne que même si Heapsort est efficace, quicksort est généralement plus rapide dans la pratique. En outre, la séance de cours montre comment les tas peuvent être utilisés pour implémenter efficacement les files d'attente prioritaires.