0
$\begingroup$

We are given a rooted tree $T$ of distinct Natural numbers. The goal is to find the largest subtree of $T$ that has MinHeap property. In fact, we want to calculate the largest subset $S$ of nodes, in a way that all nodes in $S$ have a common ancestor in $S$, and any ancestor of $n \in S$ that appeared in $S$ has a smaller value than $n$.

I can solve this problem by DP in $O(n^2)$ time, but I want to know if there is an algorithm to solve it in $O(n \log n)$ time?

For the $O(n^2)$ solution we can use the $DP$ technique. First of all, we maintain a sorted array of nodes, named $nums[n]$, then we define the array $DP[n][n]$.

$DP[i][j]$ maintains the solution for the subtree rooted by $i$, such that the biggest number in the solution is less than or equal to $nums[j]$. In this manner, we can dynamically full the DP by traversing the tree from bottom to top.

$\endgroup$
5
  • $\begingroup$ Is there any assumption about the structure of $T$ and should $S$ be balanced/complete, or is it just the heap-order property? $\endgroup$
    – Russel
    Apr 18, 2022 at 15:39
  • $\begingroup$ There is not any other assumption, it is just the heap-order property. $\endgroup$
    – R.hatam
    Apr 18, 2022 at 15:59
  • $\begingroup$ Can you put in this post your $O(n^2)$ algorithm? $\endgroup$
    – Russel
    Apr 18, 2022 at 16:05
  • $\begingroup$ Of course, I post the $O(n^2)$ algorithm. $\endgroup$
    – R.hatam
    Apr 18, 2022 at 16:28
  • $\begingroup$ You can actually just edit your question to include your solution instead of posting it as an answer $\endgroup$
    – Russel
    Apr 18, 2022 at 16:31

2 Answers 2

2
$\begingroup$

I think this can be done quite easily in linear time: a heap is an almost complete tree that satisfies the heap property.

An almost complete tree is one of the following:

  • a leaf (a single node);
  • a node with a left child that is a single node and no right child;
  • a node with a left child $\ell$ of height $h_{\ell}$ and a right child $r$ of height $h_r$ such that one of the following is true:
    • $\ell$ and $r$ are both perfect trees and $h_{\ell} -1 \leqslant h_r \leqslant h_{\ell}$;
    • $\ell$ is a perfect tree and $r$ is an almost complete tree and $h_r = h_{\ell}$;
    • $r$ is a perfect tree and $\ell$ is an almost complete tree and $h_r = h_{\ell} -1$.

Now you can compute recursively, for each node of the tree:

  • its size;
  • its height;
  • whether it is perfect or not;
  • whether it is almost complete or not;
  • whether it verifies the heap property or not.

For a given node, if you know those informations for its children, you can compute those informations for the node in constant time. You can also keep track of the biggest subtree that is a min-heap. All this is done in linear time.

$\endgroup$
2
  • $\begingroup$ Apologies, I forget to consider the details of the question. $\endgroup$
    – R.hatam
    Apr 18, 2022 at 14:24
  • $\begingroup$ The same kind algorithm can be used (you only need to compute the size and whether it verifies the heap property or not). $\endgroup$
    – Nathaniel
    Apr 18, 2022 at 14:29
1
$\begingroup$

Perform a level order traversal of $T$, and store the visited nodes in an array $A$.

Let $S$ be an array such that $S[i]$ is the size of the min-heap rooted at node $A[i]$. Initially the values of all indices is 1. This implies that initially, there are $n$ individual min-heap ordered subtree. These subtrees will be merged later when possible to obtain larger subtrees. This in effect increases the value stored in the corresponding indices of $S$.

Let $s_{max}$ be the index of $S$ that contains the largest value. Initially $s_{max} = -1$.

Iterate over the contents of $A$ in reverse. This guarantees that nodes are accessed from the bottom to top. For each node $A[i]$, check each of its children. If child $A[j] \gt A[i]$, then it is possible to merge the subtree rooted at node $A[j]$ as child of node $A[i]$. This means that the size of subtree rooted at $A[j]$ must be added to the size of the subtree rooted at $A[i]$, so add $S[j]$ to $S[i]$. Update $s_{max}$ when necessary.

Once the iteration is done, use the contents of the arrays and $s_{max}$ to construct the largest min-heap ordered subtree of $T$.

The running-time will be $O(n)$ for the traversal. As noted in the comment, the iteration basically checks the children of all nodes, which amounts to checking all the child links in the tree. Since there are $n-1$ child links in a tree with $n$ nodes and checking a child takes $O(1)$ time, the entire iteration takes $O(n)$ time. Construction of the subtree is at most the cost of the iteration. The entire procedure therefore, takes $O(n)$ time.

$\endgroup$
5
  • $\begingroup$ I think that $\mathcal{O}(nb)$ is a too large upper bound: the right bound would be $\mathcal{O}\left(\sum\limits_{x\text{ node}}\text{number of children of }x\right) = \mathcal{O}(n)$ because a tree of size $n$ has $n-1$ children in total. $\endgroup$
    – Nathaniel
    Apr 18, 2022 at 20:51
  • $\begingroup$ Thank both of you very much. $\endgroup$
    – R.hatam
    Apr 18, 2022 at 22:05
  • $\begingroup$ @Nathaniel is the $n-1$ the number of edges in the tree? I did forgot about that and that will actually give a better bound. $\endgroup$
    – Russel
    Apr 19, 2022 at 0:09
  • $\begingroup$ I updated my answer to reflect this analysis. $\endgroup$
    – Russel
    Apr 19, 2022 at 2:04
  • $\begingroup$ @Russel $n-1$ is both the number of edges and the number of children (every node is a children except for the root of the tree). $\endgroup$
    – Nathaniel
    Apr 19, 2022 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.