当前位置:网站首页>C++优先级队列模拟实现

C++优先级队列模拟实现

2021-02-23 18:05:55 噫_

实现思路:

(1)优先级队列底层默认使用vector模拟堆实现,因此要对vector中的元素进行修改,使其具有堆的性质。

(2)建堆——堆的要求是任何一个结点都比其孩子结点小或者大。如果一个结点只是比其孩子结点小或者大,而它的孩子结点不满足堆的性质,则该结构不具有堆性质,因此我们可以先从底层开始往上层走,这样先让底层具有堆的性质,则再实现上层堆性质时就不必再考虑下层。由于叶子结点本身就具有堆的性质,因此从最后一个非叶子结点开始实现堆结构,如果是实现大堆,则比较父亲结点和孩子结点中较大的那个,如果小于,则交换,一个结点向下调整完毕后,调整下一个非叶子结点,直到调整到根节点结束。

(3)堆的插入——插入新的元素以后,由于原堆是具有堆性质的,因此将新插入的元素进行向上调整,如果是大堆,则它如果比其父节点大,则交换,直到达到根节点,或者比其父节点小。

(4)堆的删除——堆只能删除根节点,主要是为了像栈和队列那样具有意义,堆的删除即出最大或者最小的那个元素。可以将堆顶元素与堆尾元素进行交换,然后将堆的大小缩小一个元素大小,再对堆顶元素进行向下调整。

(5)通过传入模板类型来表示自己想创建大堆还是小堆,以及底层结构用什么。因为模板参数是一种类型,因此可以使用仿函数或者函数指针。

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();
	}
};

 

版权声明
本文为[噫_]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4249634/blog/4960935

随机推荐