二叉树如何建堆

来源:百度知道 编辑:UC知道 时间:2024/06/03 11:35:39
比如 给你49,38,65,97,76,13,27建立一个堆,并给出堆排序的全过程

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

首先把所有数据填进一个完全二叉树中。然后对非终端结点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