应用题
11.关于堆的一些问题：
(1)堆的存储表示是顺序的，还是链接的?
(2)设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?
(3)对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大0表示法)?
(1)堆的存储表示是顺序的，还是链接的?
(2)设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?
(3)对n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大0表示法)?
【正确答案】(1)堆的存储是顺序的。
(2)最大值元素一定是叶子结点，在最下两层上。
(3)在建含有n个元素、深度为h的堆时，其比较次数不超过4n，推导如下：
由于第i层上的结点数至多是2i-1，以它为根的二叉树的深度为h一i+1，则调用[n／2]次筛选算法时总共进行的关键字比较次数不超过下式之值：
2i-1×2(h一i)=
2i×(h一i)=
2h-j×j≤(2n)
(2)最大值元素一定是叶子结点，在最下两层上。
(3)在建含有n个元素、深度为h的堆时，其比较次数不超过4n，推导如下：
由于第i层上的结点数至多是2i-1，以它为根的二叉树的深度为h一i+1，则调用[n／2]次筛选算法时总共进行的关键字比较次数不超过下式之值：
2i-1×2(h一i)=2i×(h一i)=2h-j×j≤(2n)【答案解析】