算法复习 – 堆 优先队列

本文是优先队列即二叉堆(heap)的整理,包括:

  • push
  • pop
  • 堆的创建及其他应用

优先队列

在多任务环境中,操作系统必须决定在若干进程中运行哪个进程。我们知道,有一些任务应当具有优先权,对这些特殊的应用似乎需要一类特殊的队列,称之为优先队列(priority queue)。

优先队列至少应该实现insert和deleteMin操作。

一些简单的实现如下:

  • 链表,插入队头O(1), 删除最小的元素则需要遍历链表O(n) 另一个方法是让链表保持在排序的状态,这使得插入代价O(n),而deleteMin只需要O(1)
  • BST:二叉查找树 对于两种操作平均时间都是O(logN),但可能导致树的不平衡,用平衡树又显得过于麻烦

故优先队列使用二叉堆(binary heap)来实现。

 

二叉堆

简介

如下图所示:

binary-heap

对于数组中任意位置i上的元素,左儿子在2i上,右儿子在2*i+1上,而父亲在i/2上。

对于堆,其最小元总在根上,并且任意的子树也应该是堆。(即任意结点应该小于它的后裔)

 

堆的基本操作

1.insert

为了插入一个元素,我们在下一个空闲位置创建一个空穴,并对其与父结点进行比较,进行上滤操作。

如图,插入14,将14与父结点31比较,小于父结点,故把父结点放入下面的位置,14不断的上移直到找到正确的位置。

binary-heap-insert

实现的代码如下,显然其复杂度为O(logN)

struct Heap
{
	int currentSize;
	vector<int> array;
	Heap() :currentSize(0), array(100){} //初始化,array为100个元素的数组,currentSize = 0
	void insert(const int x)
	{
		if (currentSize == array.size() - 1) //需要当前的数组和开辟的数组的大小
			array.resize(array.size() * 2);
		int hole = ++currentSize;
		for (; hole > 1 && x < array[hole >> 1] ;hole >>= 1)//若当前的父亲比较大,则要继续往上,hole==1即为根结点
			array[hole] = array[hole >> 1];
		array[hole] = x;
	}
};

 

2.deleteMin

对于删除操作,把最后一个元素放在第一个位置,然后长度减一,相当于覆盖了原有的最小元素,然后对根结点进行下滤操作寻找合适的位置,来维护堆。如下图所示。

binary-heap-deleteMin

有一个陷阱是,将最后一个元素放在第一个位置后,原有的长度减少一,可能并没有右儿子结点。见上图的21.为此,我们需要进行判断。见下面的代码。

void deleteMin()
{
	array[1] = array[currentSize--];
	percolateDown(1);
}

void percolateDown(int hole)
{
	int child;
	int x = array[hole];
	while( (hole<<1) <= currentSize)
	{
		child = hole << 1;//左儿子
		if (child != currentSize && array[child] > array[child + 1])//若不等于currentSize,则一定有右儿子结点
			child++;
		if (array[child] >= x) break; //说明子结点已经都比x小,下滤完成
		array[hole] = array[child];
		hole = child;
	}
	array[hole] = x;
}

可以看出,删除操作的复杂度也为O(logN)

 

堆的其它操作

至于返回最小的(返回根array[1])和堆是否为空return currentSize ==0 我就不说了

1.decreaseKey(p,x)

该操作将减少p处元素的值。减少的幅度为x(x>0),这可能破坏堆的性质,因此需要进行上滤操作

2.increaseKey(p,x)

该操作将增加p处元素的值。增加的幅度为x(x>0),因此用下滤操作

3.remove(p)

该操作删除堆中位置p上的结点。首先执行decreaseKey(p,∞),然后在执行deleteMin来完成

4.bulidHeap

对于一个堆,我们可以通过N次连续的insert来完成,需要O(NlogN)操作来完成.下面要讲的是O(N)的建堆方法。

将N项以任意顺序放入树中,然后对每个有儿子结点的进行下滤操作来维护堆。可以证明,其总的复杂度为O(N)

binary-heap-delete

Heap(const vector<int> nums) :currentSize(nums.size()), array(nums.size()+10)
{
	for (int i = 0; i < nums.size(); i++) 
		array[i + 1] = nums[i]; //我们堆的下标从1开始的
	buildHeap();
}
void buildHeap()
{
	for (int i = currentSize >> 1; i > 0; i--)
		percolateDown(i);
}

 

5.最大堆

最大堆和最小堆只需要改变一下比较的函数即可。最好用c++的重载运算符。

 

C++重载运算符比如,用这个比较的话<则其实是返回>的结果,即使用之前的代码即可实现最大堆。

struct data
{
	int num;
	bool operator < (const data& x) const{
		return num > x.num;
	}
};

 

下面是Poj的一道题的堆的解法。我并没有用重载运算符,所以都需要改运算符的符号<改大于啥的。

还有就是模仿STL的priority_queue,故insert和deleteMin操作对应的是push 和 pop

你可以自己实现一遍,加深理解。:)

http://poj.org/problem?id=1862

题解在我的CSDN http://blog.csdn.net/murmured/article/details/25476967

#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN = 128;

struct Heap
{
	int curSize;
	double data[MAXN];
	Heap(){curSize =0;}
	void push(double x)
	{
		int hole = ++curSize;
		for(;hole > 1 && data[hole>>1] < x ;hole>>=1)
			data[hole] = data[hole>>1];
		data[hole] = x;
	}
	
	void pop()
	{
		data[1] = data[curSize--];
		matain(1);
	}
	
	void matain(int hole)
	{
		double x = data[hole];
		for(int child;(hole<<1) <= curSize;hole=child)
		{
			child = hole << 1;
			if(child!=curSize && data[child] < data[child+1])
				child++;
			if( x > data[child] ) break;
			data[hole]=data[child];			
		}
		data[hole] = x;
	}
	
	double top(){return data[1];}
	bool empty(){return curSize == 0;}
};


int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		Heap q;
		for(int i=0;i<n;i++){
			int x;
			scanf("%d",&x);	
			q.push(x);
		}
		
		while(!q.empty())
		{
			double x1 = q.top();q.pop();
			if(q.empty()){
				printf("%.3lf\n",x1);
				break;	
			}
			double x2=q.top();q.pop();
			q.push(sqrt(x2*x1)*2);
		}
	}
	return 0;
}

 

 

参考资料

  • 《数据结构与算法分析 C++描述》
本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > 算法复习 – 堆 优先队列
本文地址:https://www.hrwhisper.me/algorithm-heap-priority-queue/

听说长得好看的已经打赏了

算法笔记 , , , , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *