模拟堆

前言

用数组来模拟堆
对于堆来说是一个满二叉树，其中根节点小于左孩子和右孩子（对于小根堆来说),所以可以利用数组来模拟
其元素序号从1开始，这样的话，对于序号为x的元素来说，则2*x为其左孩子，2*x+1为其右孩子
对于堆的模拟主要使用up和down *** 作来模拟
up:即此节点与父节点来比较，如果比父节点小则与其父节点交换
down:即此节点与其左右孩子中的最小值来比较，如果比其大则与左右孩子中较小的那个孩子交换

代码

#include

using namespace std;

#define N 10010
int heap[N], cnt;

//dwon  *** 作
void down(int k)
{
    int t = k;
    if (2 * k <= cnt && heap[2 * k] <heap[t])t = 2 * k;
    if (2 * k + 1 <= cnt && heap[2 * k + 1] <heap[t])t = 2 * k + 1;
    if (t != k)
    {
        swap(heap[k], heap[t]);
        down(t);
    }
}
//up  *** 作
void up(int k)
{
    while (k / 2 && heap[k] <heap[k / 2])
    {
        swap(heap[k], heap[k / 2]);
        k = k / 2;
    }
}
//删除一个数
void del(int idx)
{
    heap[idx] = heap[cnt--];
    down(idx);
    up(idx);
}
//修改一个数
void update(int idx, int num)
{
    heap[idx] = num;
    down(idx);
    up(idx);
}
//添加一个数字
void insert(int num)
{
    heap[++cnt] = num;
    up(cnt);
}
int main()
{
    int m;
    cin >> m;
    for (int i = 0; i < m; i++)cin >> heap[++cnt];
    for (int i = cnt / 2; i; i--)down(i);
    cout << "请输入要添加的数字(-1退出):" << endl;
    int num;
    while (1)
    {
        cin >> num;
        if (num == -1)break;
        insert(num);
    }
    cout << "请输入要删除的索引(-1退出" << "索引应小于等于" << cnt << ")" << endl;
    int idx;
    while (1)
    {
        cin >> idx;
        if (idx == -1)break;
        del(idx);
    }
    cout << "请输入要修改的索引和目标值" << "(" << "索引应小于等于" << cnt << ")" << endl;
    while (1)
    {
        cin >> idx;
        if (idx == -1)break;
        cin >> num;
        update(idx, num);
    }
    cout << "堆排序如下：" << endl;
    int count = cnt;
    while (count--)
    {
        cout << heap[1] << " ";
        heap[1] = heap[cnt--];
        down(1);
    }
    return 0;
}

结果