判断小根堆
作者:
我是高情商
,
2024-07-24 22:58:54
,
所有人可见
,
阅读 1
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=100010;
int q[N];
int n,si;
//判断小根堆(迭代写法)
bool judge_heap(int arr[],int n)
{
for(int i=1;i<=n/2;i++)
{
if(2*i+1<=n&&q[2*i+1]<q[i])return false;
if(2*i<=n&&q[2*i]<q[i])return false;
}
return true;
}
//判断小根堆(递归写法,类似于先序遍历)
bool judge_heap(int arr[],int n,int u)
{
if(u>n)return true;
int left=u*2;
int right=u*2+1;
bool is_heap=true;
if(left<=n)
{
if(q[left]<q[u])return false;
is_heap=judge_heap(arr,n,u*2);
if(!is_heap)return false;
}
if(right<=n)
{
if(q[right]<q[u])return false;
is_heap=judge_heap(arr,n,u*2+1);
if(!is_heap)return false;
}
// 当前节点及其子树都满足小根堆
return true;
}
int main() {
cin>>n;
for(int i=1;i<=n;i++)cin>>q[i];
if(judge_heap(q,n,1))
{
cout<<"是小根堆"<<endl;
}
else
{
cout<<"不是小根堆"<<endl;
}
// if(judge_heap(q,n))
// {
// cout<<"是小根堆"<<endl;
// }
// else
// {
// cout<<"不是小根堆"<<endl;
// }
}