例如:判断15,30,22,93,52,71是不是堆排序
这个序列是堆排序的结果。判断是否为堆排序,要根据堆排序的两点性质来判断,分别是:
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n)//ki相当于二叉树的非叶结点,K2i则是左孩子,k2i+1是右孩子
(2)若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:
树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字
换句话说,这道题目,15是根节点,左孩子30和右孩子22都大于15,同理30的左右孩子分别是93、52,都大于30,22的左孩子71大于它,所以这棵树是个不完全二叉树,并且可以看出它是小堆栈。
做此类题的诀窍在于:按完全二叉树的性质去排列序列,在判断是否孩子结点都大于父亲结点,或者孩子结点都小于父亲结点。
堆排序是选择排序的一种。