本文共 2752 字，大约阅读时间需要 9 分钟。

堆（Heap）实现技术说明

本文将详细介绍堆数据结构的实现与应用，重点包括堆的构建、堆排序以及常用操作的实现方法。

堆的基本实现

堆是一种特殊的数组，可以看作是一个完全二叉树。数组的最左边是一个根结点，其左右子节点依次类推。堆分为两种形式：

• 最小堆：父节点的值小于或等于任一子节点的值，适用于依次删除最小值的操作。
• 最大堆：父节点的值大于或等于任一子节点的值，适用于依次删除最最大值的操作。

本代码实现使用最小堆结构。

1.1 siftdown 函数

siftdown 是“下沉”函数，用于在已知位置上的元素快速定位目标位置，将较大的元素下沉到正确的位置。以下是 sifthood 函数的实现：

void siftdown(int i) {
    int t, flag = 0;
    while (2 * i <= n && flag == 0) {
        if (tree[i] > tree[2 * i]) {  // 建立最大堆时的判断条件
            t = 2 * i;
        } else {
            t = i;
        }
        if (2 * i + 1 <= n) {  // 如果有右孩子节点
            if (tree[t] > tree[2 * i + 1]) {  // 建立最大堆时的判断条件
                t = i * 2 + 1;
            }
        }
        if (t != i) {  // 只有当位置改变时才交换
            swap(tree[t], tree[i]);
        } else {
            flag = 1;  // 如果无法下沉，标志置为1，退出循环
        }
        i = t;  // 位置移动到当前找到的正确位置
    }
}

1.2 siftup 函数

siftup 是“上升”函数，用于将新插入或已移动到根部的元素上移至正确的位置，以下是 siftup 函数的实现：

void siftup(int i) {
    if (i == 1) return;  // 根节点位置不能再上升
    while (tree[i] < tree[i * 2]) {  // 如果当前节点大于左孩子，则继续上移
        swap(tree[i], tree[i * 2]);
        i /= 2;
    }
}

1.3 堆排序（Heapsort）

堆排序是通过多次交换根节点与最末尾元素，然后对剩余元素进行下沉操作完成的。以下是 heap sort 的实现：

void heapsort() {
    while (n > 1) {
        swap(tree[1], tree[n]);  // 交换根节点和末尾节点
        n--;                  // 数组大小减1
        siftdown(1);            // 调用下沉函数
    }
}

1.4 删除最大元素

删除最大元素的实现方法如下：

int deletmax() {
    int t = tree[1];  // 取出根节点的值
    tree[1] = tree[n];  // 将末尾元素移动到根节点
    n--;                 // 数组大小减1
    siftdown(1);          // 调用下沉函数调整堆序
    return t;             // 返回被删除的最大元素
}

2. 主函数（Main 函数）

int main(void) {
    cin >> n;             // 读取输入的元素个数
    for (int i = 1; i <= n; i++) {
        cin >> tree[i];     // 读取输入的元素并存储
    }
    // 建立最小堆
    for (int i = n / 2; i >= 1; i--) {   // 从尾部开始向上构建
        siftdown(i);                    // 调用下沉函数
    }
    // 堆排序
    heapsort();                  // 调用堆排序函数
    // 输出原堆状态
    cout << "最小堆： ";
    for (int i = 1; i <= n; i++) {
        cout << tree[i] << " ";
    }
    cout << endl;
    // 删除顶部元素
    delate();                   // 删除最大元素的函数
    cout << "删除后的堆： ";    // 输出删除后的堆状态
    for (int i = 1; i <= n; i++) {
        cout << tree[i] << " ";
    }
    cout << endl;
    // 输入需要插入的数字并插入堆中
    int m;
    do {
        cout << "输入需要插入的数字： ";
        cin >> temp;              // 读取输入的数字
        tree[n + 1] = temp;        // 插入新元素
        siftup(n + 1);             // 调用上升函数
        n++;                       // 数组大小增加1
        cout << "插入后的堆： ";    // 输出插入后的堆状态
        for (int i = 1; i <= n; i++) {
            cout << tree[i] << " ";
        }
        cout << endl;
    } while (m < 5);           // 假设最多插入5个元素
}

3. 总结

通过上述实现，可以轻松实现堆数据结构的基本操作，包括插入、删除以及排序等功能。本文详细介绍了堆的构建和优化方法，可供在实际项目中参考使用。