HC01-判断数组是否表示小根堆

代码实现

// 函数 isMinHeap：判断数组是否表示小根堆
// 参数说明：
// A[] - 待检查的数组
// n - 数组中元素个数
bool isMinHeap(int A[], int n) {
    // 遍历所有非叶子结点（即有子结点的结点）
    for (int i = 0; i <= (n - 2) / 2; i++) {
        // 检查左子结点：父结点值应 ≤ 左子结点值
        if (A[i] > A[2 * i + 1]) {
            return false;  // 违反小根堆性质
        }

        // 检查右子结点：父结点值应 ≤ 右子结点值
        // 首先确保右子结点存在（数组下标不越界）
        if (2 * i + 2 < n && A[i] > A[2 * i + 2]) {
            return false;  // 违反小根堆性质
        }
    }

    // 所有结点都满足小根堆性质
    return true;
}

---

代码逻辑解析

1. 小根堆的定义

• 完全二叉树：除最后一层外，其它各层都被完全填满
• 堆性质：每个父结点的值 ≤ 其子结点的值
• 数组表示：按层次遍历顺序存储

2. 数组与完全二叉树的对应关系

// 数组下标从0开始的完全二叉树：
// 下标为 i 的结点：
// - 父结点下标：(i-1)/2 (i > 0)
// - 左子结点下标：2*i + 1
// - 右子结点下标：2*i + 2

// 示例数组：[1, 3, 6, 5, 9, 8]
// 对应的完全二叉树：
//        1(0)
//       /    \
//     3(1)   6(2)
//    /  \    /
//  5(3) 9(4) 8(5)

3. 执行流程图解

数组：[1, 3, 6, 5, 9, 8]，n = 6

需要检查的非叶子结点范围：i = 0 到 (n-2)/2 = (6-2)/2 = 2
即检查下标 0, 1, 2 的结点

检查过程：
i = 0（结点值=1）：
  - 左子结点：A[1] = 3，1 ≤ 3 ✓
  - 右子结点：A[2] = 6，1 ≤ 6 ✓

i = 1（结点值=3）：
  - 左子结点：A[3] = 5，3 ≤ 5 ✓
  - 右子结点：A[4] = 9，3 ≤ 9 ✓

i = 2（结点值=6）：
  - 左子结点：A[5] = 8，6 ≤ 8 ✓
  - 右子结点：不存在（2*2+2 = 6 ≥ 6）

结果：是小根堆

4. 边界条件分析

// 边界计算：(n-2)/2 的含义
// 在完全二叉树中，最后一个非叶子结点的下标

// 示例验证：
// n = 1：(1-2)/2 = -1，无非叶子结点
// n = 2：(2-2)/2 = 0，下标0是非叶子结点
// n = 3：(3-2)/2 = 0，下标0是非叶子结点
// n = 4：(4-2)/2 = 1，下标0,1是非叶子结点
// n = 5：(5-2)/2 = 1，下标0,1是非叶子结点
// n = 6：(6-2)/2 = 2，下标0,1,2是非叶子结点

---

时间复杂度分析

1. 循环次数

• 非叶子结点个数：⌊(n-1)/2⌋
• 循环上界：(n-2)/2
• 循环次数：O(n/2) = O(n)

2. 每次循环操作

• 两次比较操作：O(1)
• 一次数组访问：O(1)
• 每次操作：O(1)

3. 总体时间复杂度

O(n)，其中 n 是数组长度

---

空间复杂度分析

1. 额外空间使用

• 循环变量 i：O(1)
• 临时计算：O(1)
• 无递归调用：O(1)

2. 总体空间复杂度

O(1)，只使用常量级额外空间

---

较难理解部分的说明

1. 为什么只需要检查非叶子结点？

// 小根堆性质：父结点 ≤ 子结点
// 叶子结点没有子结点，无需检查
// 只需检查有子结点的结点（非叶子结点）

// 完全二叉树中非叶子结点的范围：
// 最后一个结点下标：n-1
// 最后一个结点的父结点下标：(n-1-1)/2 = (n-2)/2
// 所以非叶子结点下标范围：0 到 (n-2)/2

// 示例验证：
// 数组：[1, 2, 3, 4, 5]，n = 5
// 最后一个结点：5（下标4）
// 最后一个结点的父结点：(4-1)/2 = 1
// 非叶子结点：下标0,1（对应值1,2）

2. 右子结点存在性检查

// 为什么要检查 2*i+2 < n？
// 因为完全二叉树的最后一层可能不满，右子结点可能不存在

// 示例：
// 数组：[1, 2, 3, 4]，n = 4
// 结点0：左子结点1，右子结点2 ✓
// 结点1：左子结点3，右子结点？（下标4 ≥ 4，不存在）

// 树形结构：
//     1(0)
//    /    \
//  2(1)   3(2)
//  /
// 4(3)

3. 边界情况验证

// 特殊情况测试：

// 空数组：n = 0
// 循环条件：0 ≤ (0-2)/2 = -1，不进入循环，返回true ✓

// 单元素：n = 1，数组[5]
// 循环条件：0 ≤ (1-2)/2 = -1，不进入循环，返回true ✓

// 两元素：n = 2，数组[3, 5]
// 循环条件：0 ≤ (2-2)/2 = 0，检查i=0
// 左子结点：A[1] = 5，3 ≤ 5 ✓，返回true

