堆

//堆的定义及基本操作

/* //堆是一颗完全二叉树 //堆一般用优先队列实现，优先队列默认实现大顶堆 //对于完全二叉树，比较简洁的实现方法是 //使用数组来是实现存储完全二叉树。 //这样结点就会按层序存储于数组中， //其中第一个结点将存储于数组中的1号位 //数组i号位表示的结点的左孩子就是2i 号位 // 右孩子就是（2i+1）号位。 */ 



//定义堆

const int maxn=100;

//heap 为堆，n为元素个数

int heap[maxn],n=10;



//向下调整 

//对heap数组在[low，high]范围进行向下调整
//其中low为欲调整结点的数组下标
// high一般为堆的最后一个元素的数组下标 

void down_adjust(int low,int high) 
{


    int i=low,j=i*2;    //i为欲调整结点，j为其左孩子

    while(j<=high)      //存在孩子结点 
    {
        //如果右孩子存在，且右孩子的值大于左孩子 

        if( j+1 <= high && heap[j+1] > heap[j]  )
        {
            j=j+1;  //让j存储右孩子下标 
        }

        //如果孩子中最大的权值比欲调整结点i大 

        if( heap[j]>heap[i] )
        {
            //交换最大权值孩子和欲调整结点i 
            swap( heap[j],heap[i] );


            //始终保持i为预调整结点，j为i的左孩子 
            i=j;
            j=2*i;




        }
        else
        {

            //孩子的权值均比欲调整结点i小，调整结束 
            break;  

        }




    }









}




//假设序列中元素个数是n，二叉树的叶子结点是n/2
//因此，数组下标在[1,n/2]范围内的结点都是非叶子节点
//在这里，要注意一下，是倒着枚举
//为什么呢？
//这种做法保证每个结点都是以其为根结点的子树中的权值最大的结点 


//建堆

void create_heap() 
{
    for(int i=n/2;i>=1;i--)
    {
        down_adjust(i,n);

    }

}



//删除堆顶元素，只需要最后一个元素覆盖堆顶元素，
//然后对根结点进行调整即可 

//删除堆顶元素
void delete_top()
{
    //用最后一个元素覆盖堆顶元素，并让元素个数减1 
    heap[1]=heap[n--];

    //向下调整堆顶元素 
    down_adjust(1,n);



}



//向上调整
//向堆中添加一个元素需要用到 向上调整

//对heap数组在[low,high]范围进行向上调整
//其中low一般设置为1，high表示欲调整结点的数组下标


void up_adjust(int low,int high) 
{

    //i为欲调整结点，j为其父亲 
    int i=high,j=i/2;

    //父亲在[low，high]范围内 
    while(j>=low)
    {
        //父亲权值小于欲调整结点i的权值
        if(heap[j]<heap[i])
         {

            //交换父亲和欲调整子结点 
            swap(heap[j],heap[i]);

            //始终保持i为欲调整结点、j为i的父亲 
            i=j;
            j=i/2;


         }
        else
        {
            //父亲权值比欲调整结点i的权值大，调整结束。 
            break;

        } 



    }





}




//添加元素x

void insert(int x) 
{
    //让元素个数加1，然后将数组末位赋值为x 
    heap[++n]=x;

    //向上调整加入的结点n 
    up_adjust(1,n);

}




//堆排序，取出大顶堆的堆顶元素，并将其与
//待排序序列的末尾元素，交换
//循环操作，直到堆中只有一个元素


//详细过程见 算法笔记 P339


//堆排序 

void heap_sort() 
{
    //建堆 
    create_heap();

    //倒着枚举，直到堆中只有一个元素

    for(int i=n;i>1;i--) 
    {
        //交换heap[i]与堆顶 
        swap(heap[i],heap[1]);
        down_adjust(1,i-1); 



    }


}