队列和栈

特点

1.先进先出 2.先进后出

队列以及优先队列

in:3，2，5，7，8，1 out:8，7，5，3，2，1

常用成员函数

1.q.size()

2.q.empty()

3.q.push(k)

4.q.pop()

5.q.top()

注意：4和5常常在一起使用

A.头文件

#include<queue>

B.声明

priority_queue<int>q1;

默认：less

或

priority_queue<int,vector<int>,greater<int>>q2;

C.自定义结构体

struct node {
   int x,y;
   bool operator<(const node&a)
       const
   {
        return  x<a.x;
   }
   priority_queue<node>q;

D.代码

int main()
{
    int a[]={3,1,4,2,6};
    int len=sizeof(a)/sizeof(int);
    for(int i=0;i<=len;i++) q.push(a[i]);
    while（q.empty()){
         cout<<q.top;
         q.pop();
    }
    return 0;
}

E.时间复杂度

push(): O(logN)

pop(): O(logN)

top() : O(1)

优先队列是用堆实现

堆(Heap)

1.完全二叉树

父节点:i

左儿子：2i

右儿子:2i+1

若当前节点为i, 父节点：[i/2]

2.儿子键值不小于父亲键值:(小根堆)

3.堆的基本操作

A.插入 insert(int val)

B.减小第i个结点的值到val decrease_value(int i,int val)

C.删除最小键值的节点 delete_min()

D.删除第i个结点 delete(int i)

E.修改第i个结点的键值 update_value(int i,int val)

N个数的2叉树深度为log2^N

代码：

void insert(int val)
{
    int i=++size;
    while(i>1&&val<Heap[i/2])
    {
        Heap[i]=Heap[i/2];
        i/=2;
    }
    Heap[i]=val;
}

减小第i个结点的值为val 1)将Heap[i]=val 2)向上调整

删除根 1)最后一个元素移动到根节点 2)向下调整

代码

int delete_min()
{
    int val=Heap[size--],ret=Heap[1];
    int i=1,ch=2;
    while(ch<=size){
        if(ch<size&&Heap[ch+1]<Heap[i]) ch++;
        if(val<=Heap[ch]) break;
        Heap[i]=Heap[ch];
        i=ch;
        ch=ch*2;
    }
    Heap[1]=val;
    return ret;
}

优先队列不支持

B,D,E操作

最短路算法:Dijkstra

伪代：

void Dij(int s) {
    memset(dist,0x3f,sizeof(dist))
    dist[s]=0,list[0]=s;
    int ft=0,re=1;
    while(ft<re){
        int u=list[ft++];
        for(v:u的邻居){
            if(dist[v]==inf)
                list[re++];
            dist[v]=min(dist[v],dist[u]+len);
        }
    }
    //在list[ft]~list[re]中，找dist值最小的元素交换到list[ft]
}

题目:[Game fishing] poj 1042