判断序列(16,19,10,15,4,23,36,20)是否为(小顶)堆?为什么?如果不是,请按照建立堆的思想把它调整为堆,并用图表示建堆的过程。
不是,4,16,10…
不是
不是,最后调整的堆是:4 15 10 16 19 23 36 20
4 15 10 16 19 23 36 20
不是,不满足堆的调条件。 4 15 10 16 19 23 36 20
本题考点是堆的定义和建立方法。&n...
用户登录可进行刷题及查看答案
本题考点是堆的定义和建立方法。 n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质): (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n/2 ) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆。 因此,本题答题要点如下: 因为不满足(ai<a2i 和ai<a2i+1)如a1=16,a3=10,所以不是小顶堆。 可以调整为堆:(4,15,10,16,19,23,36,20)
登录后提交答案