QhelDIV

@____@

priority_queue的简单用法

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

priority_queue:优先队列

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

有3个类函数:

void push(元素类型   变量)

void pop()

int top()

int size()

bool empty()

分别是:

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

定义:

  1. priority_queue <数据类型容器类型元素比较方式>
  2. priority_queue <数据类型容器类型>
  3. 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

 

 

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

Amazingly delightful utilization of words and Keenly built by the author

Avatar_small
파티 도메인 说:
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.

Avatar_small
마이크로게이밍이용방법 说:
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.

Avatar_small
먹튀스텟주소 说:
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.

Avatar_small
카지노롤링총판 说:
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

Avatar_small
굿모닝가입코드 说:
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.

Avatar_small
토팡주소 说:
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.

Avatar_small
메이저사이트추천 说:
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.

Avatar_small
คาสิโนออนไลน์ 说:
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.

Avatar_small
사설파워볼사이트 说:
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.

Avatar_small
먹튀검증업체 说:
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

Avatar_small
토토마트 说:
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!

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

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

Avatar_small
토토사이트추천 说:
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.

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

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

Avatar_small
스포츠양방배팅 说:
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.

Avatar_small
먹튀신고 说:
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.

Avatar_small
엔트리파워볼 说:
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.

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

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.

Avatar_small
먹튀검증 说:
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,

Avatar_small
바카라 说:
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.

Avatar_small
카디즈 说:
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.

Avatar_small
먹튀검증사이트 说:
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!

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

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,

Avatar_small
먹튀검증 说:
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..

Avatar_small
메이저놀이터추천 说:
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

Avatar_small
토토사이트모음 说:
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.

Avatar_small
메이저공원추천 说:
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

Avatar_small
바카라사이트추천 说:
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,

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

https://touch-of-classic.com

Avatar_small
안전공원코드 说:
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.

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

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.

Avatar_small
메이저놀이터 说:
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

Avatar_small
슈어맨 먹튀검증 说:
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.

Avatar_small
안전공원가입코드 说:
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.

Avatar_small
토토사이트 说:
2024年1月25日 18:44

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.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter