对于序列{8,18,6,16,29,28},试写出堆顶元素最小的初始堆。

就这个问题,很简单,但是我希望能解释下怎么构造一个堆,.谢谢了
2024-12-29 12:04:53
推荐回答(3个)
回答1:

首先肯定有明白什么是堆,堆有大根堆,和小根堆。你的题目要求显然是要球小根堆的。
堆的定义:n个元素的序列(k1,k2,……,kn)当且仅当满足以下关系时,称之为堆。
{ki<=k2i 且ki<=k2i+1} 此时是小根堆;
{ki>=k2i 且ki>=k2i+1} 此时是大根堆;(i=1,2,3,……,[n/2])
小顶堆的初始堆序列是{6,16,8,18,29,28}
至于怎么得到的详细视频http://v.youku.com/v_show/id_XNzk5NDk1ODg=.html
其中讲到的堆排序会告诉你,在22分钟左右,认真看看。

回答2:

1 将序列顺序排成一棵完全二叉树
2 从第n/2个元素(即此无序序列对应的完全二叉树的最后一个非终端结点)开始筛选
3 将该结点与孩子结点比较,将小的数作为根,且保持堆的特性,若影响堆的特性则按该步骤调整
4 否则读取第n/2 -1的元素,重复比较过程直到读取完第1个数为止

回答3:

25,96,11,63,57,78,44的最小堆