algorithm - datos - Max-Heapify Un árbol binario
heap estructura de datos (3)
Esta es una de las preguntas de la entrevista que encontré recientemente.
Dada la dirección raíz de un árbol binario completo o casi completo, tenemos que escribir una función para convertir el árbol a un montón máximo.
No hay matrices involucradas aquí. El árbol ya está construido.
Por ejemplo,
1
/ /
2 5
/ / / /
3 4 6 7
puede tener cualquiera de los posibles montones máximos como salida--
7
/ /
3 6
/ / / /
2 1 4 5
o
7
/ /
4 6
/ / / /
2 3 1 5
etc ...
Escribí una solución pero usando una combinación de recorridos pre y post orden, pero creo que se ejecuta en O (n ^ 2). Mi código da el siguiente resultado.
7
/ /
3 6
/ / / /
1 2 4 5
Estaba buscando una mejor solución. ¿Alguien puede ayudarme?
Editar:
Mi código
void preorder(struct node* root)
{
if(root==NULL)return;
max_heapify(root,NULL);
preorder(root->left);
preorder(root->right);
}
void max_heapify(struct node* root,struct node* prev)
{
if(root==NULL)
return ;
max_heapify(root->left,root);
max_heapify(root->right,root);
if(prev!=NULL && root->data > prev->data)
{
swapper(root,prev);
}
}
void swapper(struct node* node1, struct node* node2)
{
int temp= node1->data;
node1->data = node2->data;
node2->data = temp;
}
Creo que esto se puede hacer en el tiempo O (NlogN) con el siguiente procedimiento. http://www.cs.rit.edu/~rpj/courses/bic2/studios/studio1/studio121.html
Suponga que hay un elemento en el árbol cuyos subárboles izquierdo y derecho son montones.
E
H1 H2
Este árbol formado por E, H1 y H2 puede heapificarse en tiempo logN haciendo que el elemento E llegue a su posición correcta.
Por lo tanto, comenzamos a construir el montón de abajo hacia arriba. Vaya al subárbol situado más a la izquierda y conviértalo en un montón por comparación trivial. Haz esto porque es hermano también. Luego sube y conviértelo en montón.
De la misma manera haz esto por cada elemento.
EDITAR: Como se mencionó en los comentarios, la complejidad es en realidad O (N).
Creo que puedes obtener un trabajo simplemente revisando postOrderTraverse. Esto es O (n)
void Heapify_Min(TreeNode* node)
{
if(! = node) return;
Heapify_Min(node->left);
Heapify_Min(node->right);
TreeNode* largest = node;
if(node->left && node->left->val > node->val)
largest = node->left;
if(node->right && node->right->val > node->val)
largest = node->right;
if(largest != node)
{
swap(node, largest)
}
}
void swap(TreeNode* n1, TreeNode* n2)
{
TreeNode* temp = n1->left;
n1->left = n2->left;
n2->left =temp;
temp = n1->right;
n1->right = n2->right;
n2->right = temp;
}
}
No sé el camino si no puede acceder fácilmente al nodo padre o no hay representación de matriz, si puede recorrer el árbol para registrarlo ref en una matriz (O (N)), entonces se vuelve simple.
1
/ /
2 5
/ / / /
3 4 6 7
from the last parent node to the root node(in your case 5,2,1:
for each node make it compare to their children:
if children is larger than parent, swap parent and children:
if swapped: then check the new children''s childrens utill no swap
1
/ /
2 7
/ / / /
3 4 6 5 check [7] 5<-->7
1
/ /
4 7
/ / / /
3 2 6 5 check [2] 4<-->2
7
/ /
4 1
/ / / /
3 2 6 5 check [1] 7<-->1
7
/ /
4 6
/ / / /
3 2 1 5 check [1] 6<-->1
¡Eso es! La complejidad debe ser O (N * LogN).