Heapsort swap en utilisant le tri par insertion?

Question

Est-il possible d'utiliser le tri par insertion dans un heapsort pour remplacer sa méthode d'échange ou d'échange?

permuter En général requres 3 étapes au minimum:

temp = a 
a = b 
b = temp 

Un de mes amis a dit qu'il est possible d'utiliser le tri par insertion pour réduire l'échange à une seule opération au lieu de trois. Est-ce?

Answer 1

Je pense que ce qu'il veut dire peut-être que lorsque vous dépassez (ou augmentez) un élément dans un tas, vous ne stockez pas cet élément jusqu'à ce que vous trouviez où il est supposé aller. En tant que tel, il n'y a qu'une seule opération par échange: stocker le plus petit élément dans sa nouvelle position dans le tas. Le processus s'apparente au processus dans un tri d'insertion lorsque vous déplacez un élément vers son emplacement trié au début du tableau.