堆的简单实现

关于堆不做过多介绍

堆就是儿子的值一定不小于父亲的值并且树的节点都是按照从上到下，从左到右紧凑排列的树。

（本文为二叉堆）

具体实现并不需要指针二叉树，用数组储存并且利用公式找到父子即可。

父：(i-1)/2

子:i*2+1,i*2+2

插入：首先把新数字放到堆的末尾，也就是右下角，然后查看父的数值，需要交换就交换，重复上述操作直到不需交换

删除：把堆的第一个节点赋值为最后一个节点的值，然后删除最后一个节点，不断向下交换。

（两个儿子：严格来说要选择数值较小的那一个）

时间复杂度：和深度成正比，所以n个节点是O(logN)

  

   

    

     

    
    

     

      int heap[MAX_N],sz=0;
     
    
   

    

     

    
    

     

      //定义数组和记录个数的变量
     
    
  
 

插入代码：

  

   

    

     

    
    

     

      void push(int x)
     
    
   

    

     

    
    

     

      {//节点编号
     
    
   

    

     

    
    

     
 int i=sz++;
     
    
   

    

     

    
    

     
 while(i>0)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int p=(i-1)/2;//父
     
    
   

    

     

    
    

     
 if(heap[p]<=x)break;//直到大小顺序正确跳出循环
     
    
   

    

     

    
    

     

       heap[i]=heap[p];//把父节点放下来
     
    
   

    

     

    
    

     

       i=p;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       heap[i]=x;//最后把自己放上去
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
  
 

弹出：

  

   

    

     

    
    

     

      int pop()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int ret=heap[0];//保存好值，最后返回
     
    
   

    

     

    
    

     
 int x=heap[--sz];
     
    
   

    

     

    
    

     
 while(i*2+1<sz)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int a=i*2+1;//左孩子
     
    
   

    

     

    
    

     
 int b=i*2+2;//右孩子
     
    
   

    

     

    
    

     
 if(b<sz && heap[b]<heap[a])a=b;//找最小
     
    
   

    

     

    
    

     
 if(heap[a]>=x)break;//直到不需要交换就退出
     
    
   

    

     

    
    

     

       heap[i]=heap[a];//把儿子放上来
     
    
   

    

     

    
    

     

       i=a;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       head[i]=x;//下沉到正确位置
     
    
   

    

     

    
    

     
 return ret;//返回
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/81706288