建立最小值堆建立最小值堆
// 方法一
// 建立最小值堆
// 此方法类似于 课本中的 Dijkstra 算法
// 首先 要建立两个结构 一个要储存所给的点的信息 另外一个纪录边的信息
// 然后建立一个最小值堆
#include
// 建立纪录当前点的信息 的结构
struct Point
{
int tag; // 纪录点的下标
char colour; // 纪录点的颜色
int ric; // 纪录当前颜色还能够持续的时间
int tib; // 纪录每次Blue 颜色所持续的时间
int tip;...
建立最小值堆
// 方法一
// 建立最小值堆
// 此方法类似于 课本中的 Dijkstra 算法
// 首先 要建立两个结构 一个要储存所给的点的信息 另外一个纪录边的信息
// 然后建立一个最小值堆
#include
// 建立纪录当前点的信息 的结构
struct Point
{
int tag; // 纪录点的下标
char colour; // 纪录点的颜色
int ric; // 纪录当前颜色还能够持续的时间
int tib; // 纪录每次Blue 颜色所持续的时间
int tip; // 纪录每次Purple 颜色所持续的时间
int isvisit; // 纪录当前节点是否已经被走过了
int time; // 纪录当前结点的时间
}point[300]; // 申请一个300 大小的数组用来储存结点
// 建立记录当前路径信息 的结构
struct Road
{
int time; // 纪录要经过当前路径的时间
int index;// 路径索引
};
// 建立一个Road 类型的最小值堆
template
class Heap
{
public:
Road * heap; // 存放对数据的数组
int currentSize; // 纪录当前对中元素的个数
int maxSize; // 堆所能够容纳的最大的元素数目
void Insert(Road &newNode); // 向堆中插入元素 newNode
Road &RemoveMin(); // 从堆顶删除一个最小的元素
void ShiftUp(int position); // 从position向上开始调整,使序列成为一个堆
void ShiftDown(int left); // 筛选法函数 参数left 开始处理下标
void swap(int pos_x,int pos_y); // 交换函数
Heap(const int n); // 构造函数
virtual ~Heap(){delete []heap;} // 析构函数
};
// 构造函数
template Heap::Heap(const int n) {
// 设置当前 堆中的情况
currentSize=0;
maxSize=n;
// 动态申请数组 创建堆空间
heap=new Road [n]; }
// 插入函数
template void Heap::Insert(Road &newNode)
{
// 把newNode 插入到堆的最后
heap[currentSize]=newNode;
// 从最下面开始向上调整
ShiftUp(currentSize);
// 堆的当前大小 加一
currentSize++;
}
// 调整堆的函数
template void Heap::ShiftUp(int position)
{
// 首先对要调整的对象进行记录
// 从position 开始向上调整 使得堆有序
int temppos=position;
Road temp=heap[temppos];
while(temppos>0)
{
// 得到其父节点的下标
int n=(temppos-1)/2;
// 比较 如果 当前节点的下标 大于父节点的下标的时候 就结束循环
if(heap[n].time Road &Heap::RemoveMin()
{
// 首先把最后一个节点交换到第一个
swap(0,--currentSize);
// 从第一个节点开始向下调整 使其为一个堆
if(currentSize>1)
ShiftDown(0);
// 返回最小的值
return heap[currentSize]; }
// 交换函数
template void Heap::swap(int pos_x,int pos_y)
{
// 将pos_x ,pos_y 位置的数进行交换
Road temp;
temp=heap[pos_x];
heap[pos_x]=heap[pos_y];
heap[pos_y]=temp;
}
// 调整函数
template void Heap::ShiftDown(int left)
{
// 纪录要调整的首节点
int i=left;
// 得到他的左孩子下标
int j=2*left+1;
Road temp=heap[i];
// 开始比较
while(jheap[j+1].time))
j++;
if(temp.time>heap[j].time)
{
heap[i]=heap[j];
i=j;
// 向下继续
j=2*j+1;
}
else
break;
}
heap[i]=temp;
}
int road[300][300];
// road [][] 二维数组 用来记录 所有节点间的关系
int from,to;
// from 和to 分别记录 出发点和目标点
int n,m;
// n 和m 分别记录 节点数和 路径的数目
// weittime 用来记录 从当前节点到下一个节点所需要等待的时间 // 即 从 下标 为cur 的节点到达下标为 next 的节点所需要等待的时间 // 其中我们所传入的参数 time 表示当前的时间
int weitTime(int time,int cur,int next)
{
// 首先我们计算一下 在 time 的时候 两个节点的情况
int r1,r2; // 分别记录 两个节点当前颜色还能够延续的时间
char c1,c2; // 分别记录 当前节点到颜色
// 对于第一个节点
// 如果现在的时间 要小于 当前颜色剩余时间到时候
if(time < point[cur].ric)
{
// 颜色不变
c1 = point[cur].colour;
// 剩余时间满足
r1 = point[cur].ric-time;
}
else
{
// 我们记录 当前的时间减去 刚刚开始的时候剩余时间后 与两个时间之和的余
数
int t1 = (time - point[cur].ric)%(point[cur].tib+point[cur].tip);
// 分别对刚刚开始的 颜色进行讨论
// 如果为 Blue 的时候
if(point[cur].colour=='B')
{
// 如果刚刚得到的 t1 满足小于 tip 的话 即还在P 颜色中持续
if(t1>from>>to;
from --;
to --;
cin>>n>>m;
// 构建最小值堆
Heap H(m);
H.currentSize=0;
// 输入节点数据
for(i=0;i>point[i].colour>>point[i].ric>>point[i].tib>>point[i].tip;
point[i].tag=i;
point[i].isvisit=0; // 设置为没有访问过
point[i].time=-1;
}
for(i=0;i>index1>>index2;
cin>>road[index1-1][index2-1];
// 无向图
road[index2-1][index1-1]=road[index1-1][index2-1];
}
Road r;
Road tep;
r.index=from;
r.time=point[from].time=0;
// 首先 要把第一个起点进入堆中
H.Insert(r);
// 开始利用 课本中的 Dijkstra 算法
for( i=0;i0)
{
r=H.RemoveMin();
if(point[r.index].isvisit==0)
{
isfind=1;
break;
}
}
// 找不到就结束
if(!isfind)
break;
// 到达目标点
if(r.index==to)
break;
// 已经访问过了
point[r.index].isvisit=1;
// 不断更新节点的信息
for(j=0;j
本文档为【建立最小值堆】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。