Implementation of priority queue simulation in C + +

Realize the idea ：

（1） The bottom layer of priority queue uses... By default vector Simulation heap implementation , So be right vector Modify the elements in , Make it heap like .

（2） Building the heap —— The requirement of heap is that any node is smaller or larger than its child node . If a node is only smaller or larger than its child node , And its child node does not satisfy the nature of heap , Then the structure has no heap property , So we can start from the bottom and go up , So let the bottom layer have the nature of heap first , Then when we realize the properties of the upper heap, we don't have to consider the properties of the lower heap . Because the leaf node itself has the nature of heap , So start with the last non leaf node to implement the heap structure , If it's implementation , Compare the father node with the child node , If it is less than , The exchange , After a node is adjusted downward , Adjust the next non leaf node , Until the end of the adjustment to the root node .

（3） Pile insertion —— After inserting new elements , Because the original heap has the nature of heap , So adjust the newly inserted element up , If it's a big pile , If it is larger than its parent node , The exchange , Until it reaches the root node , Or smaller than its parent node .

（4） Heap delete —— Heap can only delete the root node , It's mainly to make sense like stacks and queues , The deletion of the heap produces the largest or smallest element . You can exchange the top elements with the bottom elements , Then reduce the size of the heap by one element , And then adjust the top elements down .

（5） Pass in the template type to indicate whether you want to create a heap or a small heap , And what is the underlying structure for . Because the template parameter is a type , So you can use a functor or a function pointer .

template<class T>
class my_less
{
public:
	bool operator()(const T& left,const T& right)
	{
		return left < right;
	}
};

template<class T>
class my_greater
{
public:
	bool operator()(const T& left, const T& right)
	{
		return left > right;
	}
};

template<class T,class Container=vector<T>,class Com=my_less<T>>
class my_priority_queue
{
private:
	Container heap_;
	Com com;

	void ad_down(size_t pos)
	{
		size_t parent_pos = pos;
		size_t child_pos = parent_pos * 2 + 1;
		while (child_pos < heap_.size())
		{
			if (child_pos+1<heap_.size() && com(heap_[child_pos],heap_[child_pos+1]))
				child_pos++;
			if (com(heap_[parent_pos], heap_[child_pos]))
			{
				swap(heap_[parent_pos], heap_[child_pos]);
				parent_pos = child_pos;
				child_pos = parent_pos * 2 + 1;
			}
			else
			{
				return;
			}
		}
	}

public:
	my_priority_queue()
	{}

	template<class Iterator>
	my_priority_queue(Iterator begin, Iterator end)
		:heap_(begin, end)
	{
		int pos = (heap_.size() - 2) >> 1;
		for (; pos >=0; --pos)
			ad_down(pos);
	}

	void push(const T& data)
	{
		heap_.push_back(data);
		size_t child_pos = heap_.size() - 1;
		size_t parent_pos = (child_pos - 1) / 2;
		while (child_pos)
		{
			if (com(heap_[parent_pos], heap_[child_pos]))
			{
				swap(heap_[parent_pos], heap_[child_pos]);
				child_pos = parent_pos;
				parent_pos = (child_pos - 1) / 2;
			}
			else
			{
				return;
			}
		}
	}

	void pop()
	{
		heap_[0] = heap_.back();
		heap_.pop_back();
		ad_down(0);
	}

	const T& top()const
	{
		return heap_.front();
	}

	size_t size()
	{
		return heap_.size();
	}
};