堆的定义和基本操作代码

//85 55 82 57 68 92 99 98 66 56

#include<iostream>
#define maxn 1000
using namespace std;

int heap[maxn];
int n = 10;

//big - top
void downjust(int low, int high)
{
    int i = low, j = 2*i;
    while(j <= high)
    {
        if(j + 1 <= high && heap[j+1] > heap[j])
        {
            j = j + 1;
        }

        if(heap[j] > heap[i])
        {
            swap(heap[j], heap[i]);
            i = j;
            j = 2*i;
        }else
        {
            break;
        }
    }
}

void createheap()
{
    for(int i = n/2; i >= 1; i--)
    {
        downjust(i, n);
    }
}

void deletetop()
{
    heap[1] = heap[n--];
    downjust(1, n);
}

void upadjust(int low, int high)
{
    int i = high, j = i/2;
    while(j >= low)
    {
        if(heap[i] > heap[j])
        {
            swap(heap[i], heap[j]);
            i = j;
            j = i/2;
        }else
        {
            break;
        }
    }
}

void insert(int x)
{
    heap[++n] = x;
    upadjust(1, n);
}

//heapsort
void heapsort()
{
    createheap();
    for(int i = n; i > 1; i--)
    {
        swap(heap[i], heap[1]);
        downjust(1, i-1);
    }
}

int main()
{
    for(int i = 1; i<= n; i++)
    {
        scanf("%d", &heap[i]);
    }




    //排序之后只能保证根节点大于子节点
    for(int i = 1; i <= n; i++)
    {
        printf("%d ", heap[i]);
    }

    cout << endl;
    deletetop();

    for(int i = 1; i <= n; i++)
    {
        printf("%d ", heap[i]);
    }

    cout << endl;
    insert(100);

    for(int i = 1; i <= n; i++)
    {
        printf("%d ", heap[i]);
    }

    cout << endl;
    heapsort();

    for(int i = 1; i <= n; i++)
    {
        printf("%d ", heap[i]);
    }


    return 0;
}
//85 55 82 57 68 92 99 98 66 56

#include