Skip to main content
added 60 characters in body
Source Link
Russel
  • 2.8k
  • 1
  • 8
  • 16

Let $b$ be a constant that gives the maximum number of children any node in $T$ can have. I assume here that $T$ is represented as a linked structure.

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 obtainconstruct the largest min-heap ordered subtree of $T$.

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

Let $b$ be a constant that gives the maximum number of children any node in $T$ can have. I assume here that $T$ is represented as a linked structure.

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 obtain the largest min-heap ordered subtree of $T$.

The running-time will be $O(n)$ for the traversal. And $O(nb)$ for the entire iteration. Since $b$ is constant the running time is $O(n)$. Construction of the subtree is at most the cost of the iteration. So the total time is $O(n)$.

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.

Source Link
Russel
  • 2.8k
  • 1
  • 8
  • 16

Let $b$ be a constant that gives the maximum number of children any node in $T$ can have. I assume here that $T$ is represented as a linked structure.

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 obtain the largest min-heap ordered subtree of $T$.

The running-time will be $O(n)$ for the traversal. And $O(nb)$ for the entire iteration. Since $b$ is constant the running time is $O(n)$. Construction of the subtree is at most the cost of the iteration. So the total time is $O(n)$.