Así que he estado tratando de implementar Max Heap. El uso que le quiero dar es que, en un momento dado, quiero que los 3 primeros elementos del montón (es decir, la raíz y sus dos hijos) sean siempre los más altos de todo el montón.

Pensé que la propiedad heap garantizaría esto, pero ni un solo ejemplo de implementación que he encontrado ha podido resolver el hecho de que, a veces, hay elementos en un nivel del montón que son más bajos que un elemento en un nivel superior. Esta es la implementación que he estado usando, básicamente usando ejemplos que he encontrado en Internet como referencia:

 let createHeap = function(){ return { arr:[], size: 0, getParent: function(i) { return Math.floor((i-1)/2) }, getLeft: function(i) { return (2*i + 1) }, getRight: function(i) { return (2*i + 2) }, insert: function(val){ let i = this.size this.size++ this.arr[i] = val; if(i!=0){ for(let j = this.getParent(i);j>=0;j--){ this.heapify(j) } } }, heapify: function(i){ let largest = i; let leftIndex = this.getLeft(i) let rightIndex = this.getRight(i) if (leftIndex < this.size && this.arr[leftIndex] > this.arr[largest]) largest = leftIndex if (rightIndex < this.size && this.arr[rightIndex] > this.arr[largest]) largest = rightIndex; if (largest != i) { let temp = this.arr[largest]; this.arr[largest] = this.arr[i] this.arr[i] = temp this.heapify(largest); } } } }

Ahora, el problema es que cuando inserto los siguientes valores en este orden: 1, 2, 3, 4, 5 el resultado que obtengo para el montón es:

 5 |\ 4 2 |\ 1 3

Esto es claro cuando lee lo que hace el código, pero no parece conservar la propiedad del montón en la medida en que entendí qué significa la propiedad del montón. Al código le falta algo para hacer lo que quiero que haga, pero no quiero implementar cambios que aumenten demasiado la complejidad, así que quería preguntar:

1. ¿Alguien sabe si la implementación es incorrecta o si nunca tuvo la intención de hacer lo que quiero que haga? (los primeros 3 elementos del montón son siempre los más altos de todo el montón)
2. ¿Cuál sería la mejor manera de implementar esto sin aumentar demasiado la complejidad?