数据结构 最小堆_数据结构 小堆

   堆可以进行优先队列的操作 并且复杂度可以接受 其实也可以用stl 下面就是我写的几个函数  代码不难懂 注释作用 

#include <stdio.h>
#include <string.h>
#include <string>
#include <list>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <ctype.h>
#include <iostream>
#include <assert.h>
using namespace std;
int heap[10005];
int heapsize=0;
int ans[10006];
void insert_opration(int t)//插入操作
{
    ++heapsize;
    heap[heapsize]=t;
    int k=heapsize;
    while(k!=1&&heap[k]<heap[k/2])
    {
        int save=heap[k];
        heap[k]=heap[k/2];
        heap[k/2]=save;
        k=k/2;
    }
}
void todown(int num)//向下维护堆
{
    int k=num;
    while((k*2)<=heapsize||(k*2+1)<=heapsize)
    {
        if(k*2+1>heapsize)
        {
            if(heap[k]>heap[k*2])
            {
                int save=heap[k];
                heap[k]=heap[2*k];
                heap[k*2]=save;
                return;
            }
            return;
        }
        else if(heap[k]>heap[k*2]||heap[k]>heap[k*2+1])
            {
                if(heap[k*2]<heap[k*2+1])
                {
                    int save=heap[k];
                    heap[k]=heap[2*k];
                    heap[k*2]=save;
                    k=k*2;
                }
                else
                {
                    int save=heap[k*2+1];
                    heap[2*k+1]=heap[k];
                    heap[k]=save;
                    k=k*2+1;
                }
            }
        else if(heap[k]<=heap[k*2]&&heap[k]<=heap[k*2+1])
        {
            return;
        }
    }
    return;
}
int extract_min()//提取出来最小的元素并且堆维护
{
    int save=heap[1];
    heap[1]=heap[heapsize];
    --heapsize;
    todown(1);
    for(int i=1;i<=heapsize;i++)
        cout<<heap[i]<<' ';
    cout<<endl;
    return save;
}
int heapbuild()// 把一堆杂乱的输入变成一个最小堆 复杂度0（n）
{
    for(int i=heapsize;i>=1;i--)
    {
        todown(i);
    }
    return 1;
}
void heapsort()//进行由小到大   复杂度n＊logn
{
    int cnt=heapsize;
    for(int i=1;i<=cnt;i++)
        ans[i]=extract_min();
    return;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>heap[i];
        heapsize++;
    }
    heapbuild();
    for(int i=1;i<=n;i++)
        cout<<heap[i]<<' ';
    cout<<endl;
    heapsort();
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<' ';
    }
    cout<<endl;
    return 0;
}