数据结构——堆

1.介绍

在完全二叉树的存储学习中，我们已经知道可以用一维数组来表示。

一维数组以位序0开始，假设有一个结点i，则其双亲结点为（i-1）/2。

如果有左孩子，则左孩子结点为2i+1。如果有右孩子，则右孩子结点为2i+2。

而堆就是更近一步，分为大根堆和小根堆。

大根堆，即其每个结点都比其子结点（假如存在的话）要大，则根节点最大，故称为大根堆。

小根堆则相反。

2.优先级队列

优先级队列有三种实现方式。

方法1：入队时，在合适的地方插入保持优先级有序。出队，就只需要出队首即可。

时间复杂度分别为O（n）和O（1）。

方法2：入队插入队尾。出队选择优先级最高的出队。时间复杂度分别为O（1）和O（n）。

方法3：利用堆实现优先队列。

仅谈小根堆。

入队

假设已有size个元素，我们将结点先插在队尾，在树中是层序遍历的最后一个结点，其位序为size（一维数组以0开始）。

然后向上调整。假如插入结点小于其双亲结点，双亲结点位序为（size-1）/2（不懂看首段），则将其与双亲结点互换。再比较其双亲结点和双亲结点的双亲结点，直至不能互换。

因此，时间复杂度为O（logn）。

 出队

我们将队尾元素插到出队元素的位序上，假如队尾元素大于其较小的孩子结点，则两者互换，否则不换。

之前，我有疑惑的地方就是这里。为什么队尾元素不与较大的孩子比较一下呢？

万一，比之较大的孩子结点还大，岂不是破坏了小根堆的结构。

但要知道，我们选择的是队尾元素，其要么最大，要么次大（因为堆左右兄弟不分大小）。

如果是队尾元素最大，就不存在较大的孩子比队尾元素大的情况。

如果是次大的情况，那么最大的元素其实是较小的孩子（如上图）。所以也是不会破坏堆结构的。

建堆

有了出队入队，堆建立也就非常的简单。只需要多次入队即可。时间复杂度为O（nlogn）。

这是一种自上向下的建堆方法，还有一种自下而上的建堆方法。

 

先一股脑复制进队列，叶节点只有一个，其子树认为有序，然后对每个双亲结点进行向下调整。这样，我们保证在调整双亲结点时，它的左右子树先分别有序，从而完成建堆。

#pragma once
#include
template
class priorityQueue
{
	T* data;
	int cur_size;
	int max_size;
	void resize();
	void revise_down(int parent);//从双亲结点向下调整
	void revise_up(int son);
public:
	priorityQueue(T*d,int init_size = 20);
	~priorityQueue() { delete[]data; }
	void push(const T& obj);
	void pop();
	T front()const;
	void print()const;
};
template
void priorityQueue::resize()
{
	T* temp = data;
	data = new T[max_size * 2];
	max_size *= 2;
	for (int i = 0; i < max_size; i++)
		data[i] = temp[i];
	delete[]temp;
}
template
void priorityQueue::revise_down(int parent)
{
	if (parent < 0 || parent >= cur_size)
		throw("out if range");
	while (true)
	{
		int small_son = 2 * parent + 1;
		if (small_son >= cur_size)
			break;
		//比较孩子大小
		if (small_son + 1 < cur_size && data[small_son] > data[small_son + 1])
			small_son++;
		//交换
		if (data[parent] > data[small_son])
			swap(data[parent] , data[small_son]);
		else break;
		parent = small_son;
	}
}
template
void priorityQueue::revise_up(int son)
{
	if (son < 0 || son >= cur_size)
		throw("out if range");
	if (son == 0)
		return;
	while (true)
	{
		int parent = (son - 1) / 2;
		if (data[parent] > data[son])
			swap(data[parent],data[son]);
		else break;
		son = parent;
	}
}
template
priorityQueue::priorityQueue(T* d, int init_size)
{
	//我们用自下而上的方法
	//首先初始化
	cur_size = max_size = init_size;
	data = new T[max_size];
	for (int i = 0; i < cur_size; i++)
		data[i] = d[i];
	//开始自下而上的调整
	//至于为什么从cur_size/2开始，因为一些叶子结点不需要调整，当然调整也是可以的
	for (int i = cur_size / 2; i >= 0; i--)
		revise_down(i);
}
template
T priorityQueue::front()const
{
	if (cur_size != 0)
		return data[0];
	else
		throw("error");
}
template
void priorityQueue::push(const T& obj)
{
	if (cur_size == max_size)
		resize();
	data[cur_size] = obj;
	cur_size++;
	revise_up(cur_size - 1);
}
template
void priorityQueue::pop()
{
	if (cur_size == 0)
		throw("no data");
	data[0] = data[cur_size - 1];
	cur_size--;
	revise_down(0);
}
template
void priorityQueue::print()const
{
	for (int i = 0; i < cur_size; i++)
		std::cout << data[i] << " ";
	std::cout<

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/875787.html