[stl] priority queue priority_ queue

---

One 、priority_queue Document introduction

1. A priority queue is a container adapter , According to the strict weak sorting criteria , Its first element is always the largest of the elements it contains .
2. This context is similar to heap , You can insert elements into the heap at any time , And only the largest heap element can be retrieved ( The top element in the priority queue ).
3. The priority queue is implemented as a container adapter , The container adapter encapsulates a specific container class as its underlying container class ,queue Provide a specific set of member functions to access its elements . Element from a specific container “ The tail ” eject , It is called the top of the priority queue .
4. The underlying container can be any standard container class template , It can also be other specially designed container classes . Containers should be accessible through random access iterators , And supports the following operations ：
   empty()： Check whether the container is empty
   size()： Returns the number of valid elements in the container
   front()： Returns a reference to the first element in the container
   push_back()： Insert the element at the end of the container
   pop_back()： Delete the container tail element
5. Standard container class vector and deque Meet these needs . By default , If not for a specific priority_queue Class instantiation specifies the container class , Then use vector.
6. Need to support random access iterators , So that the heap structure is always maintained internally . The container adapter automatically calls algorithm functions when needed make_heap、push_heap and pop_heap To automatically complete this operation .

---

Two 、priority_queue Use

Priority queues are used by default vector As its underlying container for storing data , stay vector The heap algorithm is used to vector A structure in which elements are constructed in piles , therefore priority_queue Is a pile of , All locations that need to use the heap , You can consider using priority_queue. Be careful ： By default priority_queue It's a lot .

//  The default is a lot of 
void test_priority_queue()
{
    
	priority_queue<int> pq; //  The header file queue
	pq.push(3);
	pq.push(3);
	pq.push(7);
	pq.push(1);
	pq.push(9);

	while (!pq.empty())
	{
    
		cout << pq.top() << " "; //  Take the highest priority , The default is large, with high priority 
		pq.pop();
	}
	cout << endl;
}

What if you want to make small priorities high ？
The priority of small control is high —— Pass on greater The affine function of

#include <functional> // greater The header file 
void test_priority_queue()
{
    
	//  The premise of transferring the third template parameter is to have the second template parameter 
	priority_queue<int, vector<int>, greater<int>> pq; //  Better not use deque, Because the heap may have large data 
	pq.push(3);
	pq.push(3);
	pq.push(7);
	pq.push(1);
	pq.push(9);

	while (!pq.empty())
	{
    
		cout << pq.top() << " "; //  Take the highest priority , The default is large, with high priority 
		pq.pop();
	}
	cout << endl;
}

---

3、 ... and 、topK - The... In the array K The biggest element

215. The... In the array K The biggest element

Method 1 ： Prioritize
sort( Iterator interval )： Default ascending order , Pass it in descending order greater The affine function of
O(NlogN)

//  Rank ascending 
class Solution {
    
public:
    int findKthLargest(vector<int>& nums, int k) {
    
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};
//  Subscript  0 1 2 3 4 size = 5, k = 1
//  Elements  1 2 3 4 5  The first big one is 5

//  In descending order 
class Solution {
    
public:
    int findKthLargest(vector<int>& nums, int k) {
    
        sort(nums.begin(), nums.end(), greater<int>()); //  A functor is a custom type 
        return nums[k - 1];
    }
};
// 0 1 2 3 4 size = 5, k = 1  The first big one is k - 1  Corresponding elements  5
// 5 4 3 2 1

Compared with just priority_queue and sort Zhongzhuan greater You can find obvious differences , as a result of ：

Method 2 ： A lot
Build time O（N）+ O(KlogN)

class Solution {
    
public:
    int findKthLargest(vector<int>& nums, int k) {
    
        priority_queue<int> maxHeap(nums.begin(), nums.end()); //  build N A lot of numbers 
        //  Before the k-1 Delete 
        while (--k) //  go k-1 Time 
        {
    
            maxHeap.pop();
        }
        return maxHeap.top();
    }
};

Method 3 ： build K A few small piles
O(K) Spatial complexity of

class Solution {
    
public:
    int findKthLargest(vector<int>& nums, int k) {
    
        //  If n It's big , And n Far greater than K
        //  To build a K A few small piles 
        priority_queue<int, vector<int>, greater<int>> minHeap(nums.begin(), nums.begin() + k); // O(K)
        //  The rest N-K Number , Compare with the top data in turn , If you're older than him, replace him in the pile 
        for (size_t i = k; i < nums.size(); ++i)
        {
    
            if (nums[i] > minHeap.top())
            {
    
                minHeap.pop();
                minHeap.push(nums[i]);
            }
        } // O((N-K) * logK)
        //  front K All the big numbers are in the pile , Please K The big one is the value of the heap top ( Because it's a small pile )
        return minHeap.top();
    }
    // O( K + (N-K) * logK)
};

---

Four 、priority_queue Simulation Implementation

namespace zmm
{
    
