浙江大学数据结构习题mooc堆

### 关于浙江大学MOOC平台上的数据结构课程中堆的习题

在浙江大学MOOC平台上，数据结构课程确实提供了有关堆（Heap）的相关编程练习题。这些题目旨在帮助学生理解和掌握堆这种重要的数据结构及其应用。

#### 题目描述
在一个典型的堆操作习题中，可能会涉及到构建最大堆或最小堆，并实现基本的操作如插入新元素、删除根节点等。具体来说，在浙大数据结构课程中的某一章节[^3]，存在这样一道典型题目：

给定一系列整数输入序列，要求按照如下规则处理：
- 构建一个最大堆；
- 对每次读入的新数值执行相应命令：“I x”表示向堆内插入值x，“D”则代表移除当前的最大值即堆顶元素；
- 输出最终形成的堆状态以及每一步骤后的变化情况；

此类型的练习有助于深入理解二叉堆的工作原理及其实现方法。

#include <iostream>
using namespace std;

const int MAX_SIZE = 1e6 + 5;
int heap[MAX_SIZE], size = 0;

void siftUp(int idx){
    while(idx > 1 && heap[idx / 2] < heap[idx]){
        swap(heap[idx], heap[idx / 2]);
        idx /= 2;
    }
}

void insert(int val){
    heap[++size] = val;
    siftUp(size);
}

void siftDown(int idx){
    int maxPos = idx;
    if (idx * 2 <= size && heap[maxPos] < heap[idx * 2])
        maxPos = idx * 2;
    if (idx * 2 + 1 <= size && heap[maxPos] < heap[idx * 2 + 1])
        maxPos = idx * 2 + 1;
    
    if(maxPos != idx){
        swap(heap[idx], heap[maxPos]);
        siftDown(maxPos);
    }
}

void delMax(){
    if(!size) return ;
    heap[1] = heap[size--];
    siftDown(1);
}

上述代码实现了简单的最大堆管理功能，包括`insert()`用于添加新的元素到堆里，而`delMax()`负责安全地移除并返回最大的那个元素。通过不断调整父子结点之间的关系来维持整个树形结构满足堆性质的要求。