堆排序(自下而上)
Heap sort (bottom up)
我正在尝试参加一项考试,但根本无法理解该方法。这是堆排序 Bottom up heap construction
这是我的任务
G D A N S K S O P O T
1 2 3 4 5 6 7 8 9 10 11
解决方案是(我做理解第2行)
Bottom Up Heap-construction:
1 2 3 4 5 6 7 8 9 10 11
G D A N S K S O P O T
T O S
P O N
S K A
T P S O D
T S S P O G D
answer in total. t s s p o k a o n g d
前三行我看懂了,后面的我没看懂。有没有人有时间解释一下:)
我们有这棵树
G
/ \
/ \
D A
/ \ / \
N S K S
/ \ / \
O P O T
...表示为:
1 2 3 4 5 6 7 8 9 10 11
G D A N S K S O P O T
Heap-construction algorithm 将heapify以位置5为根的子树,然后是4、3、2,最后是1。解决方案中的每一行都列出了相应heapify操作中涉及的节点的字母:
在以5为根的子树中,字母S向右向下筛选:
S* T
/ \ → / \
O T O S*
在以4为根的子树中,字母N向右向下筛选:
N* P
/ \ → / \
O P O N*
在以3为根的子树中,字母A向右向下筛选:
A* S
/ \ → / \
K S K A*
在以2为根的子树中,字母D向右向下筛选两次:
D* T T
/ \ / \ / \
P T → P D* → P S
/ \ / \ / \ / \ / \ / \
O N O S O N O S O N O D*
在以1为根的子树中,字母G向下筛选3次:
G* T T T
/ \ / \ / \ / \
/ \ / \ / \ / \
T S → G* S → S S → S S
/ \ / \ / \ / \ / \ / \ / \ / \
P S K A P S K A P G* K A P O K A
/ \ / \ / \ / \ / \ / \ / \ / \
O N O D O N O D O N O D O N G* D
上面的每一个root-sift-downs都对应你引用的解决方案中的一行。这样的一行列出了以某种方式参与筛选操作的节点,因为在此过程中正在比较它们的值。因此,例如,在这最后一步中,G 与 T 和 S 进行比较,然后 G 向左筛选,并与 P 和 S 进行比较。G 进一步筛选并与 O 和 D 进行比较,最终找到它的作为叶子放置。这就是为什么最后一行有这些字母,并将它们列为转换完成后的位置。
我正在尝试参加一项考试,但根本无法理解该方法。这是堆排序 Bottom up heap construction
这是我的任务
G D A N S K S O P O T 1 2 3 4 5 6 7 8 9 10 11
解决方案是(我做理解第2行)
Bottom Up Heap-construction:
1 2 3 4 5 6 7 8 9 10 11 G D A N S K S O P O T T O S P O N S K A T P S O D T S S P O G D answer in total. t s s p o k a o n g d
前三行我看懂了,后面的我没看懂。有没有人有时间解释一下:)
我们有这棵树
G
/ \
/ \
D A
/ \ / \
N S K S
/ \ / \
O P O T
...表示为:
1 2 3 4 5 6 7 8 9 10 11
G D A N S K S O P O T
Heap-construction algorithm 将heapify以位置5为根的子树,然后是4、3、2,最后是1。解决方案中的每一行都列出了相应heapify操作中涉及的节点的字母:
在以5为根的子树中,字母S向右向下筛选:
S* T / \ → / \ O T O S*
在以4为根的子树中,字母N向右向下筛选:
N* P / \ → / \ O P O N*
在以3为根的子树中,字母A向右向下筛选:
A* S / \ → / \ K S K A*
在以2为根的子树中,字母D向右向下筛选两次:
D* T T / \ / \ / \ P T → P D* → P S / \ / \ / \ / \ / \ / \ O N O S O N O S O N O D*
在以1为根的子树中,字母G向下筛选3次:
G* T T T / \ / \ / \ / \ / \ / \ / \ / \ T S → G* S → S S → S S / \ / \ / \ / \ / \ / \ / \ / \ P S K A P S K A P G* K A P O K A / \ / \ / \ / \ / \ / \ / \ / \ O N O D O N O D O N O D O N G* D
上面的每一个root-sift-downs都对应你引用的解决方案中的一行。这样的一行列出了以某种方式参与筛选操作的节点,因为在此过程中正在比较它们的值。因此,例如,在这最后一步中,G 与 T 和 S 进行比较,然后 G 向左筛选,并与 P 和 S 进行比较。G 进一步筛选并与 O 和 D 进行比较,最终找到它的作为叶子放置。这就是为什么最后一行有这些字母,并将它们列为转换完成后的位置。