判断小根堆和大根堆

日常学习记录。如有错误还望指正一、判断小根堆小根堆概念小根堆的最小元素存放在堆顶且任意一个非根节点的结点都大于或等于双亲结点。【孩子结点值双亲结点值】结点下标介绍注n为堆的结点总个数。奇数结点双分支根结点下标[0n/2-1]双分支左孩子下标2*根节点下标1双分支右孩子下标2*根节点下标2偶数结点单分支根结点下标n/2-1单分支左孩子下标n-1双分支根结点下标[0n/2-2]双分支左孩子下标2*根节点下标1双分支右孩子下标2*根节点下标2算法思想利用排除法排除掉孩子结点值大于根节点的所有情况如果都不符合以上情况就是小根堆否则不是。判断大根堆算法思想类似。#include stdio.h //判断小根堆堆以顺序表存储 bool judge(int a[],int n) //n为数组a的长度 { //偶数结点时有单分支双分支 if(n%20) { if(a[n/2-1]a[n-1]) //判断单分支若单分支的根节点左孩子则返回false return false; for(int in/2-2;i1;i--) //判断双分支注意i的起始条件 { if((a[i]a[2*i1])||(a[i]a[2*i2]))//双亲节点和左右孩子结点大小比较 return false; } } //奇数结点时无单分支只有双分支 else { for(int in/2-1;i1;i--) //判断双分支注意i的起始条件 { if((a[i]a[2*i1])||(a[i]a[2*i2])) 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%20) { if(a[n/2-1]a[n-1]) //判断单分支若单分支的根节点左孩子则返回false return false; for(int in/2-2;i1;i--) //判断双分支注意i的起始条件 { if((a[i]a[2*i1])||(a[i]a[2*i2]))//双亲节点和左右孩子结点大小比较 return false; } } //奇数结点时无单分支只有双分支 else { for(int in/2-1;i1;i--) //判断双分支注意i的起始条件 { if((a[i]a[2*i1])||(a[i]a[2*i2])) 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 大根堆 */