The Realization Of Heap

8月 12, 2019 Data Structure

The Realization Of Heap

一:堆的作用

堆是一种二叉树的树形结构,广义上分为大根堆与小根堆。按照人为的排序法则,通过保证父节点与子节点保持一致的顺应关系,使得根节点一定为最大/最小的元素,同时每一次的压入与弹出,都通过修正来维护这种关系,使得堆能够建立有序数据,并在插入与删除元素时高效的维护数据。需要注意的是,堆能直接访问的元素,仅有子节点。

二:STL库中导入与实现堆

C++的STL库中,有已经编写好的priority_queue的容器,包含在<queue>的头文件中,初始化形式一般为
priority_queue<Type, Container, Functional>
例如int类型的小根堆初始化则为
priority_queue<int,vector<int>, less<int> > a;
当数据类型为自己定义的结构体时,需自定义优先规则
实现方法一般为重载“<”运算符
struct info
{
int val
;
bool operator <(const info &a) const{return a.val < val};
};
priority_queue<info> a;

三:手动编写堆

以int类型的大根堆为例,根节点的16为整个堆中的max值,随后的数据虽然乱序,但都保证了父节点大于子节点的法则,同时可以发现当父节点的 Index = i时,两个子节点的Index分别为 2*i, 2*i+1,而兄弟节点的父节点Index均为 i/2,
所以确定了父节点与子节点的查找关系之后,可以利用数组来存储这一数据结构

大根堆的实例

即:
#define DAD(x) ((x)/2)
#define LE(x)  ((x)<<1)
#define RT(x)  (((x)<<1)|1)

压入元素时的维护

堆的排序就是父节点大于子节点,因此我们围绕这一规则,当插入元素时,如果他大于父节点,则交换这对父子的索引,然后将新元素再与新的父节点比较,直到达到根节点或不再大于父节点为止,这样就能保持父节点恒大于等于子节点。

void repair_up(int x)
 {
     if(x == 1) return ;
     if(a[x] < a[x/2])
     {
     swap(a[x],a[x/2]);
     repair_up(x/2);
     }
 }

弹出元素时的维护

因为使用了数组存储,我们希望在索引上弹出索引最大的元素,而堆能直接访问的又只有根节点,所以弹出根节点是最好的选择,因此,swap(根节点,索引最大节点),然后与压入时相反的法则,从根节点一路向下维护到树的最后一层或大于两个子节点为止。

void repair_down(int x)
 {
     if(2*x > cnt) return ;
     if(2*x == cnt)
     {
          if(a[x] > a[2*x]) swap(a[x],a[2*x]);
          return ;
     }
     int tar = a[2*x] > a[2*x+1]?2*x+1:2*x;
     if(a[x] > a[tar])
     {
         swap(a[x],a[tar]);
         repair_down(tar);
     }
 }

通过结构体或类封装来完整实现

struct heap
{
	int a[1000],cnt = 0;
	void repair_up(int x)
	{
		if(x == 1) return ;
		if(a[x] < a[x/2])
		{
			swap(a[x],a[x/2]);
			repair_up(x/2);
		}
	}
	void repair_down(int x)
	{
		if(2*x > cnt) return ;
		if(2*x == cnt)
		{
			if(a[x] > a[2*x]) swap(a[x],a[2*x]);
			return ;
		}
		int tar = a[2*x] > a[2*x+1]?2*x+1:2*x;
		if(a[x] > a[tar])
		{
			swap(a[x],a[tar]);
			repair_down(tar);
		}
	}
	void pop()
	{
		swap(a[1],a[cnt]);
		cnt--;
		repair_down(1);
	}
	void push(long long x)
	{
		cnt++;
		a[cnt] = x;
		repair_up(cnt);
	}
	int top(){return a[1];}
	bool empty(){return cnt == 0;}
	int sum()
	{
		int ans = 0;
		for(int i = 1;i <= min(20,cnt);i++) ans += a[i];
		return ans;
	}
};

堆的应用非常广泛,在各大Online Judge中,也不乏有应用堆解题的题目

题目来源于EOJ.1074寻找EMB富豪
该题因需邀请码才能提交,仅给题面做参考
题目来源于洛谷.2369
链接: https://www.luogu.org/problem/P2369

STL优先队列的AC代码

# include <iostream>
# include <queue>
using namespace std;
int main(void)
{
	priority_queue<int> a;
	int n,m,k,*p;
	cin>>n>>m;
	p = new int [m];
	for(int i = 0;i < n;i++)
	{
		cin>>k;
		a.push(k);
		if(i >= m) a.pop();
	}
	for(int i = 0;i < m;i++)
	{
		p[i] = a.top();
		a.pop();
	}
	for(int i = m-1;i >= 0;i--) cout<<p[i]<<endl;
	return 0;
}

手写堆的AC代码

# include <iostream>
# include <cstdio>
using namespace std;
struct heap
{
	int a[100005],cnt = 0;
	void repair_up(int x)
	{
		if(x == 1) return ;
		if(a[x] > a[x/2])// TRANS
		{
			swap(a[x],a[x/2]);
			repair_up(x/2);
		}
	}
	void repair_down(int x)
	{
		if(2*x > cnt) return ;
		if(2*x == cnt)
		{
			if(a[x] < a[2*x]) swap(a[x],a[2*x]); //TRANS
			return ;
		}
		int tar = a[2*x] < a[2*x+1]?2*x+1:2*x;//TRANS
		if(a[x] < a[tar])//TRANS
		{
			swap(a[x],a[tar]);
			repair_down(tar);
		}
	}
	void pop()
	{
		swap(a[1],a[cnt]);
		cnt--;
		repair_down(1);
	}
	void ins(int x)
	{
		cnt++;
		a[cnt] = x;
		repair_up(cnt);
	}
	int top(){return a[1];}
};
int main(void)
{
	int n,m,*p,v;
	cin>>n>>m;
	heap w;
	for(int i = 0;i < n;i++)
	{
		scanf("%d",&v);
		w.ins(v);
		if(i >= m) w.pop();
	}
	p = new int [m];
	for(int i = 0;i < m;i++)
	{
		p[i] = w.top();
		w.pop();
	}
	for(int i = m-1;i >= 0;i--) cout<<p[i]<<endl;
	return 0;
}

根据评测机给出的评测时间,仅在实现这部分功能时,书写堆的耗费时间大约是STL优先队列的百分之60,因为优先队列接口众多,所以在排序维护方面手写堆具有更优越的性能,在EOJ.1074中,数据更为庞大,此时priority_queue是无法通过的。

堆的应用很广泛,同时也是最简单的树形结构之一,非常适合作为初学树的模型来学习。

Kuroko

作者Kuroko

I am an ECNU college stduent.

《The Realization Of Heap》有10个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注