algorithm - datos - Max-Heapify Un árbol binario

heap estructura de datos

Question

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;
}

Answer 1

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).

Answer 2

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;
}

}

Answer 3

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).