¿Es posible heapify un árbol binario a un montón sin usar array?

Convertir un árbol en un montón es un problema interesante. Cuando utiliza una matriz, comienza en la matriz [n / 2] y avanza hasta la matriz [0]. Esto es esencialmente una construcción ascendente del montón.

Con un árbol, no podemos simplemente saltar al nodo en el índice n / 2. Simplemente no hay una manera eficiente de saltar a nodos de árbol arbitrarios por su índice de arriba a abajo, de izquierda a derecha.

Entonces tenemos que ser un poco creativos. Los algoritmos de árboles tienden a ser algoritmos recursivos, por lo que es un buen lugar para comenzar. Si queremos imitar el algoritmo de heapify, sabemos que necesitamos construir el montón de abajo hacia arriba. Una construcción de abajo hacia arriba significa que estamos haciendo la construcción en el camino desde la recursividad. Esto significa que cualquier código de construcción de montón que tengamos debe venir después de nuestras llamadas recursivas.

• ¿Por qué los conjuntos en Python tienen una complejidad algorítmica de O (1)?
• En lugar de usar una matriz y ordenar elementos de mayor a menor, ¿cómo puedo usar un montón?
• ¿Cuál es una explicación fácil de entender del algoritmo de Reddit?
• ¿Cómo se calcula el PageRank? ¿Cuál fue el PageRank inicial? ¿Cómo comienza el algoritmo?
• Si arr es una matriz de enteros, ¿por qué la expresión ar ++ no es legal?

Esto termina siendo un simple algoritmo de divide y vencerás: para un nodo dado, heapify el árbol enraizado en el hijo izquierdo, heapify el árbol enraizado en el hijo derecho, y luego burbujea hacia abajo el nodo actual (según sea necesario) para que el árbol enraizado en el nodo actual satifica la propiedad de almacenamiento dinámico mínimo.

Esto se ve así:

import java.util.ArrayDeque;
import java.util.Queue;

Solución de clase {
public static void main (String [] args) {
BinaryTreeNode A = new BinaryTreeNode (5);

BinaryTreeNode B = new BinaryTreeNode (2);
BinaryTreeNode C = new BinaryTreeNode (28);

BinaryTreeNode D = new BinaryTreeNode (16);
BinaryTreeNode E = new BinaryTreeNode (4);
BinaryTreeNode F = new BinaryTreeNode (2);
BinaryTreeNode G = new BinaryTreeNode (39);

BinaryTreeNode H = new BinaryTreeNode (88);
BinaryTreeNode I = new BinaryTreeNode (98);

A. izquierda = B;
A.derecho = C;

B. izquierda = D;
B.derecho = E;
C. izquierda = F;
C.derecho = G;
D. izquierda = H;
D.right = I;

heapifyTree (A);
printLevelByLevel (A);
}

public static <T extend Comparable > void heapifyTree (raíz BinaryTreeNode ) {
if (root == null) {
regreso;
}

heapifyTree (root.left);
heapifyTree (root.right);
bubbleDown (raíz);
}

privado estático <T se extiende Comparable > void bubbleDown (nodo BinaryTreeNode ) {
BinaryTreeNode smallestNode = nodo;

if (node.left! = null && node.left.value.compareTo (node.value) <0) {
smallestNode = node.left;
}

if (node.right! = null && node.right.value.compareTo (node.value) <0) {
smallestNode = node.right;
}

if (smallestNode! = nodo) {
swapNodeValues ​​(nodo, smallestNode);
bubbleDown (el nodo más pequeño);
}
}

private static <T extend Comparable > void swapNodeValues ​​(BinaryTreeNode a, BinaryTreeNode b) {
T temp = a.value;
a.value = b.value;
b.value = temp;
}

public static <T extend Comparable > void printLevelByLevel (raíz BinaryTreeNode ) {
if (root == null) {
regreso;
}

Queue <BinaryTreeNode > toVisit = new ArrayDeque ();
toVisit.add (raíz);

while (! toVisit.isEmpty ()) {
BinaryTreeNode nodo = toVisit.poll ();
System.out.println (node.value);

if (node.left! = null) {
toVisit.add (nodo.izquierda);
}

if (node.right! = null) {
toVisit.add (node.right);
}
}
}

clase estática privada BinaryTreeNode <T extiende Comparable > {
Valor T;
BinaryTreeNode left;
BinaryTreeNode derecha;

public BinaryTreeNode (valor T) {
this.value = value;
}
}
}