#include

using namespace std;

int heap[100];  

  

//下滑操作  

void siftDown(int start,int end)  

{  

    //将start号结点向下调整直到end  

    int i=start,j=2*i;  

    heap[0]=heap[i]; //用heap[0]来临时保存i结点的值  

    while(j<=end)  

    {  

        //有右孩子并且右孩子比左孩子小时，将j保存右孩子  

        if(jheap[j+1]) ++j;  

        //比j号结点小时，不需调整  

        if(heap[0]<=heap[j])   

            break;  

        else  

        {  

            //向下调整  

            heap[i]=heap[j];  

            i=j;  

            j=2*j;  

        }  

    }  

    heap[i]=heap[0];  

}  

  

//生成小根堆  

void createHeap(int n)  

{  

    memset(heap,0,sizeof(heap)); //初始化heap数组  

    cout<<"Enter values:"<<endl;  

    //从下标1开始存  

    for(int i=1;i<=n;++i)  

        cin>>heap[i];  

  

    int currentPos=n/2; //找到开始调整的位置(即最后一个结点双亲的位置)  

    while(currentPos>0)  

    {  

        siftDown(currentPos,n);  

        --currentPos;  

    }  

}  

  

//向上调整的函数  

//将结点start调整到根结点1为止  

void siftUp(int start)  

{  

    int j=start,i=j/2;  

    heap[0]=heap[j];  

    while(j>0)  

    {  

        if(heap[i]<=heap[0])  

            break;  

        else  

        {  

            //向上调整工作  

            heap[j]=heap[i];  

            j=i;  

            i=i/2;  

        }  

    }  

    heap[j]=heap[0];  

}  

  

//插入操作的实现  

bool insert(int x,int& num)  

{  

    ++num;  

    heap[num]=x;  

    siftUp(num);  

      

    return true;  

}  

  

//删除操作  

bool removeMin(int& num)  

{  

    heap[1]=heap[num]; //填补树根  

  

    --num;  

    siftDown(1,num); //将根结点下滑到尾部  

    return true;  

}  

  

//前序遍历  

void preOrder(int i,int num)  

{  

    if(i<=num)  

    {  

        cout<<heap[i]<<" ";  

  

        preOrder(2*i,num);  

        preOrder(2*i+1,num);  

    }  

}  

int main()  

{  

    int n=0;  

    cout<<"Enter the num:";  

    cin>>n;  

    createHeap(n);  

    preOrder(1,n);  

    cout<<endl;  

  

    int val=0;  

    cout<<"Enter value to insert:";  

    cin>>val;  

    insert(val,n);  

    preOrder(1,n);  

    cout<<endl;  

  

    removeMin(n);  

    preOrder(1,n);  

    cout<<endl;

}

赞0 2326次