	//  By default 
	template<class T, class Container = vector<T>>
	class priority_queue
	{
    
	private:
		//  Don't want others to call him at will 
		void adjust_up(size_t child)
		{
    
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
    
				if (_con[child] > _con[parent])
				{
    
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
    
					break;
				}
			}
		}
		void adjust_down(size_t parent) //  Premise ： The left and right subtrees are small piles or piles 
		{
    
			size_t child = 2 * parent + 1; //  By default, it points to the left child 
			while (child < _con.size()) //  Turn to leaf stop 
			{
    
				if (child + 1 < _con.size() && _con[child + 1] > _con[child])
				{
    
					child++;
				}
				if (_con[child] > _con[parent])
				{
    
					swap(_con[parent], _con[child]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
    
					break;
				}
			}
		}

	public:
		priority_queue()
		{
    }
		
		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:_con(first, last)
		{
    
			//  To build as a heap 
			//  Adjust the heap building from the last non leaf 
			// i  Out-of-service size_t
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
			{
    
				adjust_down(i);
			}
		}

		void push(const T& x)
		{
    
			//  After inserting the end , Adjust up to the root 
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}
		void pop()
		{
     
			assert(!_con.empty());
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		const T& top()
		{
    
			return _con[0];
		}
		size_t size()
		{
    
			return _con.size();
		}
		bool empty()
		{
    
			return _con.empty();
		}

	private:
		Container _con; //  A custom type will call its constructor 
	};
}

Here we realize a lot , But if you want to change it to a small pile , It needs to be changed adjustup and adjustdown The symbolic relationship in , This is more troublesome , So we use a kind of imitating function to solve this problem

4.1 functor

struct Less
{
    
	bool operator()(int x, int y)
	{
    
		return x < y;
	}
};
struct Greater
{
    
	bool operator()(int x, int y)
	{
    
		return x > y;
	}
};

int main()
{
    
	//  ad locum ,less and gt Like function name , Or like a function pointer , It can be called like a function 
	Less less; // Less Is a class , Define an object 
	cout << less(1, 2) << endl; 

	Greater gt;
	cout << gt(1, 2) << endl; //  Equivalent to gt.operator()(1,2)
	return 0;
}

ad locum ,Less Called a functor type ,less It's called a function object

The above code is only applicable to int type , So we are adding template parameters

template<class T>
struct Less
{
    
	bool operator()(const T& x, const T& y) const
	{
    
		return x < y;
	}
};

template<class T>
struct Greater
{
    
	bool operator()(const T& x, const T& y) const
	{
    
		return x > y;
	}
};

int main()
{
    
	Less<int> less; // Less Is a class , Define an object 
	cout << less(1, 2) << endl; 
	//  Or you can write 
	cout << Less<int>()(1, 2) << endl;
	cout << Less<double>()(1.1, 1.2) << endl;


	Greater<int> gt;
	cout << gt(1, 2) << endl; //  Equivalent to gt.operator()(1,2)
	return 0;
}

A functor is a type , Types can be passed through template parameters

It looks like , We can imitate the function , Modified the code of simulation implementation

namespace zmm
{
    
