Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Post History
As you know, a max heap is a binary tree such that each parent is greater than its children. The most compact and efficient way to represent such a tree is an array, where each index corresponds t...
Answer
#3: Post edited
by
meriton
·
2021-12-20T00:36:54Z (almost 3 years ago)
- As you know, a max heap is a binary tree such that each parent is greater than its children.
- The most compact and efficient way to represent such a tree is an array, where each index corresponds to a node in the tree, numbered from the root, level by level, from left to right, as shown in the following picture:
- 0
- / \
- / \
- 1 2
- / \ / \
- 3 4 5 6
- Then, if a node is stored at index `i`, we know that its left child is stored at index `i * 2 + 1`, and its right child at index `i * 2 + 2`.
- This representation has the advantage that we do not need any pointers to represent the structure of the tree, allowing for a more compact memory layout.
- The sort proceeds by taking the numbers in an array, reinterpreting that array as an encoded max heap, and moving elements around until the heap invariant (that each parent is greater than both of its children) is satisfied.
- The heapify function takes an index i, and checks that the node stored there is greater than its children. If this is not the case, the greater child swaps places with the parent. Since this swap reduces the value of the child, it is possible that the child is no longer greater than its children, so we recursively check them (again).
More precisely, the heapify function assumes that the subtree of the children are correct (each node greater than its children), and makes sure the entire tree rooted at `i` is correct. By invoking heapify for each node, from bottom to top, we therefore ensure the entire tree is correct.- And that's why the function is called `heapify`: It turns our unsorted array into an encoded max heap.
- As you know, a max heap is a binary tree such that each parent is greater than its children.
- The most compact and efficient way to represent such a tree is an array, where each index corresponds to a node in the tree, numbered from the root, level by level, from left to right, as shown in the following picture:
- 0
- / \
- / \
- 1 2
- / \ / \
- 3 4 5 6
- Then, if a node is stored at index `i`, we know that its left child is stored at index `i * 2 + 1`, and its right child at index `i * 2 + 2`.
- This representation has the advantage that we do not need any pointers to represent the structure of the tree, allowing for a more compact memory layout.
- The sort proceeds by taking the numbers in an array, reinterpreting that array as an encoded max heap, and moving elements around until the heap invariant (that each parent is greater than both of its children) is satisfied.
- The heapify function takes an index i, and checks that the node stored there is greater than its children. If this is not the case, the greater child swaps places with the parent. Since this swap reduces the value of the child, it is possible that the child is no longer greater than its children, so we recursively check them (again).
- More precisely, the heapify function assumes that the subtrees of the children are correct (each node greater than its children), and makes sure the entire tree rooted at `i` is correct. By invoking heapify for each node, from bottom to top, we therefore ensure the entire tree is correct.
- And that's why the function is called `heapify`: It turns our unsorted array into an encoded max heap.
#2: Post edited
by
meriton
·
2021-12-20T00:21:01Z (almost 3 years ago)
- As you know, a max heap is a binary tree such that each parent is greater than its children.
- The most compact and efficient way to represent such a tree is an array, where each index corresponds to a node in the tree, numbered from the root, level by level, from left to right, as shown in the following picture:
- 0
- / \
- / \
- 1 2
- / \ / \
- 3 4 5 6
- Then, if a node is stored at index `i`, we know that its left child is stored at index `i * 2 + 1`, and its right child at index `i * 2 + 2`.
- This representation has the advantage that we do not need any pointers to represent the structure of the tree, allowing for a more compact memory layout.
- The sort proceeds by taking the numbers in an array, reinterpreting that array as an encoded max heap, and moving elements around until the heap invariant (that each parent is greater than both of its children) is satisfied.
- The heapify function takes an index i, and checks that the node stored there is greater than its children. If this is not the case, the greater child swaps places with the parent. Since this swap reduces the value of the child, it is possible that the child is no longer greater than its children, so we recursively check them (again).
More precisely, the heapify function assumes that the subtree of the children are correct (each node greater than its children), and makes sure the entire tree rooted at `i` is correct. By invoking heapify for each node, from bottom to top, we therefore ensure the entire tree is correct.
- As you know, a max heap is a binary tree such that each parent is greater than its children.
- The most compact and efficient way to represent such a tree is an array, where each index corresponds to a node in the tree, numbered from the root, level by level, from left to right, as shown in the following picture:
- 0
- / \
- / \
- 1 2
- / \ / \
- 3 4 5 6
- Then, if a node is stored at index `i`, we know that its left child is stored at index `i * 2 + 1`, and its right child at index `i * 2 + 2`.
- This representation has the advantage that we do not need any pointers to represent the structure of the tree, allowing for a more compact memory layout.
- The sort proceeds by taking the numbers in an array, reinterpreting that array as an encoded max heap, and moving elements around until the heap invariant (that each parent is greater than both of its children) is satisfied.
- The heapify function takes an index i, and checks that the node stored there is greater than its children. If this is not the case, the greater child swaps places with the parent. Since this swap reduces the value of the child, it is possible that the child is no longer greater than its children, so we recursively check them (again).
- More precisely, the heapify function assumes that the subtree of the children are correct (each node greater than its children), and makes sure the entire tree rooted at `i` is correct. By invoking heapify for each node, from bottom to top, we therefore ensure the entire tree is correct.
- And that's why the function is called `heapify`: It turns our unsorted array into an encoded max heap.
#1: Initial revision
by
meriton
·
2021-12-20T00:19:15Z (almost 3 years ago)
As you know, a max heap is a binary tree such that each parent is greater than its children.
The most compact and efficient way to represent such a tree is an array, where each index corresponds to a node in the tree, numbered from the root, level by level, from left to right, as shown in the following picture:
0
/ \
/ \
1 2
/ \ / \
3 4 5 6
Then, if a node is stored at index `i`, we know that its left child is stored at index `i * 2 + 1`, and its right child at index `i * 2 + 2`.
This representation has the advantage that we do not need any pointers to represent the structure of the tree, allowing for a more compact memory layout.
The sort proceeds by taking the numbers in an array, reinterpreting that array as an encoded max heap, and moving elements around until the heap invariant (that each parent is greater than both of its children) is satisfied.
The heapify function takes an index i, and checks that the node stored there is greater than its children. If this is not the case, the greater child swaps places with the parent. Since this swap reduces the value of the child, it is possible that the child is no longer greater than its children, so we recursively check them (again).
More precisely, the heapify function assumes that the subtree of the children are correct (each node greater than its children), and makes sure the entire tree rooted at `i` is correct. By invoking heapify for each node, from bottom to top, we therefore ensure the entire tree is correct.