logo标签列表

最大堆化二叉树

algorithmdata-structuresheapbinary-treebinary-heap
11

这是我最近遇到的一道面试题。

给定完整或几乎完整二叉树的根地址，我们必须编写一个将树转换为最大堆的函数。

这里没有涉及任何数组。树已经构建好了。

例如，

              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);
    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;
}
1
你展示的“二叉树”是一个最小堆，而不是一个排序的二叉树。这是你的意图吗？ - Sneftel
@Sneftel 你好！它恰好是一个小根堆。这不是有意为之的，可以是任何随机完全或几乎完全的二叉树。 - discoverAnkit
1
这里没有涉及到数组 - 这是指你不能将树复制到数组中，然后进行堆化，还是仅仅意味着你最初没有将树作为数组存在？如果是后者，则可以将其复制到数组中，进行堆化，重建树；这样的时间复杂度为O(n)。 - G. Bach
1
@G.Bach 是的，您不允许将树复制到数组中，然后进行堆化操作，也不是最初就将树作为数组。它是一棵二叉树，而不是数组的二叉树可视化。 - discoverAnkit
4个回答
6
我认为可以通过以下步骤在O（NlogN）时间内完成此操作。
假设树中有一个元素，它的左右子树都是堆。 http://www.cs.rit.edu/~rpj/courses/bic2/studios/studio1/studio121.html 
          E
       H1   H2

通过将元素 E 下沉到正确的位置，由 E、H1 和 H2 形成的这棵树可以在 logN 的时间内堆化。

因此，我们从底部向上构建堆。进入最左边的子树并通过简单比较将其转换为堆。对于它的兄弟也是如此。然后向上转换为堆。

依此类推，对每个元素进行相同的操作。

编辑：正如评论中提到的，复杂度实际上是 O(N)。

前往最左子树？那么，我们需要使用额外的空间通过层序遍历来存储非叶节点的地址吗？ - discoverAnkit
1
@ankitG 不需要，只需要log(N)的堆栈空间来递归左右子节点。定义一个“heapify”过程，首先在当前节点的左右子节点上递归调用自身（如果有的话），然后将当前节点向下移动到其适当的位置。这是在数组上使用的相同线性时间算法。 - Erik P.
3
我认为这里的复杂度分析不正确。如果你以树的高度H为思考角度，你会得到O(H)=2*O(H-1)+H的结果，其中(1)是将两个子树变成堆，(2)是将根节点向下移动到它的位置。这表明O(H)=2^H，因此O(N)=N。 - Steve D
1
@SteveD 是正确的。如果您正确实现，时间复杂度将为O(N)。您应该能够将额外空间（递归堆栈深度）限制为O(log n)。 - Jim Mischel
2

如果无法轻松访问父节点或没有数组表示，则我不知道该如何操作，如果您可以遍历树并在数组中记录其引用（O（N）），则变得简单。

        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

就是这样！复杂度应该为O(N*LogN)。

谢谢！是的！我也对在这种情况下访问父节点感到怀疑，但看起来我们必须通过层次遍历使用额外的空间来存储非叶节点的地址。 - discoverAnkit
但是如果我们必须使用数组（O（N）），为什么不将二叉树存储在数组中，然后在O（n）中进行堆化呢？我的解决方案可能需要O（n ^ 2）的时间，并且不使用额外的空间。 - discoverAnkit
@ankitG 我认为heapify的时间复杂度应该是O（NlogN），因为你需要检查所有具有子节点的节点。 - Gohan
0
我认为你可以通过修改postOrderTraverse方法轻松地得到一个工作。这是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;
}

}
2
交换完成后，您需要再次检查子树是否仍然是堆。 - Robert Dolca
0
这是一个解决此问题的可行代码。
package Test;


import static Test.BinaryTreeNode.swap;

public class TestImplementations {
    public static void main(String args[]){
        BinaryTreeNode root = new BinaryTreeNode(2,
                new BinaryTreeNode(7,
                        new BinaryTreeNode(5,
                                new BinaryTreeNode(1),new BinaryTreeNode(6)),
                        new BinaryTreeNode(9,
                                new BinaryTreeNode(17))),
                new BinaryTreeNode(3,
                        new BinaryTreeNode(11),new BinaryTreeNode(4))
                );
        System.out.println(root);
        CustomHeap h = new CustomHeap();
        h.minHeapify(root);
        System.out.println(root);
    }
}

class BinaryTreeNode {
    private  Integer value;
    private  BinaryTreeNode left;
    private  BinaryTreeNode right;

    public BinaryTreeNode(Integer value){
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public BinaryTreeNode(Integer value, BinaryTreeNode left){
        this.value = value;
        this.left = left;
        this.right = null;
    }

    public BinaryTreeNode(Integer value, BinaryTreeNode left, BinaryTreeNode right){
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Integer getValue() {
        return value;
    }

    public BinaryTreeNode getLeft() {
        return left;
    }

    public BinaryTreeNode getRight() {
        return right;
    }

    public static void swap(BinaryTreeNode r, BinaryTreeNode c){
        Integer val = r.getValue();
        r.value = c.getValue();
        c.value = val;
    }
}

class CustomHeap {
    public void minHeapify(Test.BinaryTreeNode r){
        if( r == null || (r.getLeft() == null && r.getRight() == null)){
            return;
        }
        minHeapify(r.getLeft());
        minHeapify(r.getRight());
        if(isMin(r,r.getLeft())){
            swap(r,r.getLeft());
            minHeapify(r.getLeft());
        }
        if(r.getRight() !=null && isMin(r,r.getRight())){
            swap(r,r.getRight());
            minHeapify(r.getRight());
        }
    }

    private Boolean isMin(Test.BinaryTreeNode r, Test.BinaryTreeNode c){
        return c.getValue() < r.getValue() ? Boolean.TRUE : Boolean.FALSE;
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接