二叉树如何建堆

发布网友发布时间：2022-07-15 14:23

共2个回答

热心网友时间：2024-11-30 02:06

首先把所有数据填进一个完全二叉树中。然后对非终端结点n/2向下进行调整。建小根堆的时候方法是：1.比较它与两个孩子的大小。哪个孩子比它小也比兄弟小则把它调到那个孩子的位置。然后再判断该位置还要不要往下调。2.从n/2开始，对它之前的所有元素进行1操作。
本题解法为（按完全二叉树写）
一。把所有元素写进完全二叉树中得
49
38 65

97 76 13 27

二。1.对非叶子元素进行调整，即第n/2个元素，即本题的65.
因为65的孩子为13和27.因为都比65小，而13比27小。所以调到13的位置。即65和13换
49
38 13
97 76 65 27

2.对n/2前一个元素进行调整。即本题的38.因为97和76都比38大，所以不用调
3.对2之前的一个元素，即本题的49进行调整，因为38和13都49小，而13比38小，所以49和13换位置。换位置后49的两个孩子为65和27.27比49小，所以27和49换位置。
13
38 27
97 76 65 49

热心网友时间：2024-11-30 02:06

看算法导论去吧，有详细过程。或者一般数据结构书都讲。
在这说也说不清楚