优先队列(priority queue)一，优先队列二，STL优先队列三，二叉堆实现优先队列四，二项堆实现优先队列五，线段树实现优先队列六，OJ实战

98 阅读 0 评论 65 点赞

我是靠谱客的博主如意枕头，这篇文章主要介绍优先队列(priority queue)一，优先队列二，STL优先队列三，二叉堆实现优先队列四，二项堆实现优先队列五，线段树实现优先队列六，OJ实战，现在分享给大家，希望可以做个参考。

一，优先队列

二，STL优先队列

三，二叉堆实现优先队列

四，二项堆实现优先队列

五，线段树实现优先队列

六，OJ实战

力扣 295. 数据流的中位数

一，优先队列

优先队列可以插入元素、查询最大值、删除最大值。

优先队列其实就是最大堆或最小堆，最大堆可以用来实现最大优先队列，最小堆可以用来实现最小优先队列。

用各种堆都可以实现优先队列。

二，STL优先队列

优先队列如果要自定义排序函数，只能用仿函数，不能用普通函数的指针。

示例：

复制代码

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
#include<iostream>
#include<queue>
#include<functional>
using namespace std;

class cmp
{
public:
	bool operator()(int a, int b)
	{
		return a < b;
	}
};

bool cmp2(int a, int b)
{
	return a < b;
}

template <typename A>
void display()
{
	A q;
	q.push(1);
	q.push(3);
	q.push(4);
	q.push(2);
	while (!q.empty())
	{
		cout << q.top();
		q.pop();
	}
	cout << endl;
}

int main()
{
	display < priority_queue<int, vector<int>> >();  //默认大顶堆	
	display < priority_queue <int, vector<int>, greater<int>> >();//小顶堆
	display < priority_queue <int, vector<int>, less<int>> >();//大顶堆
	display < priority_queue<int, vector<int>, cmp>>();//大顶堆
	//display < priority_queue<int, vector<int>, cmp2>>();  错误
	return 0;
}

输出：

4321
1234
4321
4321

附上priority_queue的实现代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
		// TEMPLATE CLASS priority_queue
template<class _Ty,
	class _Container = vector<_Ty>,
	class _Pr = less<typename _Container::value_type> >
	class priority_queue
	{	// priority queue implemented with a _Container
public:
	......
	一堆函数
	......
protected:
	_Container c;	// the underlying container
	_Pr comp;	// the comparator functor
	};

可以看出模板参数_Pr的默认值是less，也就是说默认排序函数是less函数。

priority_queue中包含一个排序的序列，堆顶是这个序列的最后一个元素，所以从小到大排序是大顶堆，从大到小排序是小顶堆。

三，二叉堆实现优先队列

二叉堆

最大优先队列：

复制代码

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

template<typename T>
bool cmp(T a, T b)
{
    return a < b; //最大堆
}

template<typename T>
void exchange(T* a, T* b)
{
    T tmp = *a;
    *a = *b;
    *b = tmp;
}

int LeftChild(int id)
{
    return id * 2;
}
int RightChild(int id)
{
    return id * 2 + 1;
}
int Parent(int id)
{
    return id/2;
}

template<typename T>
void AdjustHeap(T* arr, int rootId, int size)
{
    int largest = rootId, left = LeftChild(rootId), right = RightChild(rootId);
    if (left < size && cmp(arr[largest], arr[left]))largest = left;
    if (right < size && cmp(arr[largest], arr[right]))largest = right;
    if (largest == rootId)return;
    exchange(arr + rootId, arr + largest);
    AdjustHeap(arr, largest, size);
}

template<typename T>
void HeapIncrese(T* arr, int size, int id, T newValue)
{
    arr[id] = newValue;
    while (id > 0 && cmp(arr[Parent(id)], arr[id])) {
        exchange(arr + id, arr + Parent(id));
        id = Parent(id);
    }
}

