Mixing
MAX-HEAPIFY - why the worst case is when the bottom level is “half full”?
$begingroup$
In the 3rd edition of 'Introduction to Algorithms', on page 155, when analysing MAX-HEAPIFY it says:
The children's subtrees each have size at most 2n/3 - the worst case
occurs when the last row of the tree is exactly half full.
I know how 2n/3 comes. However,
Can anyone please explain to me how
"the worst case occurs when the last row of the tree is exactly half full"?
Why half full? Why not full tree?
Thank you!
analysis algorithms
edited May 27 '14 at 15:20
Weipeng Huang
31
asked May 7 '14 at 9:39
SoniaSonia
6
$endgroup$
add a comment |
$begingroup$
In the 3rd edition of 'Introduction to Algorithms', on page 155, when analysing MAX-HEAPIFY it says:
The children's subtrees each have size at most 2n/3 - the worst case
occurs when the last row of the tree is exactly half full.
I know how 2n/3 comes. However,
Can anyone please explain to me how
"the worst case occurs when the last row of the tree is exactly half full"?
Why half full? Why not full tree?
Thank you!
analysis algorithms
edited May 27 '14 at 15:20
Weipeng Huang
31
asked May 7 '14 at 9:39
SoniaSonia
6
$endgroup$
add a comment |
$begingroup$
In the 3rd edition of 'Introduction to Algorithms', on page 155, when analysing MAX-HEAPIFY it says:
The children's subtrees each have size at most 2n/3 - the worst case
occurs when the last row of the tree is exactly half full.
I know how 2n/3 comes. However,
Can anyone please explain to me how
"the worst case occurs when the last row of the tree is exactly half full"?
Why half full? Why not full tree?
Thank you!
analysis algorithms
edited May 27 '14 at 15:20
Weipeng Huang
31
asked May 7 '14 at 9:39
SoniaSonia
6
$endgroup$
In the 3rd edition of 'Introduction to Algorithms', on page 155, when analysing MAX-HEAPIFY it says:
The children's subtrees each have size at most 2n/3 - the worst case
occurs when the last row of the tree is exactly half full.
I know how 2n/3 comes. However,
Can anyone please explain to me how
"the worst case occurs when the last row of the tree is exactly half full"?
Why half full? Why not full tree?
Thank you!
analysis algorithms
analysis algorithms
edited May 27 '14 at 15:20
Weipeng Huang
31
asked May 7 '14 at 9:39
SoniaSonia
6
edited May 27 '14 at 15:20
Weipeng Huang
31
asked May 7 '14 at 9:39
SoniaSonia
6
edited May 27 '14 at 15:20
Weipeng Huang
31
edited May 27 '14 at 15:20
Weipeng Huang
31
edited May 27 '14 at 15:20
Weipeng Huang
31
31
asked May 7 '14 at 9:39
SoniaSonia
6
asked May 7 '14 at 9:39
SoniaSonia
6
asked May 7 '14 at 9:39
SoniaSonia
6
6
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
As you add more elements to the last row, you balance out the size of the two children subtrees, and thus push the proportion of elements in any one child to $1/2$.
You could always just do an algebraic calculation rather than "thinking it out", though:
- Let there be $k$ elements in the last row
- Compute the size of the largest child
- Find the maximum of the result from the previous step
answered May 27 '14 at 15:26
HurkylHurkyl
112k9120262
$endgroup$
add a comment |
$begingroup$
Even if the tree is complete binary tree, the no. of nodes in both the sub-trees (left and right of node i) will be bounded by 2n/3. Since the algorithm will choose one of the sub tree of node i, it will not matter which sub-tree it chooses. The thing that matter is that sub-tree must be maximum size and since the size of max nodes subtree is bounded by 2n/3 we will get the same recurrence equation.
answered Aug 9 '16 at 20:07
xyzxyz
1
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f784787%2fmax-heapify-why-the-worst-case-is-when-the-bottom-level-is-half-full%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As you add more elements to the last row, you balance out the size of the two children subtrees, and thus push the proportion of elements in any one child to $1/2$.
You could always just do an algebraic calculation rather than "thinking it out", though:
- Let there be $k$ elements in the last row
- Compute the size of the largest child
- Find the maximum of the result from the previous step
answered May 27 '14 at 15:26
HurkylHurkyl
112k9120262
$endgroup$
add a comment |
$begingroup$
As you add more elements to the last row, you balance out the size of the two children subtrees, and thus push the proportion of elements in any one child to $1/2$.
You could always just do an algebraic calculation rather than "thinking it out", though:
- Let there be $k$ elements in the last row
- Compute the size of the largest child
- Find the maximum of the result from the previous step
answered May 27 '14 at 15:26
HurkylHurkyl
112k9120262
$endgroup$
add a comment |
$begingroup$
As you add more elements to the last row, you balance out the size of the two children subtrees, and thus push the proportion of elements in any one child to $1/2$.
You could always just do an algebraic calculation rather than "thinking it out", though:
- Let there be $k$ elements in the last row
- Compute the size of the largest child
- Find the maximum of the result from the previous step
answered May 27 '14 at 15:26
HurkylHurkyl
112k9120262
$endgroup$
As you add more elements to the last row, you balance out the size of the two children subtrees, and thus push the proportion of elements in any one child to $1/2$.
You could always just do an algebraic calculation rather than "thinking it out", though:
- Let there be $k$ elements in the last row
- Compute the size of the largest child
- Find the maximum of the result from the previous step
answered May 27 '14 at 15:26
HurkylHurkyl
112k9120262
answered May 27 '14 at 15:26
HurkylHurkyl
112k9120262
answered May 27 '14 at 15:26
HurkylHurkyl
112k9120262
answered May 27 '14 at 15:26
HurkylHurkyl
112k9120262
112k9120262
add a comment |
add a comment |
$begingroup$
Even if the tree is complete binary tree, the no. of nodes in both the sub-trees (left and right of node i) will be bounded by 2n/3. Since the algorithm will choose one of the sub tree of node i, it will not matter which sub-tree it chooses. The thing that matter is that sub-tree must be maximum size and since the size of max nodes subtree is bounded by 2n/3 we will get the same recurrence equation.
answered Aug 9 '16 at 20:07
xyzxyz
1
$endgroup$
add a comment |
$begingroup$
Even if the tree is complete binary tree, the no. of nodes in both the sub-trees (left and right of node i) will be bounded by 2n/3. Since the algorithm will choose one of the sub tree of node i, it will not matter which sub-tree it chooses. The thing that matter is that sub-tree must be maximum size and since the size of max nodes subtree is bounded by 2n/3 we will get the same recurrence equation.
answered Aug 9 '16 at 20:07
xyzxyz
1
$endgroup$
add a comment |
$begingroup$
Even if the tree is complete binary tree, the no. of nodes in both the sub-trees (left and right of node i) will be bounded by 2n/3. Since the algorithm will choose one of the sub tree of node i, it will not matter which sub-tree it chooses. The thing that matter is that sub-tree must be maximum size and since the size of max nodes subtree is bounded by 2n/3 we will get the same recurrence equation.
answered Aug 9 '16 at 20:07
xyzxyz
1
$endgroup$
Even if the tree is complete binary tree, the no. of nodes in both the sub-trees (left and right of node i) will be bounded by 2n/3. Since the algorithm will choose one of the sub tree of node i, it will not matter which sub-tree it chooses. The thing that matter is that sub-tree must be maximum size and since the size of max nodes subtree is bounded by 2n/3 we will get the same recurrence equation.
answered Aug 9 '16 at 20:07
xyzxyz
1
answered Aug 9 '16 at 20:07
xyzxyz
1
answered Aug 9 '16 at 20:07
xyzxyz
1
answered Aug 9 '16 at 20:07
xyzxyz
1
1
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f784787%2fmax-heapify-why-the-worst-case-is-when-the-bottom-level-is-half-full%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
