GATE | GATE-CS-2006 |问题77

三元最大堆类似于二进制最大堆，但节点没有两个子节点，而是有三个子节点。三元堆可以用如下数组表示：根存储在第一个位置[0]，下一级的节点从左到右从[1]到[3]存储。树的第二级从左到右的节点从[4]位置开始存储。通过将x放置在位置a[n]并将其推到树上以满足heap属性，可以将项目x插入到包含n个项目的三元堆中。

假设元素7、2、10和4按该顺序插入到上述问题中找到的有效3元最大堆中，以下哪一项是数组中表示结果堆的项序列？

（A） 10, 7, 9, 8, 3, 1, 5, 2, 6, 4 （B） 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 （C） 10, 9, 4, 5, 7, 6, 8, 2, 1, 3 （D） 10, 8, 6, 9, 7, 2, 3, 4, 1, 5 答复: （A） 说明： 插入7之后

                                          9
                                      /   |   
                                    /     |     
                                  7       6       8
                               / | 
                             /   |  
                            3    1    5    

插入2之后

                                           9
                                      /    |   
                                    /      |     
                                  7        6       8
                               / |        /
                             /   |       /
                            3    1    5  2

插入10后

                                 10
                             /    |   
                           /      |     
                        7         9       8
                    / |        / |
                  /   |       /  |
                3    1    5  2    6

插入4之后

                                 10
                             /   |   
                           /     |     
                         7        9       8
                      / |       / | 
                    /   |      /  |   
                  3    1    5  2   6    4

这个问题的小测验