Max-Heapify Un Arbre Binaire
C'est l'une des questions d'entrevue que j'ai récemment rencontrées.
étant donné l'adresse racine d'un arbre binaire complet ou presque complet, nous devons écrire une fonction pour convertir l'arbre en max-heap.
il n'y a pas de tableaux impliqués ici. L'arbre est déjà construit.
Par exemple,
1
/
2 5
/ /
3 4 6 7
peut avoir les éventuelles max tas comme l' 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 traverses avant et après l'ordre mais qui je suppose s'exécute en O (N^2). Mon code donne la sortie suivante.
7
/
3 6
/ /
1 2 4 5
je cherchais 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;
}
3 réponses
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 y ait un élément dans l'arbre dont les sous-arbres gauche et droit sont en tas.
E
H1 H2
cet arbre formé par E, H1 et H2 peut être reconstitué dans le temps logN en faisant glisser L'élément E jusqu'à sa position correcte.
par conséquent, nous commençons à 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).
Je ne sais pas comment faire si vous ne pouvez pas accéder facilement au noeud parent ou aucune représentation du tableau, si vous pouvez traverser l'arbre pour l'enregistrer ref dans un tableau(O(N)), alors cela devient 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 O(N*LogN).
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;
}
}