c++ STL二叉堆(优先队列)_二叉树用优先队列c++

c++ STL二叉堆(优先队列)

1.介绍

完全二叉树：叶子节点只会出现在最后2层，且最后一层的叶子节点都靠左对齐。

二叉堆 (优先队列)：一种特殊的完全二叉树，父结点值比子结点大或者小。

最小堆（小根堆）：父结点比子结点都要小

最大堆（大根堆）：父结点比子结点都要大

二叉堆前提是他必须是一颗完全二叉树！！！！！

既然可以按顺序标号，那么我们就可以用一个数组来把这颗树存起来了

根节点下标为1，左孩子下标 父结点下标*2 ，右孩子下标 父结点下标*2+1

反过来，我们知道孩子的下标，求父结点的下标 孩子的下标 / 2

如果这是最小堆最小元素就是 数组[1]; 反之，最大堆最大的 数组[1];

2.手写堆（可以跳过直接看3）

样例堆如下图：

删除元素：(删除1)

让堆顶的结点和最后一个元素交换，再删除最后一个元素，最后对堆进行调整（下沉）；

void down( int i ) 
{
    int t, flag = 1;//flag来标记符不符合堆的特性
    while ( i * 2 <= n && flag ) {
        t = i*2;//左孩子
        if ( i * 2 + 1 <= n ) { //有右孩子
            if ( h[i*2] > h[i*2+1] ) {
                t = i*2+1;
            }
        }
        if ( h[t] > h[i] ) {
            flag = 0;
        }
        else {
            swap(t, i);//交换下标t,i的数组元素
            i = t;
        }
    }
}
void delete()
{
    swap(1, n); //交换下标为1 和 n的元素
    n--;//堆的size-1
    down(1);   //下沉
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

插入元素

插入元素：插入元素0

先让n++，h[n] = 0, 再对0进行上浮

void up( int i)//上浮下标为i的元素
{
    if ( i == 1 ) return ;//i=1就是根节点嘛
    
    int flag = 1;
    while ( i != 1 && flag ) {
        if ( h[i] < h[i/2] ) {
            swap(i, i/2);
        }
        else {
            flag = 0;
        }
        i /= 2;  //i要时刻跟踪着我们插入的结点
    }
}
void insert( int x ) 
{
    n++;
    h[n] = x;//h数组表示存结点的数组
    up(n);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

创建堆:

先用数组存起来所有元素，然后从倒数第二层依次下沉：

void create()
{
    //n为堆中最后一个结点的位置，
	for ( int i = n/2; i >= 1; --i ) {
        down(i);
    }    
}
1
2
3
4
5
6
7

完整代码

#include <iostream>
//堆的基本常规操作

using namespace std;
int n, h[105];

//交换下标元素
void swap( int i, int j);
//下沉
void down( int i );
void delete1();

//上浮
void up( int i );
void insert( int x );

//创建堆
void create();

//主函数
int main()
{
	cin >> n;
	for ( int i = 1; i <= n; ++i ) {
		cin >> h[i];
	}
	create();
	
	for ( int i = 1; i <= n; ++i ) {
		cout << h[i] << ' ';
	}
	return 0;
}

void swap( int i, int j)
{
	int temp = h[i];
	h[i] = h[j];
	h[j] = temp;
}

void delete1()
{
	swap(1, n);
	n--;
	down(1);
}

void down( int i )
{
	int t, flag = 1;
	while ( i * 2 <= n && flag ) {
		//表示左孩子的下标
		t = i * 2;
		//在判断有没有右孩子
		if ( i * 2 + 1 <= n ) {
			if ( h[i*2+1] < h[i*2] ) {
				t = i*2+1;
			}
		}
		if ( h[t] > h[i] ) {
			flag = 0;
		}
		else {
			swap(i, t);
			i = t;
		}
	}
}
void insert( int x )
{
	n++;
	h[n] = x;
	up(n);
}
void up( int i )
{
	//如果i等于1，直接跳出循环
	if ( i == 1 ) return ;
	
	int flag = 1;
	while ( i != 1 && flag ) {
		if ( h[i] < h[i/2] ) {
			swap(i, i/2);
			i /= 2;
		}
		else {
			flag = 0;
		}
	}
}

void create()
{
	for ( int i = n/2; i >= 1; --i ) {
		down(i);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

3.STL优先队列

priority_queue<int, vector< int>, greater< int> > q; //最小堆

priority_queue<int, vector< int>, less< int> > c; //最大堆

基本操作：

定义：priority_queue<类型，容器方式，比较方法> q;

例子：priority_queue<int, vector< int>, greater< int> > q;

容器方式STL里面默认用的是vector；

类型可以自定义；

c++默认是一个最大堆 priority_queue<int, vector< int> > q 等同于 priority_queue< int, vector< int>, less< int> > q

#include <iostream>
#include <queue>
using namespace std;

//定义优先队列a,b,c，事实上三者一毛一样的
priority_queue<int> a;
priority_queue<int, vector<int> > b;//默认vector
priority_queue<int, vector<int>, less<int> > c; //默认less

int main()
{
	for ( int i = 0; i < 5; ++i ) {
		a.push(i);//加入元素
		b.push(i);
		c.push(i);
	}
	
	cout << "A：";
	while ( !a.empty() ) {
		cout << a.top() << ' ';
		a.pop();
	}
	cout << endl;
	
	cout << "B：";
	while ( !b.empty() ) {
		cout << b.top() << ' ';
		b.pop();
	}
	cout << endl;
	
	cout << "C：";
	while ( !c.empty() ) {
		cout << c.top() << ' ';
		c.pop();
	}
	cout << endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

来一个类型为pair的，默认是先比较第一个，在比较第二个

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() 
{
    priority_queue<pair<int, int> > a;
    pair<int, int> b(1, 2);
    pair<int, int> c(1, 3);
    pair<int, int> d(2, 5);
    a.push(d);
    a.push(c);
    a.push(b);
    while (!a.empty()) 
    {
        cout << a.top().first << ' ' << a.top().second << '\n';
        a.pop();
    }
}

//如果pair里面的类型是我们自定义的，c++没有给我们准备比较规则，那么我们就要自己写比较规则了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

自定义比较方法

看看优先队列定义：

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

参数3需要指定一个实现了 operator< 操作符的类（叫做仿函数或者函数对象，实际上就是类，只是调用时写起来像函数一样）
1
2
3
4
5
6
7

假如我们不想用c++的greater,我们要自己写，自己来做最小堆

#include <iostream>
#include <queue>
using namespace std;

struct cmp{
	//左边是队尾，右边是队首
	//即队首b 小于 其他元素
	//最小堆
	bool operator () ( int a, int b ) {
		return b < a;
	}
};

int main()
{
	priority_queue<int, vector<int>, cmp> c;
	
	for ( int i = 0; i < 5; ++i ) {
		c.push(i);
	}
	
	cout << "C：";
	while ( !c.empty() ) {
		cout << c.top() << ' ';
		c.pop();
	}
	cout << endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

自定义类型

less

#include <iostream>
#include <queue>
#include <string>
using namespace std;

//学生，假设年龄小的优先级高
//年龄相同，按姓名字典序
typedef struct Student{
	int age;
	string name;
}Stu;
//b是队首元素
bool operator < (Stu a, Stu b)
{
	if (a.age == b.age) return b.name > a.name;//按字典序来看优先级
	return b.age < a.age;//年龄小的优先级高
}

int main()
{
	priority_queue<Stu, vector<Stu>, less<Stu> > c;  //================>这里是less,就重写小于
	
	for ( int i = 0; i < 5; ++i ) {
		Stu a = {i, "s"};
		c.push(a);
	}
	
	cout << "C：\n";
	while ( !c.empty() ) {
		cout << c.top().name << ' ' << c.top().age << endl;
		c.pop();
	}
	cout << endl << endl;
	
	Stu a = {10, "田小锋"}; c.push(a);
	Stu b = {10, "田小锋01"}; c.push(b);
	cout << "C：\n";
	while ( !c.empty() ) {
		cout << c.top().name << ' ' << c.top().age << endl;
		c.pop();
	}
	cout << endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

greater

#include <iostream>
#include <queue>
#include <string>
using namespace std;

//学生，假设年龄小的优先级高
//年龄相同，按姓名字典序
typedef struct Student{
	int age;
	string name;
}Stu;
//b是队首元素
bool operator > (Stu a, Stu b)
{
	if (a.age == b.age) return b.name > a.name;//按字典序来看优先级
	return b.age < a.age;//年龄小的优先级高
}

int main()
{
	priority_queue<Stu, vector<Stu>, greater<Stu> > c; //===============>这里是greater,就重写>
	
	for ( int i = 0; i < 5; ++i ) {
		Stu a = {i, "s"};
		c.push(a);
	}
	
	cout << "C：\n";
	while ( !c.empty() ) {
		cout << c.top().name << ' ' << c.top().age << endl;
		c.pop();
	}
	cout << endl << endl;
	
	Stu a = {10, "田小锋"}; c.push(a);
	Stu b = {10, "田小锋01"}; c.push(b);
	cout << "C：\n";
	while ( !c.empty() ) {
		cout << c.top().name << ' ' << c.top().age << endl;
		c.pop();
	}
	cout << endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

下面是直接在结构体里面重写比较方法

#include <iostream>
#include <queue>
#include <string>
using namespace std;

//学生，假设年龄小的优先级高
//年龄相同，按姓名字典序
typedef struct Student{
	int age;
	string name;
	
	//b是队首元素
	bool operator > ( const Student b) const  //这个const不能少哦，
	{
		if (age == b.age) return b.name > name;//按字典序来看优先级
		return b.age < age;//年龄小的优先级高
	}
}Stu;


int main()
{
	priority_queue<Stu, vector<Stu>, greater<Stu> > c;
	
	for ( int i = 0; i < 5; ++i ) {
		Stu a = {i, "s"};
		c.push(a);
	}
	
	cout << "C：\n";
	while ( !c.empty() ) {
		cout << c.top().name << ' ' << c.top().age << endl;
		c.pop();
	}
	cout << endl << endl;
	
	Stu a = {10, "田小锋"}; c.push(a);
	Stu b = {10, "田小锋01"}; c.push(b);
	cout << "C：\n";
	while ( !c.empty() ) {
		cout << c.top().name << ' ' << c.top().age << endl;
		c.pop();
	}
	cout << endl;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47