template<typename T>
void HeapInsert(T* arr, int &size,T value)
{
    HeapIncrese(arr,size+1,size,value);
    size++;
}

int g_size;
void Init()
{
    g_size = 0;
}
template<typename T>
T Top(T* arr)
{
    return arr[0];
}
template<typename T>
void Push(T* arr, T value)
{
    HeapInsert(arr,g_size,value);
}
template<typename T>
void Pop(T* arr)
{
    g_size--;
    exchange(arr, arr+g_size);
    AdjustHeap(arr, 0, g_size);
}

int main()
{
    int q[10];
    Init();
    Push(q,4);
    Push(q,2);
    Push(q,6);
    Push(q,3);
    Push(q,4);
    Push(q,5);
    cout<<Top(q)<<" ";
    Pop(q);
    cout<<Top(q)<<" ";
    Pop(q);
    cout<<Top(q)<<" ";
    Pop(q);
    cout<<Top(q)<<" ";
    Pop(q);
    cout<<Top(q)<<" ";
    Pop(q);
    cout<<Top(q)<<" ";
    Pop(q);
    cout<<endl<<g_size;
    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
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
100
101
102
103
104
105
106
107
#include<iostream>
#include <vector>
using namespace std;

template<typename T>
bool cmp(T a, T b)
{
    return a < b; //最大堆
}

template<typename T>
void exchange(T* a, T* b)
{
    T tmp = *a;
    *a = *b;
    *b = tmp;
}

int LeftChild(int id)
{
    return id * 2;
}
int RightChild(int id)
{
    return id * 2 + 1;
}
int Parent(int id)
{
    return id/2;
}

template<typename T>
void AdjustHeap(T* arr, int rootId, int size)
{
    int largest = rootId, left = LeftChild(rootId), right = RightChild(rootId);
    if (left < size && cmp(arr[largest], arr[left]))largest = left;
    if (right < size && cmp(arr[largest], arr[right]))largest = right;
    if (largest == rootId)return;
    exchange(arr + rootId, arr + largest);
    AdjustHeap(arr, largest, size);
}

template<typename T>
void HeapIncrese(T* arr, int size, int id, T newValue)
{
    arr[id] = newValue;
    while (id > 0 && cmp(arr[Parent(id)], arr[id])) {
        exchange(arr + id, arr + Parent(id));
        id = Parent(id);
    }
}

template<typename T>
void HeapInsert(T* arr, int &size,T value)
{
    HeapIncrese(arr,size+1,size,value);
    size++;
}

int g_size;
void Init()
{
    g_size = 0;
}
template<typename T>
T Top(T* arr)
{
    return arr[0];
}
template<typename T>
void Push(T* arr, T value)
{
    HeapInsert(arr,g_size,value);
}
template<typename T>
void Pop(T* arr)
{
    g_size--;
    exchange(arr, arr+g_size);
    AdjustHeap(arr, 0, g_size);
}

int main()
{
    int q[10];
    Init();
    Push(q,4);
    Push(q,2);
    Push(q,6);
    Push(q,3);
    Push(q,4);
    Push(q,5);
    cout<<Top(q)<<" ";
    Pop(q);
    cout<<Top(q)<<" ";
    Pop(q);
    cout<<Top(q)<<" ";
    Pop(q);
    cout<<Top(q)<<" ";
    Pop(q);
    cout<<Top(q)<<" ";
    Pop(q);
    cout<<Top(q)<<" ";
    Pop(q);
    cout<<endl<<g_size;
    return 0;
}

运行结果：

6 5 4 4 3 2
0

四，二项堆实现优先队列

二项堆里面已经实现了push、pop、top等操作，所以它就是一种优先队列。

五，线段树实现优先队列

代码：

复制代码

struct anode
{
    int t;
    int d;
};
int n;
int num[10001],maxx[40001];
struct anode node[10001];
 
void build(int key, int low, int high)//id
{
	if (low == high)
	{
		maxx[key] = low;
		return;
	}
	int mid = (low + high) / 2;
	build(key * 2, low, mid);
	build(key * 2 + 1, mid + 1, high);
	maxx[key] = (num[maxx[key * 2]] > num[maxx[key * 2 + 1]]) ? maxx[key * 2] : maxx[key * 2 + 1];
}
 
void update(int key, int low, int high, int uplace)//id
{
	if (low == high)
	{
		maxx[key] = low;
		return;
	}
	int mid = (low + high) / 2;
	if (uplace <= mid)update(key * 2, low, mid, uplace);
	else update(key * 2 + 1, mid + 1, high, uplace);
	maxx[key] = (num[maxx[key * 2]] > num[maxx[key * 2 + 1]]) ? maxx[key * 2] : maxx[key * 2 + 1];
}
 
int query(int key, int low, int high, int x, int y)//id
{
	if (low == x && high == y)return maxx[key];
	int mid = (low + high) / 2;
	if (mid < x)return query(key * 2 + 1, mid + 1, high, x, y);
	if (mid >= y)return query(key * 2, low, mid, x, y);
	int a = query(key * 2, low, mid, x, mid);
	int b = query(key * 2 + 1, mid + 1, high, mid + 1, y);
	return  (num[a]>num[b]) ? a : b;
}
 
void push(int loc)
{
    num[loc]=node[loc].t; ///根据实际情况修改
    update(1,1,n,loc);
}
void pop(int loc)
{
    num[loc]=0; ///根据实际情况修改
    update(1,1,n,loc);
}
int top()//id
{
    return query(1,1,n,1,n);
}

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
struct anode
{
    int t;
    int d;
};
int n;
int num[10001],maxx[40001];
struct anode node[10001];
 
void build(int key, int low, int high)//id
{
	if (low == high)
	{
		maxx[key] = low;
		return;
	}
	int mid = (low + high) / 2;
	build(key * 2, low, mid);
	build(key * 2 + 1, mid + 1, high);
	maxx[key] = (num[maxx[key * 2]] > num[maxx[key * 2 + 1]]) ? maxx[key * 2] : maxx[key * 2 + 1];
}
 
void update(int key, int low, int high, int uplace)//id
{
	if (low == high)
	{
		maxx[key] = low;
		return;
	}
	int mid = (low + high) / 2;
	if (uplace <= mid)update(key * 2, low, mid, uplace);
	else update(key * 2 + 1, mid + 1, high, uplace);
	maxx[key] = (num[maxx[key * 2]] > num[maxx[key * 2 + 1]]) ? maxx[key * 2] : maxx[key * 2 + 1];
}
 
int query(int key, int low, int high, int x, int y)//id
{
	if (low == x && high == y)return maxx[key];
	int mid = (low + high) / 2;
	if (mid < x)return query(key * 2 + 1, mid + 1, high, x, y);
	if (mid >= y)return query(key * 2, low, mid, x, y);
	int a = query(key * 2, low, mid, x, mid);
	int b = query(key * 2 + 1, mid + 1, high, mid + 1, y);
	return  (num[a]>num[b]) ? a : b;
}
 
void push(int loc)
{
    num[loc]=node[loc].t; ///根据实际情况修改
    update(1,1,n,loc);
}
void pop(int loc)
{
    num[loc]=0; ///根据实际情况修改
    update(1,1,n,loc);
}
int top()//id
{
    return query(1,1,n,1,n);
}

应用：

力扣 630. 课程表 III

六，OJ实战

力扣 295. 数据流的中位数

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2

思路：

维护1个最大堆和1个最小堆，并动态维持他们的尺寸相同。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MedianFinder {
public:
    MedianFinder() {
    }
 
    void addNum(int num) {
        if (qmax.empty()||num<=qmax.top())qmax.push(num);
        else qmin.push(num);
    }
 
    double findMedian() {
        while (qmin.size() > qmax.size()) qmax.push(qmin.top()),qmin.pop();
        while (qmax.size() > qmin.size()+1)qmin.push(qmax.top()),qmax.pop();
        if (qmax.size() > qmin.size())return qmax.top();
        return (qmax.top() + qmin.top()) / 2.0;
    }
private:
    priority_queue<int, vector<int>> qmax;
    priority_queue <int, vector<int>, greater<int>> qmin;
};

或者用自己实现的堆：

复制代码

template<typename T>
class MyHeap {
public:
	T arr[100000];
	MyHeap(int type)//0最小堆1最大堆
	{
		this->type = type;
	}
	T Top()
	{
		return arr[0];
	}
	void Push(T value)
	{
		HeapInsert(arr, value);
	}
	void Pop()
	{
		size--;
		exchange(arr, arr + size);
		AdjustHeap(arr, 0);
	}
	bool empty()
	{
		return size == 0;
	}
	int Size()
	{
		return size;
	}
private:
	void AdjustHeap(T* arr, int rootId)
	{
		int largest = rootId, left = LeftChild(rootId), right = RightChild(rootId);
		if (left < size && cmp(arr[largest], arr[left]))largest = left;
		if (right < size && cmp(arr[largest], arr[right]))largest = right;
		if (largest == rootId)return;
		exchange(arr + rootId, arr + largest);
		AdjustHeap(arr, largest);
	}
	void HeapIncrese(T* arr, int id, T newValue)
	{
		arr[id] = newValue;
		while (id > 0 && cmp(arr[Parent(id)], arr[id])) {
			exchange(arr + id, arr + Parent(id));
			id = Parent(id);
		}
	}
	void HeapDecrese(T* arr, int size, int id, T newValue)
	{
		arr[id] = newValue;
		AdjustHeap(arr, id, size);
	}
	void HeapChange(T* arr, int id, T newValue)
	{
		if (cmp(arr[id], newValue))HeapIncrese(arr, id, newValue);
		else HeapDecrese(arr, id, newValue);
	}
	void HeapInsert(T* arr, T value)
	{
		HeapIncrese(arr, size++, value);
	}
	bool cmp(T a, T b)
	{
		return type ? (a < b) : (a > b);
	}
	void exchange(T* a, T* b)
	{
		T tmp = *a;
		*a = *b;
		*b = tmp;
	}

int LeftChild(int id)
	{
		return id * 2 + 1;
	}
	int RightChild(int id)
	{
		return id * 2 + 2;
	}
	int Parent(int id)
	{
		return (id - 1) / 2;
	}
	int type;
	int size = 0;
};

class MedianFinder {
public:
	MedianFinder() {
	}

void addNum(int num) {
		if (qmax.empty() || num <= qmax.Top())qmax.Push(num);
		else qmin.Push(num);
	}

double findMedian() {
		while (qmin.Size() > qmax.Size()) qmax.Push(qmin.Top()), qmin.Pop();
		while (qmax.Size() > qmin.Size() + 1)qmin.Push(qmax.Top()), qmax.Pop();
		if (qmax.Size() > qmin.Size())return qmax.Top();
		return (qmax.Top() + qmin.Top()) / 2.0;
	}
private:
	MyHeap<int> qmax{ 1 };
	MyHeap<int> qmin{ 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
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
100
101
102
103
104
105
106
107
108
109
110
111
template<typename T>
class MyHeap {
public:
	T arr[100000];
	MyHeap(int type)//0最小堆1最大堆
	{
		this->type = type;
	}
	T Top()
	{
		return arr[0];
	}
	void Push(T value)
	{
		HeapInsert(arr, value);
	}
	void Pop()
	{
		size--;
		exchange(arr, arr + size);
		AdjustHeap(arr, 0);
	}
	bool empty()
	{
		return size == 0;
	}
	int Size()
	{
		return size;
	}
private:
	void AdjustHeap(T* arr, int rootId)
	{
		int largest = rootId, left = LeftChild(rootId), right = RightChild(rootId);
		if (left < size && cmp(arr[largest], arr[left]))largest = left;
		if (right < size && cmp(arr[largest], arr[right]))largest = right;
		if (largest == rootId)return;
		exchange(arr + rootId, arr + largest);
		AdjustHeap(arr, largest);
	}
	void HeapIncrese(T* arr, int id, T newValue)
	{
		arr[id] = newValue;
		while (id > 0 && cmp(arr[Parent(id)], arr[id])) {
			exchange(arr + id, arr + Parent(id));
			id = Parent(id);
		}
	}
	void HeapDecrese(T* arr, int size, int id, T newValue)
	{
		arr[id] = newValue;
		AdjustHeap(arr, id, size);
	}
	void HeapChange(T* arr, int id, T newValue)
	{
		if (cmp(arr[id], newValue))HeapIncrese(arr, id, newValue);
		else HeapDecrese(arr, id, newValue);
	}
	void HeapInsert(T* arr, T value)
	{
		HeapIncrese(arr, size++, value);
	}
	bool cmp(T a, T b)
	{
		return type ? (a < b) : (a > b);
	}
	void exchange(T* a, T* b)
	{
		T tmp = *a;
		*a = *b;
		*b = tmp;
	}

	int LeftChild(int id)
	{
		return id * 2 + 1;
	}
	int RightChild(int id)
	{
		return id * 2 + 2;
	}
	int Parent(int id)
	{
		return (id - 1) / 2;
	}
	int type;
	int size = 0;
};



class MedianFinder {
public:
	MedianFinder() {
	}

	void addNum(int num) {
		if (qmax.empty() || num <= qmax.Top())qmax.Push(num);
		else qmin.Push(num);
	}

	double findMedian() {
		while (qmin.Size() > qmax.Size()) qmax.Push(qmin.Top()), qmin.Pop();
		while (qmax.Size() > qmin.Size() + 1)qmin.Push(qmax.Top()), qmax.Pop();
		if (qmax.Size() > qmin.Size())return qmax.Top();
		return (qmax.Top() + qmin.Top()) / 2.0;
	}
private:
	MyHeap<int> qmax{ 1 };
	MyHeap<int> qmin{ 0 };
};

其他应用：

A算法

CSU 1588 合并果子

CCF-CSP-2017-3-4 地铁修建

力扣 347. 前 K 个高频元素

力扣 373. 查找和最小的K对数字

力扣 378. 有序矩阵中第K小的元素

力扣 1090. 受标签影响的最大值

力扣 1631. 最小体力消耗路径

力扣 451. 根据字符出现频率排序

2020编码大赛（2）初赛

最后

以上就是如意枕头最近收集整理的关于优先队列(priority queue)一，优先队列二，STL优先队列三，二叉堆实现优先队列四，二项堆实现优先队列五，线段树实现优先队列六，OJ实战的全部内容，更多相关优先队列(priority内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：数据结构
浏览次数：98 次浏览
发布日期：2024-05-23 11:55:01
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_7_o_26_f2_12__23__6_0.html

优先队列(priority queue)一，优先队列二，STL优先队列三，二叉堆实现优先队列四，二项堆实现优先队列五，线段树实现优先队列六，OJ实战

一，优先队列

二，STL优先队列

三，二叉堆实现优先队列

四，二项堆实现优先队列

五，线段树实现优先队列

六，OJ实战

力扣 295. 数据流的中位数

最后

评论列表共有 0 条评论

发表评论取消回复

优先队列(priority queue)一，优先队列二，STL优先队列三，二叉堆实现优先队列四，二项堆实现优先队列五，线段树实现优先队列六，OJ实战

一，优先队列

二，STL优先队列

三，二叉堆实现优先队列

四，二项堆实现优先队列

五，线段树实现优先队列

六，OJ实战

力扣 295. 数据流的中位数

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复