堆的插入操作

本文主要是介绍堆的插入操作，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

以小根堆为例

1、交换法 --- 插入堆尾部，然后调整堆

int heap[100];
int len;
void insert(int value)
{
   len++;  //0号位置不存储数据，len+1为插入位置
   heap[len] = value; //插在堆尾部
   int son,fa;
   son = len;
   fa = son/2; //0号位置不存储数据
   while(son > 1)
   {
     if(heap[son] >= heap[fa])
         break;
    
     //若heap[son] < heap[fa] 则交换
     swap(heap[son],heap[fa]);
     
     //节点上移
     son = fa;
     fa = son/2; 
    
   }
   

}

 2、下移法  --- 找合适的插入点，然后插入；比交换法效率高

int heap[100];
int len;

void insert(int value)
{
   int son,fa;
   son = len + 1;
   fa =  son / 2;
   
   //找合适的插入点
   while(son > 1)
   {
     if(value >= heap[fa])
         break;
    
     // value < heap[fa] fa下移
     heap[son] = heap[fa]; //比交换操作快

     //节点上移
     son = fa;
     fa = son /2;
   }
   //插入到son位置
   heap[son] = value;
}

 3、哨兵法 --- 0号位置存储足够小的数(小根堆)，value依次与fa的值比较，较大的数下移

int heap[100];
int len;

void insert(int value)
{  
   heap[0] = -10000; //0号位置存储足够小的数 哨兵

   int son,fa;
   son = len + 1;
   fa = son/2;
   
   //找插入点
   while(value < heap[fa]) //value < heap[fa] fa下移
   {
     heap[son] = heap[fa]; //fa上移
     //节点上移
     son = fa;
     fa = son /2;
   }

   heap[son]= value;
}

 }

这篇关于堆的插入操作的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！