堆排序(自下而上)

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 进行比较,最终找到它的作为叶子放置。这就是为什么最后一行有这些字母,并将它们列为转换完成后的位置。