binary heaps:
小根堆:父节点比儿子节点的值小

（1）小根堆的创建：
   1.复制堆数组
   2.找到最初的调整位置，即最后一个分支结点
   3.从该分支节点处自上向下逐步调整形成堆
   4.不断向前找一个分支结点，执行操作3
   时间复杂度：O(n)

（2）小根堆找最小：
  直接就是根节点

  时间复杂度：O(1)

 (3)小根堆的插入：
  1. 将待插入元素插入已建成堆的最后面
  2. 沿着插入位置所在的分支逐步向上调整
  时间复杂度：O(logn)

 (4)小根堆最小元素的删除：
   1. 将顶元素删除
   2. 将数组中最后一个元素放到堆顶
   3. 自顶向下调整
   时间复杂度：O(logn)

(5)修改已知下标的小根堆中的元素

直接改

时间复杂度：O(1)

代码实现：

#include <stdio.h>
#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>

using namespace std;

struct heap_node{
   int var;
   int pos;  
};

int swap(heap_node & a,heap_node & b);
int shifit(vector<heap_node> & a, int i, int n);

class binary_heap{
   public:
       int num;
       vector<heap_node> element;
       binary_heap(int n)
       {
           num = n;
           element.resize(n);
       }

       binary_heap(vector<int> a)
       {
           num = a.size();
           element.resize(a.size());
           for(int i=0;i<element.size();i++)
           {
               element[i].var = a[i];
               element[i].pos = i;
           }    

       }  

       ~binary_heap()
       {
           element.clear();
       }
       int create()//将一个乱序的一维数值改为>小根堆
       {
           for(int i=(num-1)/2;i>=0;i--)
           {
               shifit(element,i,num);
           }
           return 0;
       }

       int print_heap()
       {
                        for(int i=0;i<num;i++)
                       {
                               cout<<setw(5)<<element[i].pos<<" ";
                       }
                       cout<<endl;
           for(int i=0;i<num;i++)
           {
               cout<<setw(5)<<element[i].var<<" ";
           }
           cout<<endl;
       }
       int print_min()
       {
           cout<<"the min element in heap "<<element[0].var<<" "<<element[0].pos<<endl;
           return 0;
       }
       int delete_min()
       {
           swap(element[0],element[num-1]);
           num --;
           shifit(element,0,num);
           return 0;    
       }          

       int insert_element(int a)
       {
           if(element.size()>num)
           {
               element[num].var = a;
               element[num].pos = num;
           }
           else
           {
               heap_node temp;
               temp.var = a;
               temp.pos = num;
               element.push_back(temp);
           }
           num++;
           int chi = num-1;
           int par;
           while((par = chi/2)>=0)
           {
               if(element[chi].var<element[par].var)
               {
                   swap(element[chi],element[par]);
                   chi = par;      
               }
               else
                   break;
           }

           return 0;  
       }
           int change_element(int index, int var)
           {
                             element[index].var = var;
                           
                           return 0;
           }  

};

int swap(heap_node & a,heap_node & b)
{
   heap_node temp;
   temp.var = a.var;
   temp.pos = a.pos;
   a.var = b.var;
   a.pos = b.pos;  
   b.var = temp.var;
   b.pos = temp.pos;
   return 0;
}
int shifit(vector<heap_node> & a, int i, int n)
{
   int j;
   while((j=2*i+1)<n)
   {
       if(j<n-1 && a[j+1].var<a[j].var)
           j++;
       if(a[i].var>a[j].var)
       {
           swap(a[i],a[j]);
       }    
       i=j;  
   }
   return 0;
}