Max-Heapify Un arbre binaire

C'est l'une des questions pour l'interview j'ai récemment est venu à travers.

Compte tenu de la racine de l'adresse complète ou presque complète arbre binaire, nous devons écrire une fonction pour convertir l'arbre jusqu'à un max-heap.

Il n'y a pas de tableaux en cause ici. L'arbre est déjà construit.

Pour, par exemple,

              1   
         /        \
        2           5
      /  \       /  \ 
     3      4    6     7

peut avoir les éventuelles max tas comme la sortie--

              7   
         /        \
        3           6
      /  \       /  \ 
     2     1     4     5

ou

              7   
         /        \
        4           6
      /  \       /  \ 
     2     3     1     5

etc...

J'ai écrit une solution, mais en utilisant une combinaison de pré-et post-ordre traversals mais qui, je pense, s'exécute en O(n^2). Mon code donne le résultat suivant.

              7   
         /        \
        3           6
      /  \       /  \ 
     1     2     4     5

J'étais à la recherche d'une meilleure solution. Quelqu'un peut-il aider s'il vous plaît?

Edit :

Mon Code

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

source d'informationauteur ankitG

  1. 5

    Je pense que cela peut être fait en O(NlogN) de temps de la procédure suivante.
    http://www.cs.rit.edu/~rpj/courses/bic2/studios/studio1/studio121.html

    Supposons qu'il existe un élément dans l'arbre dont les deux de droite et de gauche sous-arbres sont des tas. 

              E
       H1   H2

    Cet Arbre formé par E, H1 et H2 peuvent être heapified dans logN temps en faisant de l'élément E de nager jusqu'à sa position correcte.

    Par conséquent, nous avons commencer à construire le tas de bas en haut. Goto la plus à gauche du sous-arbre et de le convertir à un segment par comparaison triviale. Le faire pour son frère. Montez ensuite le convertir en tas.

    Que faire pour chaque élément.

    EDIT: Comme mentionné dans les commentaires, la complexité est en fait O(N).

  2. 2

    Je ne sais pas le chemin si vous ne pouvez pas accéder au nœud parent facilement ou pas de la matrice de la représentation, si vous pouvez parcourir l'arborescence de l'enregistrer ref dans un array(O(N)), alors il deviendra 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

    C'est elle!
    La complexité doit être en O(N*LogN).

  3. 0

    Je pense que vous pouvez en obtenir un travail simplement par la révision de postOrderTraverse. Ce est 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;
}

}