Priority Queue & Monotone Queue

Priority Queue

STL

• Use type priority_queue in STL header <queue>

• It will auto make the number in queue keep in a seriation, auto Z -> A

• If you want A -> Z, add: priorirty_queue < int , vector < int > , greater < int > > que ;

Array

• Use heap

• If A -> Z, small-root-heap

• If Z -> A, big-root-heap

• It's a little bit difficult, so in examination, we also use STL

Monotone Queue

STL

• Use type deque in STL header <deque>

• It can support you move number in head and tail

• queue head: que.begin () ; queue tail: que.end ()

• push front: que.push_front () ; push back: que.push_back ()

• Examinations

  • Luogu P1886 Windows move / [TESTFOR] monotone queue: Use monotone queue maintain the sequence, sort by A -> Z.