最大化加密二叉树 [英] 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屋！