数据结构2:C++基于二叉堆实现优先队列

基本概念

        既然是通过二叉堆来实现一个优先队列，那么我们需要先知道什么是二叉堆，实际上，二叉堆的本质就是一个数组，只是我们从逻辑上将这个数组看作一颗完全二叉树，而这颗完全二叉树就是二叉堆。

        二叉堆又分为小根堆和大根堆，要判断一个二叉堆是哪种类型，首先要找到第一个非叶子节点的数组索引，假如数组的末尾元素索引是n，那么第一个非叶子节点的数组索引就是(n-1)/2。

        比如如图所示二叉堆的第一个非叶子节点的元素就是5。

        由此引出大根堆的性质，当i>=0并且i<=(n-1)/2时，如果arr[i]>arr[2*i+1]并且arr[i]>arr[2*i+2]，也就是当前数组的节点i的元素的值，不仅大于其右孩子的值也大于其左孩子的值，对于整个数组的i都是如此，那么这个二叉堆就是一个大根堆。

        相应的如果arr[i]<arr[2*i+1]并且arr[i]<arr[2*i+2]，这个二叉堆就是一个小根堆。

堆的操作

        如果要向一个二叉堆中增加元素，也就是入堆操作，那么添加的元素只能在数组的末尾，然后判断元素是否需要进行上浮操作，调整元素的位置，使其满足这个二叉堆的性质。

        如果要删除一个二叉堆中的元素，也就是出堆操作，那么删除的元素只能是堆顶元素也就是数组的0号位元素，并且用数组的末尾元素将数组的0号位元素进行覆盖，并判断覆盖后的0号位元素是否需要进行下沉操作。

        对于二叉堆来说，由于它本身的二叉树结构，因此入堆和出堆的时间复杂度都是log(n)。

代码实现

        要通过二叉堆实现一个优先队列，实际上就是将二叉堆的下沉和上浮操作进行封装，达到一个入队列和出队列的操作。

class PriorityQueue
{
	using Cmp = std::function<bool(int, int)>;
private:
	int size;//队列中的元素个数
	int cap;//队列占用的总空间大小(以元素大小为单位)
	int* que;//指向动态数组的指针
	Cmp cmp;
public:
	PriorityQueue(int cap = 20, Cmp cmp = std::greater<int>()) :size(0), cmp(cmp), cap(cap)
	{
		que = new int[cap];
	}
	PriorityQueue(Cmp cmp) :cmp(cmp),size(0), cap(20)
	{
		que = new int[cap];
	}
	~PriorityQueue()
	{
		delete[]que;
		que = nullptr;
	}
	//入堆函数
	void push(int val)
	{
		if (size == cap)
		{
			int* p = new int[cap * 2];
			memcpy(p, que, cap*sizeof(int));
			delete[]que;
			que = p;
			cap *= 2;
		}
		if (size == 0)
		{
			que[size] = val;
		}
		else
		{
			siftup(size, val);
		}
		size++;
	}
	//出堆函数
	void pop()
	{
		if (size == 0)throw "the queue is empty";
		size--;
		if (size > 0)
		{
			siftdown(0, que[size]);
		}
	}
	//上浮函数
	void siftup(int i,int val)
	{
		//最多上浮到首元素
		while (i > 0)
		{
			int father = (i - 1) / 2;//从孩子的索引推出父亲的索引
			if (cmp(val,que[father]))
			{
				que[i]=que[father];
				i = father;
			}
			else
			{
				break;
			}
		}
		que[i] = val;
	}
	//下沉函数
	void siftdown(int i, int val)
	{
		//不能下沉超过第一个非叶子节点
		while (i <= (size - 1 - 1) / 2)//(n-1)/2
		{
			int child = 2 * i + 1;
			//找到两个孩子中，满足条件的孩子
			if (child + 1 < size && cmp(que[child + 1], que[child]))
			{
				child = child + 1;
			}
			if (cmp(que[child], val))
			{
				que[i] = que[child];
				i = child;
			}
			else
			{
				break;
			}
		}
		que[i] = val;
	}
	bool empty() const
	{
		return size == 0;
	}
	int getsize()const
	{
		return size;
	}
	int top()const
	{
		if (size == 0)
			throw "que is empty";
		return que[0];
	}
};

这里我使用了一个函数对象作为构造函数的传入参数，这样用户就可以自己定义优先队列的构造机制，可以是小根堆也可以是大根堆，用户只需要自己定义传入的函数对象就可以了，默认的话就是大根堆。

测试代码

int main()
{
	PriorityQueue que;
	srand(time(NULL));
	for (int i = 0; i < 10; i++)
	{
		que.push(i+1);
	}
	while(!que.empty())
	{
		std::cout << que.top()<< " ";
		que.pop();
	}
	return 0;
}

从输出结果也可以发现，大根堆每次出堆的都是整个数组中的最大元素。