数据结构：如何判断给定的序列是否为大根堆？

数据结构：如何判断给定的序列是否为大根堆？

引用

CSDN

1.

https://blog.csdn.net/2301_80011650/article/details/138972953

堆是一种特殊的数据结构，通常被看作是一棵完全二叉树。在计算机科学中，堆常用于在频繁变动的数据集中快速找出最大值或最小值。本文将详细介绍如何判断一个给定的序列是否为大根堆。

在计算机科学中，堆是一类特殊的数据结构的统称，通常可以被看作是一棵完全二叉树。需要注意的是，堆不一定是完全二叉树，只是为了方便存储和索引，我们通常用完全二叉树的形式来表示堆。

堆的物理结构本质上是顺序存储的，通常是线性排列的数组，但在逻辑上，它不是线性的，而是类似于完全二叉树的结构。堆分为两种基本类型：最大堆（也称为大根堆）和最小堆（也称为小根堆）。在最大堆中，每个节点的值都不小于其子节点的值；而在最小堆中，每个节点的值都不大于其子节点的值。堆的作用常用来在频繁变动的数据集中找出最大值或最小值。堆的根节点通常被称为堆顶，而最后一个节点称为堆尾，节点总数称为堆长度。常见的堆实现包括二叉堆和斐波那契堆等。

这篇文章只讨论大根堆。小根堆的原理与之类似。

下图展示了一个小根堆的例子，每个节点的值都不大于其子节点的值：

而下图展示了一个大根堆的例子：

对于一棵完全二叉树，我们可以知道以下性质：

• 对于任意一个结点（1 <= i <= n）：
• 如果i == 1，则结点i即为二叉树的根，无双亲
• 如果i > 1，则其双亲结点为[i / 2]
• 如果2 * i > n，则结点i无左孩子（结点i为叶子结点）
• 否则其左孩子结点为2 * i
• 如果2 * i + 1 > n，则结点i无右孩子
• 否则其右孩子为2 * i + 1
• 如果有n个结点，那么最后一个非叶子结点下标为n/2-1（下标从0开始）

如果完全没有接触完全二叉树的话，这里我简单给个例子：

给定序列
则建立的完全二叉树为：（其实就是前序遍历的顺序建立（根左右））

所以，我们就可以利用以上性质来判断堆是否为大根堆（或小根堆）了。

以下给出代码：

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

// 判断一个序列是否为大根堆
bool isMaxHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {    // 根结点下标为0
        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;
        // 检查左子节点是否存在且大于父节点
        if (leftChild < n && arr[leftChild] > arr[i])   // 如果左孩子大于父节点
            return false;
        // 检查右子节点是否存在且大于父节点
        if (rightChild < n && arr[rightChild] > arr[i])  // 如果右孩子大于父节点
            return false;
    }
    return true;
}

int main() {
    int arr[] = {90, 15, 10, 7, 12, 2};  // 给出一个任意序列
    int n = sizeof(arr) / sizeof(arr[0]);
    if (isMaxHeap(arr, n))
        printf("The sequence is a max heap.\n");
    else
        printf("The sequence is not a max heap.\n");
    return 0;
}

判断是否为小根堆的情况类似，大家可以自己尝试，有手就行！