最大化加密二叉树 [英] Max-Heapify A Binary Tree
问题描述
这是我最近遇到的面试问题之一。
给定完整或几乎完整的二叉树的根地址,我们必须编写一个函数将树转换为最大堆。
这里没有涉及到数组。树已经建成。
例如,
1
/ \
2 5
/ \ / \
3 4 6 7
可以有任何可能的最大堆作为输出 -
7
/ \
3 6
/ \ / \
2 1 4 5
或
7
/ \
4 6
/ \ / \
2 3 1 5
等...
我写了一个解决方案,但是使用前后顺序遍历的组合,但是我猜在O(n ^ 2)中运行。我的代码给出以下输出。
7
/ \
3 6
/ \ / \
1 2 4 5
我正在寻找一个更好的解决方案。有人可以帮忙吗?
编辑:
我的代码
void preorder(struct node * root)
{
if(root == NULL)return;
max_heapify(root,NULL);
预订(root->左);
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&&> 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;
}
我认为这可以完成在O(NlogN)时间通过以下过程。
http://www.cs。 rit.edu/~rpj/courses/bic2/studios/studio1/studio121.html
假设树中有一个元素在左边和右边亚树是堆积的。
E
H1 H2
由E,H1和H2形成的树可以通过使元素E游泳到正确的位置,在logN时间内堆积。
<因此,我们从底部开始构建堆。转到最左侧的子树,并通过琐碎的比较将其转换成堆。做这个也是兄弟姐妹。然后上去把它转换成堆。
对于每个元素都是这样做的。
编辑:如意见中所述,复杂性实际上是O(N)。
This is one of the interview questions I recently came across.
Given the root address of a complete or almost complete binary tree, we have to write a function to convert the tree to a max-heap.
There are no arrays involved here. The tree is already constructed.
For e.g.,
1
/ \
2 5
/ \ / \
3 4 6 7
can have any of the possible max heaps as the output--
7
/ \
3 6
/ \ / \
2 1 4 5
or
7
/ \
4 6
/ \ / \
2 3 1 5
etc...
I wrote a solution but using a combination of pre and post order traversals but that I guess runs in O(n^2). My code gives the following output.
7
/ \
3 6
/ \ / \
1 2 4 5
I was looking for a better solution. Can somebody please help?
Edit :
My 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;
}
I think this can be done in O(NlogN) time by the following procedure. http://www.cs.rit.edu/~rpj/courses/bic2/studios/studio1/studio121.html
Assume there is an element in the tree whose both left and right sub-trees are heaps.
E
H1 H2
This Tree formed by E, H1 and H2 can be heapified in logN time by making the element E swim down to its correct position.
Hence, we start building the heap bottom up. Goto the left-most sub-tree and convert it to a heap by trivial comparison. Do this for it's sibling as well. Then go up and convert it to heap.
Like-wise do this for every element.
EDIT: As mentioned in the comments, the complexity is actually O(N).
这篇关于最大化加密二叉树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!