对于n个元素的关键字序列{k1,k2,…,kn),当且仅当满足关系Ki≤K2i且Ki≤K2i＋1(2i≤n,2i＋1≤n)称其为小

Question

对于n个元素的关键字序列{k1,k2,…,kn)，当且仅当满足关系Ki≤K2i且Ki≤K2i+1(2i≤n,2i+1≤n)称其为小根堆，反之则为大根堆。以下序列中，(58)不符合堆的定义。

A．(5,10,15,76,39,27,18)

B．(5,10,18,76,39,27,15)

C．(59,27,36,15,8,25,9)

D．(59,36,27,15,8,25,9)

Answer 1

正确答案：B
解析：将4个选项的序列中元素放入一棵完全二叉树，如图1-7所示，以便于观察节点ki、k2i、k2i+1≤n,2i+1≤n)之间的关系。按照小根堆的定义检查选项A、B的二叉树，按照大根堆的定义检查选项C、D的二叉树，显然，选项B不符合小根堆的定义。