l********r
发帖数: 140 | 1 Given the root of a binary tree (not balanced), heapify it.
Am I right we msut need the parent pointer for each node to be more
efficient? |
l********r
发帖数: 140 | 2 By the way, my algorithm is like (assume max heap):
for the current node, if left or right is bigger than the current, switch
the biggest value as the current value, and try to move it all the way up to
its parent chain if that is bigger than the parent's value as well.
Then do the same for its left and right children. |
l********r
发帖数: 140 | |
s*****n
发帖数: 994 | 4 It's still not balanced by your algorithm? |
l********r
发帖数: 140 | 5 Why not?
It starts with root, it guarantee the current node and its two children
satisfy the condition. Then it back check (heapify) all its parents, and
guarantee that. Then move down to its children. I just don't know whether it
is efficient or not.
【在 s*****n 的大作中提到】
: It's still not balanced by your algorithm?
|
s*****n
发帖数: 994 | 6 左右子节点都是balanced并不保证current node是balanced
比如左深度3 右深度100 |
c**y
发帖数: 172 | 7 Does Post-Order travel work here?
void heapify(binaryTree *node)
{
if (!node) return;
if (node->left)
heapify(node->left);
if (node->right)
heapify(node->right);
int max = node->value;
if (node->left && node->left->value > max) {
max = node->left->value;
}
if (node->right && node->right->value > max) {
max = mode->right->value;
}
if (max == node->value) {
return;
} else if (node->left && max == node->left->value) {
int tmp = node->value;
node->value = node->left->value;
node->left->value = tmp;
} else {
int tmp = node->value;
node->value = node->right->value;
node->right->value = tmp;
}
return;
} |
l********r
发帖数: 140 | 8 "Given the root of a binary tree (not balanced), heapify it."
It asks to heapify, it does not ask to balance the tree.
【在 s*****n 的大作中提到】
: 左右子节点都是balanced并不保证current node是balanced
: 比如左深度3 右深度100
|
s**x
发帖数: 7506 | 9
I think you need push all the way down in the last swap step, thinking the
case root is the smallest value.
【在 c**y 的大作中提到】
: Does Post-Order travel work here?
: void heapify(binaryTree *node)
: {
: if (!node) return;
: if (node->left)
: heapify(node->left);
: if (node->right)
: heapify(node->right);
: int max = node->value;
: if (node->left && node->left->value > max) {
|
c**y
发帖数: 172 | 10 Thanks for pointing out the issue. I now know it.
【在 s**x 的大作中提到】
:
: I think you need push all the way down in the last swap step, thinking the
: case root is the smallest value.
|
|
|
g*********e
发帖数: 14401 | 11
but heap is a balanced tree
【在 l********r 的大作中提到】
: "Given the root of a binary tree (not balanced), heapify it."
: It asks to heapify, it does not ask to balance the tree.
|
c**y
发帖数: 172 | 12 Revised solution. Will try to test it if I get a chance today.
void heapify(binaryTree *node)
{
if (!node) return;
if (node->left)
heapify(node->left);
if (node->right)
heapify(node->right);
int max = node->value;
if (node->left && node->left->value > max) {
max = node->left->value;
}
if (node->right && node->right->value > max) {
max = mode->right->value;
}
if (max == node->value) {
return;
} else if (node->left && max == node->left->value) {
int tmp = node->value;
node->value = node->left->value;
node->left->value = tmp;
heapify(node->left);
} else {
int tmp = node->value;
node->value = node->right->value;
node->right->value = tmp;
heapify(node->right);
}
return;
} |
s**x
发帖数: 7506 | 13
the pushdown (or siftdown) part should not call heapify, it is much simpler
than heapify, just swap the bigger of two children with root if needed, you
need a separate function or a for loop I think.
【在 c**y 的大作中提到】
: Revised solution. Will try to test it if I get a chance today.
: void heapify(binaryTree *node)
: {
: if (!node) return;
: if (node->left)
: heapify(node->left);
: if (node->right)
: heapify(node->right);
: int max = node->value;
: if (node->left && node->left->value > max) {
|
c**y
发帖数: 172 | 14 The revised algorithm above follows the approach used in building a heap,
which consists of two parts: BUILD-MAX-HEAP (see page 157 of CLRC, 3rd
edition) and MAX-HEAPIFY (see page 154 of the same book).
The MAX-HEAPIFY algorithm is a recursive solution in that it calls itself
again in the pushdown part. Similarly, heapify is directly called by itself
in the above solution.
BUILD-MAX-HEAP restores the heap property in a bottom-up fashion.
Correspondingly, post-order is used to achieve the same bottom-up effect.
simpler
you
【在 s**x 的大作中提到】
:
: the pushdown (or siftdown) part should not call heapify, it is much simpler
: than heapify, just swap the bigger of two children with root if needed, you
: need a separate function or a for loop I think.
|
s**x
发帖数: 7506 | 15 I just reviewed some chapters and searched online as well. the MAX-HEAPITY
is called SiftDown in some other papers, which makes more sense.
MAX-HEAPITY is SiftDown
BUILD-MAX-HEAP is calling SiftDown/MAX-HEAPITY from bottom up.
your solution does not have a SiftDown Call, siftdown only touches one child
, while your heapify always touches both left and right children during a
recursive call.it might work too, but would be expensive.
itself
【在 c**y 的大作中提到】
: The revised algorithm above follows the approach used in building a heap,
: which consists of two parts: BUILD-MAX-HEAP (see page 157 of CLRC, 3rd
: edition) and MAX-HEAPIFY (see page 154 of the same book).
: The MAX-HEAPIFY algorithm is a recursive solution in that it calls itself
: again in the pushdown part. Similarly, heapify is directly called by itself
: in the above solution.
: BUILD-MAX-HEAP restores the heap property in a bottom-up fashion.
: Correspondingly, post-order is used to achieve the same bottom-up effect.
:
: simpler
|
s**x
发帖数: 7506 | 16 modifies Caiy's code:
void SiftDown(binaryTree *node)
{
if(!node) return;
binaryTree *largest = node;
if (node->left != NULL && largest->value < node->left->value)
largest = node->left;
if (node->right != NULL && largest->value < node->right->value)
largest = node->right;
if (largest == node) return;
int tmp = node->value;
node->value = largest->value;
largest->value = tmp;
SiftDown(largest);
}
void heapify(binaryTree *node)
{
if (!node) return;
if (node->left)
heapify(node->left);
if (node->right)
heapify(node->right);
SiftDown(node);
} |
l********r
发帖数: 140 | 17 Given the root of a binary tree (not balanced), heapify it.
Am I right we msut need the parent pointer for each node to be more
efficient? |
l********r
发帖数: 140 | 18 By the way, my algorithm is like (assume max heap):
for the current node, if left or right is bigger than the current, switch
the biggest value as the current value, and try to move it all the way up to
its parent chain if that is bigger than the parent's value as well.
Then do the same for its left and right children. |
l********r
发帖数: 140 | |
s*****n
发帖数: 994 | 20 It's still not balanced by your algorithm? |
|
|
l********r
发帖数: 140 | 21 Why not?
It starts with root, it guarantee the current node and its two children
satisfy the condition. Then it back check (heapify) all its parents, and
guarantee that. Then move down to its children. I just don't know whether it
is efficient or not.
【在 s*****n 的大作中提到】
: It's still not balanced by your algorithm?
|
s*****n
发帖数: 994 | 22 左右子节点都是balanced并不保证current node是balanced
比如左深度3 右深度100 |
c**y
发帖数: 172 | 23 Does Post-Order travel work here?
void heapify(binaryTree *node)
{
if (!node) return;
if (node->left)
heapify(node->left);
if (node->right)
heapify(node->right);
int max = node->value;
if (node->left && node->left->value > max) {
max = node->left->value;
}
if (node->right && node->right->value > max) {
max = mode->right->value;
}
if (max == node->value) {
return;
} else if (node->left && max == node->left->value) {
int tmp = node->value;
node->value = node->left->value;
node->left->value = tmp;
} else {
int tmp = node->value;
node->value = node->right->value;
node->right->value = tmp;
}
return;
} |
l********r
发帖数: 140 | 24 "Given the root of a binary tree (not balanced), heapify it."
It asks to heapify, it does not ask to balance the tree.
【在 s*****n 的大作中提到】
: 左右子节点都是balanced并不保证current node是balanced
: 比如左深度3 右深度100
|
s**x
发帖数: 7506 | 25
I think you need push all the way down in the last swap step, thinking the
case root is the smallest value.
【在 c**y 的大作中提到】
: Does Post-Order travel work here?
: void heapify(binaryTree *node)
: {
: if (!node) return;
: if (node->left)
: heapify(node->left);
: if (node->right)
: heapify(node->right);
: int max = node->value;
: if (node->left && node->left->value > max) {
|
c**y
发帖数: 172 | 26 Thanks for pointing out the issue. I now know it.
【在 s**x 的大作中提到】
:
: I think you need push all the way down in the last swap step, thinking the
: case root is the smallest value.
|
g*********e
发帖数: 14401 | 27
but heap is a balanced tree
【在 l********r 的大作中提到】
: "Given the root of a binary tree (not balanced), heapify it."
: It asks to heapify, it does not ask to balance the tree.
|
c**y
发帖数: 172 | 28 Revised solution. Will try to test it if I get a chance today.
void heapify(binaryTree *node)
{
if (!node) return;
if (node->left)
heapify(node->left);
if (node->right)
heapify(node->right);
int max = node->value;
if (node->left && node->left->value > max) {
max = node->left->value;
}
if (node->right && node->right->value > max) {
max = mode->right->value;
}
if (max == node->value) {
return;
} else if (node->left && max == node->left->value) {
int tmp = node->value;
node->value = node->left->value;
node->left->value = tmp;
heapify(node->left);
} else {
int tmp = node->value;
node->value = node->right->value;
node->right->value = tmp;
heapify(node->right);
}
return;
} |
s**x
发帖数: 7506 | 29
the pushdown (or siftdown) part should not call heapify, it is much simpler
than heapify, just swap the bigger of two children with root if needed, you
need a separate function or a for loop I think.
【在 c**y 的大作中提到】
: Revised solution. Will try to test it if I get a chance today.
: void heapify(binaryTree *node)
: {
: if (!node) return;
: if (node->left)
: heapify(node->left);
: if (node->right)
: heapify(node->right);
: int max = node->value;
: if (node->left && node->left->value > max) {
|
c**y
发帖数: 172 | 30 The revised algorithm above follows the approach used in building a heap,
which consists of two parts: BUILD-MAX-HEAP (see page 157 of CLRC, 3rd
edition) and MAX-HEAPIFY (see page 154 of the same book).
The MAX-HEAPIFY algorithm is a recursive solution in that it calls itself
again in the pushdown part. Similarly, heapify is directly called by itself
in the above solution.
BUILD-MAX-HEAP restores the heap property in a bottom-up fashion.
Correspondingly, post-order is used to achieve the same bottom-up effect.
simpler
you
【在 s**x 的大作中提到】
:
: the pushdown (or siftdown) part should not call heapify, it is much simpler
: than heapify, just swap the bigger of two children with root if needed, you
: need a separate function or a for loop I think.
|
|
|
s**x
发帖数: 7506 | 31 I just reviewed some chapters and searched online as well. the MAX-HEAPITY
is called SiftDown in some other papers, which makes more sense.
MAX-HEAPITY is SiftDown
BUILD-MAX-HEAP is calling SiftDown/MAX-HEAPITY from bottom up.
your solution does not have a SiftDown Call, siftdown only touches one child
, while your heapify always touches both left and right children during a
recursive call.it might work too, but would be expensive.
itself
【在 c**y 的大作中提到】
: The revised algorithm above follows the approach used in building a heap,
: which consists of two parts: BUILD-MAX-HEAP (see page 157 of CLRC, 3rd
: edition) and MAX-HEAPIFY (see page 154 of the same book).
: The MAX-HEAPIFY algorithm is a recursive solution in that it calls itself
: again in the pushdown part. Similarly, heapify is directly called by itself
: in the above solution.
: BUILD-MAX-HEAP restores the heap property in a bottom-up fashion.
: Correspondingly, post-order is used to achieve the same bottom-up effect.
:
: simpler
|
s**x
发帖数: 7506 | 32 modifies Caiy's code:
void SiftDown(binaryTree *node)
{
if(!node) return;
binaryTree *largest = node;
if (node->left != NULL && largest->value < node->left->value)
largest = node->left;
if (node->right != NULL && largest->value < node->right->value)
largest = node->right;
if (largest == node) return;
int tmp = node->value;
node->value = largest->value;
largest->value = tmp;
SiftDown(largest);
}
void heapify(binaryTree *node)
{
if (!node) return;
if (node->left)
heapify(node->left);
if (node->right)
heapify(node->right);
SiftDown(node);
} |
c********p
发帖数: 1969 | |
x*****0
发帖数: 452 | |
c********p
发帖数: 1969 | |
x*****0
发帖数: 452 | |
x*****a
发帖数: 9 | 37 不太理解这里的heapify
比如说一个heap, 是一个complete binary tree. 所以其实他是balanced的.
如果不需要上面这个条件, 只是让他有heap的特征, 比如说root就是max或者min, post
order traversal就可以, 不需要parent pointer |
s**x
发帖数: 7506 | 38 先读一读几个 heap sort 的算法就明白了。 不同的书用的术语也不一样， 核心是一
样的。 我感觉你取post order 也是一样的。不过没人那么说而已，本质都是先处理子
树，再处理根结点，处理根结点就是siftdown.
post
★ 发自iPhone App: ChineseWeb 8.6
【在 x*****a 的大作中提到】
: 不太理解这里的heapify
: 比如说一个heap, 是一个complete binary tree. 所以其实他是balanced的.
: 如果不需要上面这个条件, 只是让他有heap的特征, 比如说root就是max或者min, post
: order traversal就可以, 不需要parent pointer
|
