堆的两种实现（数组和STL）

基本思想：两种操作都跟树的深度成正比，所以复杂度 O(log(n)) ;

push():在向堆中插入数值时，首先在堆的末尾插入该数值，然后不断向上提直到没有大小颠倒为止。

pop(): 从堆中取出一个数值时，首先把堆的最后一个节点的数值复制到根节点上，并且删除最后一个节点，然后不断向下交换直到没有大小颠倒为止，在向下交换的时候，如果有两个儿子，那就选择数值较小的（如果可以交换的话）进行交换。

数组实现：

 #include <cstdio>

 const int maxn = ;

 int heap[maxn], sz=;

 void push(int x) {

     int i = sz++;

     while(i > ) {

         int p = (i-) / ;  //p是父亲节点的编号

         if(heap[p] <= x) break;  //如果没有大小颠倒则退出

         heap[i] = heap[p];  //把父亲节点 放下来 ，而把自己提上去

         i = p;

     }

     heap[i] = x;  //把 x放入 正确的位置

 }

 int pop() {

     int ret = heap[]; //最小值

     int x = heap[--sz]; //要提到根的数值

     int i = ;  //从根开始向下交换

     while(i *  +  < sz) {   //可能 只有 一个  儿子

         int a = i *  + , b = i *  + ;  //两个儿子的 编号

         if(b < sz && heap[b] < heap[a]) a=b;  //如果 右儿子存在 并且 值比 左儿子小 则交换

         if(heap[a] >= x) break; //如果不能交换 就退出

         heap[i] = heap[a];  //把儿子的  数值提上来

         i=a;

     }

     heap[i] = x;

     return ret;

 }

 int main()

 {

     push();

     push();

     push();

     push();

     push();

     int x1 = pop();

     int x2 = pop();

     printf("%d %d\n",x1,x2);

     for(int i = ; i< sz; i++)

         printf("%d ", heap[i]);

     return ;

 }

STL：

priority_queue 默认取出的是最大值。

priority_queue<int, vector<int>, greater<int> >que; 从小到大

priority_queue<int, vector<int>, less<int> >que; 从大到小

 #include <iostream>

 #include <queue>

 using namespace std;

 int main() {

     priority_queue<int> que;

     que.push();

     que.push();

     que.push();

     while(que.size()) {

         cout << que.top() << endl;

         que.pop();

     }

     return ;

 }

巴特西

堆的两种实现（数组和STL）

最新文章

热门文章

巴特西

堆的 两种实现 （数组和STL）

最新文章

热门文章

堆的两种实现（数组和STL）