判断小根堆和大根堆

日常学习记录。

如有错误，还望指正！

一、判断小根堆

小根堆概念：小根堆的最小元素存放在堆顶，且任意一个非根节点的结点都大于或等于双亲结点。【孩子结点值>=双亲结点值】

结点下标介绍：

注：n为堆的结点总个数。

算法思想：利用排除法，排除掉孩子结点值大于根节点的所有情况，如果都不符合以上情况，就是小根堆，否则不是。判断大根堆算法思想类似。

#include <stdio.h> //判断小根堆，堆以顺序表存储 bool judge(int a[],int n) //n为数组a的长度 { //偶数结点时：有单分支+双分支 if(n%2==0) { if(a[n/2-1]>a[n-1]) //判断单分支，若单分支的根节点>左孩子，则返回false return false; for(int i=n/2-2;i>=1;i--) //判断双分支，注意i的起始条件！ { if((a[i]>a[2*i+1])||(a[i]>a[2*i+2]))//双亲节点和左右孩子结点大小比较 return false; } } //奇数结点时：无单分支，只有双分支 else { for(int i=n/2-1;i>=1;i--) //判断双分支，注意i的起始条件！ { if((a[i]>a[2*i+1])||(a[i]>a[2*i+2])) return false; } } return true; } int main() { int a1[7]={8,15,10,21,34,16,12}; int a2[7]={8,15,10,21,34,16,7}; int a3[6]={8,15,10,21,34,16}; int a4[8]={8,15,10,21,34,16,12,30}; int a5[8]={8,15,10,21,34,16,12,10}; printf("%d\n",judge(a1,7));//1 printf("%d\n",judge(a2,7));//0 printf("%d\n",judge(a3,6));//1 printf("%d\n",judge(a4,8));//1 printf("%d\n",judge(a5,8));//0 return 0; } /* 0 8 / \ 1 15 10 2 / \ / \ 21 34 16 12 小根堆 3 4 5 6 8 / \ 15 10 / \ / \ 21 34 16 7 非小根堆 8 / \ 15 10 / \ / 21 34 16 小根堆 8 / \ 15 10 / \ / \ 21 34 16 12 小根堆 / 30 8 / \ 15 10 / \ / \ 21 34 16 12 非小根堆 / 10 */

二、判断大根堆

大根堆概念：大根堆的最大元素存放在堆顶，且任意一个非根节点的结点都小于或等于双亲结点。【孩子结点值<=双亲结点值】,和小根堆概念相反。

把判断小根堆的＞全部改成＜，其余不变

#include <stdio.h> //判断大根堆 bool judge(int a[],int n) //n为数组a的长度 { //偶数结点时：有单分支+双分支 if(n%2==0) { if(a[n/2-1]<a[n-1]) //判断单分支，若单分支的根节点<左孩子，则返回false return false; for(int i=n/2-2;i>=1;i--) //判断双分支，注意i的起始条件！ { if((a[i]<a[2*i+1])||(a[i]<a[2*i+2]))//双亲节点和左右孩子结点大小比较 return false; } } //奇数结点时：无单分支，只有双分支 else { for(int i=n/2-1;i>=1;i--) //判断双分支，注意i的起始条件！ { if((a[i]<a[2*i+1])||(a[i]<a[2*i+2])) return false; } } return true; } int main() { int a1[7]={25,13,10,12,9,16,7}; int a2[7]={25,13,10,12,9,8,7}; int a3[6]={25,13,10,12,9,8}; printf("%d\n",judge(a1,7)); printf("%d\n",judge(a2,7)); printf("%d\n",judge(a3,6)); return 0; } /* 25 / \ 13 10 / \ / \ 12 9 16 7 非大根堆 25 / \ 13 10 / \ / \ 12 9 8 7 大根堆 25 / \ 13 10 / \ / 12 9 8 大根堆 */