c语言实现最小堆和最大堆

第一部分：最大堆和最小堆的基本性质

（1）基本定义

①最大堆

根是这颗树最大的值，每个根节点都比    左右子节点的值大， 对左右子树仍然成立；

②最小堆

根是这颗树的最小的值， 每个根节点都比左右子节点的值小， 同样对左右子树成立；

（2）性质（数组下标关系）

由堆构建的树的背后原理是基于完全二叉树，以及数组下标（从1开始）和完全二叉树节点位置的技巧（即假如说根节点是i，那么它的左儿子=2*i， 右儿子=2*i+1）。

（如数组的下标从0开始），那么（即假如说根节点是i，那么它的左儿子=2*i+1， 右儿子=2*i+2）

第二部分：代码实现前的分析

基本取值范围设置：

①非叶子结点的索引下标取值范围（以数组下标从0开始为例）

除了最底层外，其他层的节点都是满的，而最底层从左到右填充。因此，对于一个有n个元素的堆，最后一个元素的索引是n-1，其父节点的索引是(n-1-1)/2 = (n-2)/2。

②对于非叶子结点，肯定有左节点，完全二叉树可能有右结点，也可能没有有右结点。

只有最后一个非叶子结点可能出现上述情况，其他的非叶子结点都是左右节点都有。

③最后一个非叶子结点是否有右结点的判断方式

当我们想要检查一个节点是否有右子节点时，我们需要确保右子节点的索引不会超出数组的范围。因此，我们使用 2 * i + 2 < n 这个条件来判断。如果这个条件成立，说明右子节点的索引小于数组的长度 n，即存在右子节点；否则，说明右子节点的索引超出了数组范围，不存在右子节点。

第三部分：代码实现

#include <stdio.h>
#include <stdio.h>

int jisuan1(int arr[],int n)//如果是最大堆，返回1，否则返回0
{
    for(int i=0;i<=(n-2)/2;i++)
    {
        //左节点判断
        if(arr[i]<arr[2*i+1])
        {
            return 0;
        }
        if((2*i+2<n)&&(arr[i]<arr[2*i+2]))
        {
            return 0;        }
    }
    return 1;
}

int jisuan2(int arr[],int n)//如果是最小堆，返回1，否则返回0
{
    for(int i=0;i<=(n-2)/2;i++)
    {
        //左节点判断
        if(arr[i]>arr[2*i+1])
        {
            return 0;
        }
        if((2*i+2<n)&&(arr[i]>arr[2*i+2]))
        {
            return 0;        }
    }
    return 1;
}

int main() {
    int arr[] = {3,1,4,1,5,9,2,6,5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result=jisuan1(arr,n);
    if(result==1)
    {
        printf("这是一个最大堆。");
    }
    else
    {
        int result2=jisuan2(arr,n);
        if(result2==1)
        {
            printf("这是一个最小堆。");
        }
        else
        {
            printf("这不是一个有效的堆。");
        }
    }
    return 0;
}

第四部分：效果分析展示

（1）最大堆

输入数组元素为： int arr[] = {5,2,1};

（2）最小堆

输入： int arr[] = {1,2,6,5,7,13};

（3）不是最大最小堆

输入数组元素为：int arr[] = {3,1,4,1,5,9,2,6,5};

好啦，希望能够帮助到大家！