Find the largest MinHeap subtree in a given Tree

Question

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.

Answer 1

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.

Answer 2

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.