最大堆算法任务
Max-Heapify Algorithm Task
设 A[1...9] = 3 9 5 4 8 6 11 7 2 为一个由 9 个数字组成的数组。说明执行代码Max - Heapify(A, 4, 9), Max-Heapify(A,3,9), Max-Heapify(A,2,9), Max-Heapify(A,1, 9).
为什么may数组不对？
我画了一个堆树
之后我试着做了
Heapify(A,4,9)值4和2交换
3 9 5 2 8 6 11 7 4 -> 我排序了 3 9 5 7 8 6 11 2 4
Max-Heapify(A,3,9) -> 值5和4交换
3 9 4 7 8 6 11 2 5 -> 我排序了 3 9 11 7 8 6 4 2 5 -> 11 9 3 7 8 6 4 2 5
Max-Heapify(A,2,9) -> 值 11 和 9 交换
11 9 6 7 8 3 4 2 5
Max-Heapify(A,1,9) -> 值 11 和 5
5 9 6 7 8 3 4 2 11 -> 如何排序是从父节点开始还是从下到上？有什么提示可以在数组中而不是绘制堆树来解决这个问题吗？
解：11 9 6 7 8 3 5 4 2
您以某种方式将 MaxHeapify 解释为在做一些不应该做的事情。比如你写：
Heapify (A, 4, 9) value 4 and 2 exchange
没有。索引 4 处的值的子项位于索引 8 和 9。要知道节点的子项位于何处，请将索引加倍并添加 0 或 1。（索引 8）处的 7 大于索引 4 处的父项，因此交换在值 4 和 7 之间。结果：
3 9 5 7 8 6 11 4 2
* * *
请注意，在这次交换之后，索引为 4 的节点的两个子节点都变小了。
Heapify (A, 3, 9) 将比较索引 3 (5) 的值与其索引 6 和 7 的子值。6 和 11 的值：11 必须向上冒泡：
3 9 11 7 8 6 5 4 2
* * *
Heapify (A, 2, 9) 会将索引 2 (9) 的值与其索引 4 和 5 的子值进行比较：值 7 和 8：这没关系；无变化：
3 9 11 7 8 6 5 4 2
* * *
Heapify (A, 1, 9) 将比较索引 1 (3) 的值与其索引 2 和 3 的子值：值 9 和 11：11 必须冒泡：
11 9 3 7 8 6 5 4 2
* * *
此时堆已完全堆化：对于每个节点，您现在拥有其值大于（或等于）其子节点的值。这就是一堆。堆不是排序数组。为了降序获取值，需要根据extract算法从堆顶弹出元素：取出前面的元素，将尾元素放在那里，使array 1 元素变短，然后将前面的值向下筛选到堆中（通过交换），直到堆 属性 恢复。
您可以在 Wikipedia.
阅读与堆结构相关的所有函数
设 A[1...9] = 3 9 5 4 8 6 11 7 2 为一个由 9 个数字组成的数组。说明执行代码Max - Heapify(A, 4, 9), Max-Heapify(A,3,9), Max-Heapify(A,2,9), Max-Heapify(A,1, 9).
为什么may数组不对？
我画了一个堆树
之后我试着做了
Heapify(A,4,9)值4和2交换 3 9 5 2 8 6 11 7 4 -> 我排序了 3 9 5 7 8 6 11 2 4
Max-Heapify(A,3,9) -> 值5和4交换
3 9 4 7 8 6 11 2 5 -> 我排序了 3 9 11 7 8 6 4 2 5 -> 11 9 3 7 8 6 4 2 5
Max-Heapify(A,2,9) -> 值 11 和 9 交换
11 9 6 7 8 3 4 2 5
Max-Heapify(A,1,9) -> 值 11 和 5 5 9 6 7 8 3 4 2 11 -> 如何排序是从父节点开始还是从下到上？有什么提示可以在数组中而不是绘制堆树来解决这个问题吗？
解：11 9 6 7 8 3 5 4 2
您以某种方式将 MaxHeapify 解释为在做一些不应该做的事情。比如你写：
Heapify (A, 4, 9)value 4 and 2 exchange
没有。索引 4 处的值的子项位于索引 8 和 9。要知道节点的子项位于何处，请将索引加倍并添加 0 或 1。（索引 8）处的 7 大于索引 4 处的父项，因此交换在值 4 和 7 之间。结果：
3 9 5 7 8 6 11 4 2
* * *
请注意，在这次交换之后，索引为 4 的节点的两个子节点都变小了。
Heapify (A, 3, 9) 将比较索引 3 (5) 的值与其索引 6 和 7 的子值。6 和 11 的值：11 必须向上冒泡：
3 9 11 7 8 6 5 4 2
* * *
Heapify (A, 2, 9) 会将索引 2 (9) 的值与其索引 4 和 5 的子值进行比较：值 7 和 8：这没关系；无变化：
3 9 11 7 8 6 5 4 2
* * *
Heapify (A, 1, 9) 将比较索引 1 (3) 的值与其索引 2 和 3 的子值：值 9 和 11：11 必须冒泡：
11 9 3 7 8 6 5 4 2
* * *
此时堆已完全堆化：对于每个节点，您现在拥有其值大于（或等于）其子节点的值。这就是一堆。堆不是排序数组。为了降序获取值，需要根据extract算法从堆顶弹出元素：取出前面的元素，将尾元素放在那里，使array 1 元素变短，然后将前面的值向下筛选到堆中（通过交换），直到堆 属性 恢复。
您可以在 Wikipedia.
阅读与堆结构相关的所有函数