priority_queue的简单用法

Qheldiv posted @ 2013年1月11日 12:14 in C++ with tags dijkstra c++ 优先队列 , 4168 阅读

priority_queue：优先队列

顾名思义，这个东西可以用于存放单调的数据，后面将会看到用于优化Dijkstra

有3个类函数：

void push(元素类型变量)

void pop()

int top()

int size()

bool empty()

分别是：

加入类型是XXX的变量XXX
弹出队列首元素
取优先队列的队首元素的值
返回队列元素数量
查看队列是否为空

定义：

priority_queue <数据类型，容器类型，元素比较方式>
priority_queue <数据类型，容器类型>
priority_queue <数据类型>

数据类型：int,double.....

容器类型：vector（默认），deque，但不能是list

元素比较方式：less（默认，不上升序），greater（不下降序）

比如要定义一个元素值为整数，容器为vector<int>的不下降序的优先队列PQ：

priority_queue <int,vector<int> ,greater<int> >PQ

如果是第3种定义方式，容器默认为vector，比较方式默认是less（第二种的默认比较方式也是less）

实用的例子：

堆优化的Dijkstra算法，写出堆不难，但麻烦，如果想更快的写出高效的Dijkstra，用priority_queue就很不错：

#include <queue>
priority_queue <pair<int ,int>,vector<pair<int ,int> >,greater<pair<int,int> > > PQ;

void Dijkstra()
{
	while(!PQ.empty())
		PQ.pop();
	MC[1]=0;
	PQ.push(pair<int,int>(MC[1],1));
	while(!PQ.empty())
	{
	int Index=PQ.top().second;
		PQ.pop();
		if(!flag[Index])
		{
			flag[Index]=true;
			for(Node *p=last[Index];p;p=p->Prev)
				if(!flag[p->Name] && MC[p->Name]>MC[Index]+p->Dis)
				{
					MC[p->Name]=MC[Index]+p->Dis;
					PQ.push(pair<int,int>(MC[p->Name],p->Name));
				}
		}
	}
}

MC是最小花费

flag标志数组

last 邻接表

更详细的信息请参阅：

http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/

参考

cplusplus.com

http://blog.chinaunix.net/space.php?uid=533684&do=blog&cuid=2615612

[回复]

seo service london 说:
2024年1月16日 14:43

Amazingly delightful utilization of words and Keenly built by the author

[回复]

파티 도메인 说:
2024年1月25日 14:12

This site is excellent and so is how the subject matter was explained. I also like some of the comments too. Looking forward to your next post.

[回复]

마이크로게이밍이용방법 说:
2024年1月25日 14:45

Great to be here in your article or post, whatever, I figure I ought to likewise buckle down for my own site like I see some great and refreshed working in your site.

[回复]

먹튀스텟주소 说:
2024年1月25日 14:55

I definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work.

[回复]

카지노롤링총판 说:
2024年1月25日 15:06

Decent data, profitable and phenomenal outline, as offer well done with smart thoughts and ideas, bunches of extraordinary data and motivation, both of which I require, on account of offer such an accommodating data her

[回复]

굿모닝가입코드 说:
2024年1月25日 15:06

Thanks for sharing the post.. parents are worlds best person in each lives of individual..they need or must succeed to sustain needs of the family.

[回复]

토팡주소 说:
2024年1月25日 15:15

Thanks for sharing the post.. parents are worlds best person in each lives of individual..they need or must succeed to sustain needs of the family.

[回复]

메이저사이트추천 说:
2024年1月25日 15:17

Mendy has been playing for Real Madrid since 2019. This season, the defender has played 16 matches for the cream in all competitions, in which he scored one goal. The player's contract with the Madrid club is valid until the end of June 2025. The estimated cost of a football player, according to the Transfermarkt Internet portal, is € 20 million.

[回复]

คาสิโนออนไลน์ 说:
2024年1月25日 15:20

Acknowledges for paper such a beneficial composition, I stumbled beside your blog besides decipher a limited announce. I want your technique of inscription.

[回复]

사설파워볼사이트 说:
2024年1月25日 15:27

Acknowledges for paper such a beneficial composition, I stumbled beside your blog besides decipher a limited announce. I want your technique of inscription.

[回复]

먹튀검증업체 说:
2024年1月25日 15:28

Wonderful article man! The way you have explained everything step by step is phenomenal. I really appreciate your work. Keep it up!!! In case, if you are looking

[回复]

토토마트 说:
2024年1月25日 15:36

