MAX_HEAPIFY mise en œuvre

Question

J'écrit le code JavaScript pour construire un maximum heapify qui maintient la propriété max-tas, mais j'ai beaucoup de questions concernant la mise en œuvre:

tableau

I test sur: [1, 2, 3, 4 , 7, 8, 9, 10, 14, 16]

quand je test sur le réseau quand il est triée je suis:

[16, 14, 9, 10, 7, 8 , 3, 1, 4, 2]

Alors que je unsorted obtenu:

[16, 14, 8, 9, 10, 2, 3, 4, 7, 1]

Pourquoi ou pourquoi pas est le maxi- Heapify affecté par le tableau en cours de tri?

je trouve que, lorsque le tableau est trié la solution est la suivante:

[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

Pourquoi Ai-je obtenu une solution différente lorsque le tableau est trié, même si je trouve que ma mise en œuvre est correcte selon le pseudocode de CLRS?

Pourriez-vous spécifier une autre procédure qui n'utilise pas la récursivité tout en obtenant la même fonctionnalité?

function BuildMaxHeap(array){ 
for(var i = Math.floor(array.length/2); i >= 0; i--){ 
    MAX_HEAPIFY(array, i); 
} 
return array; 
} 

function MAX_HEAPIFY(array, i) { 
var left = 2 * i + 1; 
var right = 2 * i + 2; 
var largest = i; 
if(left <= array.length && array[left] > array[largest]){ 
    largest = left; 
    } 
if(right <= array.length && array[right] > array[largest]){ 
    largest = right; 
} 
if(largest != i){ 
    var temp = array[i]; 
    array[i] = array[largest]; 
    array[largest] = temp; 
    MAX_HEAPIFY(array, largest); 
} 
} 

Answer 1

Comme vous l'avez remarqué, les tas min/max créés à partir d'un ensemble de nombres peuvent avoir plusieurs configurations de leurs feuilles en fonction de l'ordre dans lequel ils sont insérés.

Vous pourriez penser que ce «classement global» des feuilles peut provenir d'un comportement émergent de la propriété de segment de mémoire sous-jacente, mais un tableau donné n'a pas de correspondance biunivoque avec une configuration particulière. Cela se produit en raison de la façon dont un enfant est inséré et barboté (permuté avec les parents), qui s'arrêtera dès qu'il est plus petit que son parent - dont il peut y avoir plusieurs candidats valides pour un poste dans le tas.

Cela m'avait dérouté quand j'ai aussi mis en place un tas.

Answer 2

Question intéressante;

juste pour être sûr,

function buildMaxHeap(array){ 
return array.sort((a,b)=>b-a); 
} 

retourne également un tableau valide.

Puisque le but est seulement de fournir un arbre où

• racine a une valeur maximale Touche
• stockée à une non-racine est au plus la valeur de son parent
• tout chemin de la racine à la feuille est pour non-augmentation
• sous-arbres gauche et droite ne sont pas liés

(http://www.cs.toronto.edu/~krueger/cscB63h/w07/lectures/tut02.txt)

L'algorithme permute les parents et les enfants jusqu'à ce que ces 4 conditions soient remplies, donc oui, si vous commencez avec un tableau différent, la sortie peut également être différente.

Du point de vue CodeReview:

• MAX_HEAPIFY -> JavaScript suit lowerCamelCase, donc maxHeapify
• Votre empreinte est éteint, essayez d'utiliser quelque chose comme http://jsbeautifier.org/
• pourquoi appeler une fonction MAX_HEAPIFY et l'autre BuildMaxHeap, ces noms se ressemblent et ne disent pas au lecteur ce qu'ils font.

À part cela, il n'y a pas grand chose à dire.