最大堆实现最大优先队列

最大优先队列:队列中最大值(优先级最高的元素)总是在队首。

操作

算法

最大堆来实现最大优先队列可以获得很好的性能,插入和删除的优先级都是O(logn),访问最大元素操作的时间复杂度为O(1)。

插入(push):首先将元素插入到元素的最后,然后将该元素与它的父节点比较,如果它大于它的父节点,则交换两者的位置,重复,直到小于或等于父节点。

删除(pop):首先将队列的第一个元素与最后一个元素交换位置,然后使队列的长度-1,这样最大元素就被删除了。接下来,就是要让堆保持最大堆的性质,调用maxHeapify(0)即可。maxHeapify是堆操作中的一个最重要的函数,我在堆排序那篇文章中介绍过。

实现

下面是实现的代码,用的是C++的类模板,元素的存储用的是标准容器类vector,这样可以不用关心内存的分配和回收。我发现C++的类模板类的声明和实现必须放在一个头文件中(VC++ 2010),否则链接会出现错误。

#pragma once

#include <vector>
using std::vector;

template<class T>
class MaxPriorityQueue
{
public:
	T front();
	void push(const T& x);
	void pop();
	bool empty();
	int size();

private:
	void maxHeapify(int i);

private:
	vector<T> vct;
};

template<class T> T MaxPriorityQueue<T>::front()
{
	return vct.front();
}

template<class T> void MaxPriorityQueue<T>::push(const T& x)
{
	vct.push_back(x);

	int n = vct.size();
	for (int i = n; i > 1 && vct[i - 1] > vct[i / 2 - 1]; i /= 2)
	{
		std::swap(vct[i - 1], vct[i / 2 - 1]);
	}
}

template<class T> void MaxPriorityQueue<T>::pop()
{
	int n = vct.size();
	std::swap(vct[0], vct[n - 1]);
	vct.pop_back();
	maxHeapify(0);
}

template<class T> bool MaxPriorityQueue<T>::empty()
{
	return vct.empty();
}

template<class T> int MaxPriorityQueue<T>::size()
{
	return vct.size();
}

template<class T> void MaxPriorityQueue<T>::maxHeapify(int i)
{
	int leftChild = i * 2 + 1;
	int rightChild = i * 2 + 2;
	int largest = i;

	if (leftChild < vct.size() && vct[leftChild] > vct[largest])
	{
		largest = leftChild;
	}
	if (rightChild < vct.size() && vct[rightChild] > vct[largest])
	{
		largest = rightChild;
	}

	if (largest != i)
	{
		std::swap(vct[largest], vct[i]);
		maxHeapify(largest);
	}
}