I just wanted to drop you a quick note to say how much I appreciate your blog. Your writing style is like catching up with an old friend—comfortable, engaging, and always filled with valuable stories. Keep it up!

[回复]

온오프카지노주소 说:
2024年1月25日 15:41

Thanks for sharing nice information with us. i like your post and all you share with us is uptodate

[回复]

토토사이트추천 说:
2024年1月25日 15:54

Normally, you can only use Payday for around 10,000 yen for the first time, but this plan is specialized for Apple products and has a significantly wider usage limit.

[回复]

먹튀사이트 说:
2024年1月25日 15:58

Spot up for this write-up, I honestly feel this fabulous website wants considerably more considerati

[回复]

스포츠양방배팅 说:
2024年1月25日 16:11

I definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work.

[回复]

먹튀신고 说:
2024年1月25日 16:14

Hey There. I found your blog using msn. This is a very well written article. I’ll be sure to bookmark it and come back to read more of your useful info. Thanks for the post. I’ll definitely return.

[回复]

엔트리파워볼 说:
2024年1月25日 16:19

Hi, I find reading this article a joy. It is extremely helpful and interesting and very much looking forward to reading more of your work.

[回复]

배트맨토토 说:
2024年1月25日 16:22

[回复]

먹튀검증 说:
2024年1月25日 16:29

Thank you again for all the knowledge you distribute,Good post. I was very interested in the article, it's quite inspiring I should admit. I like visiting you site since I always come across interesting articles like this one.Great Job, I greatly appreciate that.Do Keep sharing! Regards,

[回复]

바카라 说:
2024年1月25日 16:34

Discover the best selection and lowest prices on prescription and over-the-counter medications. Everything you'd expect from Canada's largest online pharmacy! CanadaCloudPharmacy.com is the most trusted name in high-quality, affordable medications, having been a first-class, certified online pharmacy serving many satisfied customers since 2001. In addition to discount prescription drugs, our Canada Pharmacy online provides a wide variety of discounted over-the-counter (OTC) medications, such as pain relievers, allergy medications, and even pet medications.

[回复]

카디즈 说:
2024年1月25日 16:40

Hi, I find reading this article a joy. It is extremely helpful and interesting and very much looking forward to reading more of your work.

[回复]

먹튀검증사이트 说:
2024年1月25日 16:46

Just admiring your work and wondering how you managed this blog so well. It’s so remarkable that I can't afford to not go through this valuable information whenever I surf the internet!

[回复]

온라인카지노종류 说:
2024年1月25日 17:02

[回复]

먹튀검증 说:
2024年1月25日 17:07

I'm impressed, I must say. Very rarely do I come across a blog thats both informative and entertaining, and let me tell you, you ve hit the nail on the head. Your blog is important..

[回复]

메이저놀이터추천 说:
2024年1月25日 17:37

Wonderful article man! The way you have explained everything step by step is phenomenal. I really appreciate your work. Keep it up!!! In case, if you are looking

[回复]

토토사이트모음 说:
2024年1月25日 17:40

Nice information, valuable and excellent design, as share good stuff with good ideas and concepts, lots of great information and inspiration, both of which I need, thanks to offer such a helpful information here.

[回复]

메이저공원추천 说:
2024年1月25日 17:45

Wonderful article man! The way you have explained everything step by step is phenomenal. I really appreciate your work. Keep it up!!! In case, if you are looking

[回复]

바카라사이트추천 说:
2024年1月25日 17:56

Your blog provided us with valuable information to work with. Each & every tips of your post are awesome. Thanks a lot for sharing. Keep blogging,

[回复]

메이저사이트 说:
2024年1月25日 18:05

https://touch-of-classic.com

[回复]

안전공원코드 说:
2024年1月25日 18:13

Partaking in a particularly overpowering undertaking utilizes a great deal of our assets. Appreciation for sharing. I regard your site's facilities and strong data. Look at our site, and we will find you.

[回复]

보증업체 说:
2024年1月25日 18:21

[回复]

메이저놀이터 说:
2024年1月25日 18:25

I feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it

[回复]

슈어맨 먹튀검증 说:
2024年1月25日 18:28

Hi, I find reading this article a joy. It is extremely helpful and interesting and very much looking forward to reading more of your work.

[回复]

안전공원가입코드 说:
2024年1月25日 18:34

Hi, I find reading this article a joy. It is extremely helpful and interesting and very much looking forward to reading more of your work.

[回复]