// 三元素：n = 3，数组[3, 5, 1]
// 循环条件：0 ≤ (3-2)/2 = 0，检查i=0
// 左子结点：A[1] = 5，3 ≤ 5 ✓
// 右子结点：A[2] = 1，3 > 1 ✗，返回false

---

延伸知识点

1. 大根堆判断

// 判断数组是否是大根堆
bool isMaxHeap(int A[], int n) {
    for (int i = 0; i <= (n - 2) / 2; i++) {
        // 大根堆性质：父结点 ≥ 子结点
        if (A[i] < A[2 * i + 1]) {
            return false;
        }
        if (2 * i + 2 < n && A[i] < A[2 * i + 2]) {
            return false;
        }
    }
    return true;
}

2. 通用堆判断

// 通用堆判断函数
typedef enum { MIN_HEAP, MAX_HEAP } HeapType;

bool isHeap(int A[], int n, HeapType type) {
    for (int i = 0; i <= (n - 2) / 2; i++) {
        if (type == MIN_HEAP) {
            if (A[i] > A[2 * i + 1]) return false;
            if (2 * i + 2 < n && A[i] > A[2 * i + 2]) return false;
        } else {
            if (A[i] < A[2 * i + 1]) return false;
            if (2 * i + 2 < n && A[i] < A[2 * i + 2]) return false;
        }
    }
    return true;
}

3. 堆的构建与验证

// 构建小根堆
void buildMinHeap(int A[], int n) {
    // 从最后一个非叶子结点开始向上调整
    for (int i = (n - 2) / 2; i >= 0; i--) {
        minHeapify(A, n, i);
    }
}

// 验证堆性质的调试版本
bool isMinHeap_debug(int A[], int n) {
    printf("检查数组是否为小根堆：");
    for (int i = 0; i < n; i++) {
        printf("%d ", A[i]);
    }
    printf("\n");

    for (int i = 0; i <= (n - 2) / 2; i++) {
        printf("检查结点%d(值=%d):\n", i, A[i]);

        if (A[i] > A[2 * i + 1]) {
            printf("  左子结点%d(值=%d)违反性质: %d > %d\n", 
                   2*i+1, A[2*i+1], A[i], A[2*i+1]);
            return false;
        }

        if (2 * i + 2 < n && A[i] > A[2 * i + 2]) {
            printf("  右子结点%d(值=%d)违反性质: %d > %d\n", 
                   2*i+2, A[2*i+2], A[i], A[2*i+2]);
            return false;
        }

        printf("  满足堆性质\n");
    }

    printf("是小根堆\n");
    return true;
}

4. 堆相关操作

// 堆化操作（维护小根堆性质）
void minHeapify(int A[], int n, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && A[left] < A[smallest]) {
        smallest = left;
    }

    if (right < n && A[right] < A[smallest]) {
        smallest = right;
    }

    if (smallest != i) {
        swap(&A[i], &A[smallest]);
        minHeapify(A, n, smallest);
    }
}

// 插入元素并维护堆性质
void insertToMinHeap(int A[], int* n, int key) {
    A[(*n)++] = key;
    int i = *n - 1;

    // 向上调整
    while (i != 0 && A[(i-1)/2] > A[i]) {
        swap(&A[i], &A[(i-1)/2]);
        i = (i-1)/2;
    }
}

5. 实际应用场景

// 优先队列验证
bool validatePriorityQueue(int queue[], int size) {
    return isMinHeap(queue, size);
}

// 堆排序中间状态检查
bool checkHeapProperty(int heap[], int size, int phase) {
    switch(phase) {
        case BUILD_PHASE:
            return isMinHeap(heap, size);
        case EXTRACT_PHASE:
            // 提取过程中可能暂时违反堆性质
            return true;
        default:
            return false;
    }
}

// 内存管理中的堆验证
bool validateMemoryHeap(int* memory_blocks, int count) {
    return isMinHeap(memory_blocks, count);
}

6. 理论扩展

数学性质分析：

小根堆的性质：
1. 完全二叉树结构
2. ∀i, A[i] ≤ A[2*i+1] 且 A[i] ≤ A[2*i+2]（如果子结点存在）

时间复杂度理论分析：
- 需要检查每个非叶子结点：Ω(n/2)
- 该算法恰好检查 n/2 个结点：O(n/2)
- 因此是渐近最优的算法

与其他数据结构的比较：

// 与BST的比较：
// BST：中序遍历有序
// 堆：父结点与子结点有大小关系，但兄弟结点无序

// 与有序数组的比较：
// 有序数组：全局有序
// 堆：局部有序（父-子关系）

// 验证复杂度：
// 有序数组验证：O(n)
// BST验证：O(n)
// 堆验证：O(n)

堆的应用扩展：

// 多叉堆（d-ary heap）
bool isDaryMinHeap(int A[], int n, int d) {
    for (int i = 0; i < (n-1)/d; i++) {
        // 检查d个子结点
        for (int j = 1; j <= d; j++) {
            int child = d*i + j;
            if (child < n && A[i] > A[child]) {
                return false;
            }
        }
    }
    return true;
}

// 左式堆、斜堆等特殊堆的验证需要额外信息

这种方法体现了完全二叉树性质利用和局部约束检查的完美结合。通过理解堆的数组表示规律，只需要线性时间就能验证全局性质，是数据结构算法中的经典高效设计。同时展示了如何通过数学分析确定需要检查的结点范围，避免了不必要的计算。