	//  By default  -> Less
	//  A functor is a type -> You can pass through template parameters 
	template<class T>
	struct Less
	{
    
		//  Left ＜ Right 
		bool operator()(const T& x, const T& y) const
		{
    
			return x < y;
		}
	};


	//  Little heap 
	template<class T>
	struct Greater
	{
    
		bool operator()(const T& x, const T& y) const
		{
    
			return x > y;
		}
	};


	template<class T, class Container = vector<T>, class Compare = Less<T>> //  The default is Less A lot 
	class priority_queue
	{
    
	private:
		//  Don't want others to call him at will 
		void adjust_up(size_t child)
		{
    
			Compare com;
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
    
				// if (_con[child] > _con[parent])  Equivalent to  if (_con[parent] < _con[child])  Because the imitative function is left less than right 
				if (com(_con[parent], _con[child]))
				{
    
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
    
					break;
				}
			}
		}
		void adjust_down(size_t parent) //  Premise ： The left and right subtrees are small piles or piles 
		{
    
			Compare com;
			size_t child = 2 * parent + 1; //  By default, it points to the left child 
			while (child < _con.size()) //  Turn to leaf stop 
			{
    
				// if (child + 1 < _con.size() && _con[child + 1] > _con[child])
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
    
					child++;
				}
				// if (_con[child] > _con[parent])
				if (com(_con[parent], _con[child]))
				{
    
					swap(_con[parent], _con[child]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
    
					break;
				}
			}
		}

	public:
		priority_queue()
		{
    }
		
		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:_con(first, last)
		{
    
			//  To build as a heap 
			//  Adjust the heap building from the last non leaf 
			// i  Out-of-service size_t
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
			{
    
				adjust_down(i);
			}
		}

		void push(const T& x)
		{
    
			//  After inserting the end , Adjust up to the root 
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}
		void pop()
		{
     
			assert(!_con.empty());
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		const T& top()
		{
    
			return _con[0];
		}
		size_t size()
		{
    
			return _con.size();
		}
		bool empty()
		{
    
			return _con.empty();
		}

	private:
		Container _con; //  A custom type will call its constructor 
	};
}

4.2 The application of affine function

If the data type does not support comparison , Or the way of comparison is not what you want , You can use the imitative function , It's more logical to control yourself

class Date
{
    
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{
    }

	//  Because the original date class does not support < > Symbol , So overloading allows him to use 
	bool operator<(const Date& d)const
	{
    
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day); } bool operator>(const Date& d)const
	{
    
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	friend ostream& operator<<(ostream& _cout, const Date& d);
	
private:
	int _year;
	int _month;
	int _day;
};

ostream& operator<<(ostream& _cout, const Date& d)
{
    
	_cout << d._year << "-" << d._month << "-" << d._day << endl;
	return _cout;
}

void test_priority_queue2()
{
    
	priority_queue<Date, vector<Date>> pq;
	pq.push(Date(2022, 3, 26));
	pq.push(Date(2021, 10, 26));
	pq.push(Date(2023, 3, 26));

	while (!pq.empty())
	{
    
		cout << pq.top();
		pq.pop();
	}
	cout << endl;
}

struct LessPDate
{
    
	bool operator()(const Date* d1, const Date* d2) const
	{
    
		return *d1 < *d2;
	}
};
void test_priority_queue3()
{
    
	priority_queue<Date*, vector<Date*>, LessPDate> pq;
	pq.push(new Date(2022, 3, 26));
	pq.push(new Date(2021, 10, 26));
	pq.push(new Date(2023, 3, 26));

	while (!pq.empty())
	{
    
		cout << *pq.top(); //  At this time, it is not arranged according to size , Here is the comparison pointer （ Address ） size 
		//  What about date size comparison ？ ——  increase  class LessPDate
		//  If the data type does not support comparison , Or the way of comparison is not what you want , You can use the imitative function , It's more logical to control yourself 
		pq.pop();
	}
	cout << endl;
}


int main()
{
    
	test_priority_queue3();
	return 0;
}