精华内容
下载资源
问答
  • 优先级队列

    2021-01-31 20:24:20
    优先级队列 优先级队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先级队列执行的操作有1)查找一个元素;2)插入一个新元素3)删除一个元素。...其中a是初始状态,通过插入后,状态应该变为b,其插入过

    优先级队列

    优先级队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先级队列执行的操作有1)查找一个元素;2)插入一个新元素3)删除一个元素。与这些操作对应的是top、push、pop。在最小优先级队列中,查找和删除的元素都是优先级最小的元素;在最大优先级队列中,查找和删除的元素都是优先级最大的元素。

    在这里插入图片描述

    一棵大根树:每个节点的值都大于或等于其子节点的值。
    一棵大根堆:既是大根树也是完全二叉树。(图中的a和c)

    大根堆的操作

    大根堆的插入
    在这里插入图片描述
    其中a是初始状态,通过插入后,状态应该变为b,其插入过程是:把新元素插入新节点,然后沿着新节点到根节点的路径,执行一次起泡排序,将新元素与其父节点的元素比较交换,直到后者大于或等于前者为止。
    从大根堆删除一个元素
    在这里插入图片描述
    ,就是删除根节点的元素。删除后应先把最后一个位置的元素拿出来,然后再重新组织该堆,最终找到最后一个位置的元素该放的位置。
    在大根堆的初始化问题中
    在这里插入图片描述
    排列好所有的元素称为完全二叉树,然后从最后一个具有孩子的节点开始检查即i=n/2i=\lfloor n/2 \rfloor点开始,检查是否是大根堆,然后继续检查i-1、i-2等节点的子树,直至检查到以1为根的树为止。
    大根堆的插入

    template<class T>
    void maxHeap<T>::push(const T& theElement)
    {//把元素theElement加入堆
    	//必要时增加数组程度
    	if(heapSize == arrayLength - 1)
    	{//数组长度加倍
    		changeLength1D(heap, arrayLength, 2 * arrayLength);
    		arrayLength *= 2;
    	}
    	//为元素theElement寻找插入位置
    	//currentNode从新叶子向上移动
    	int currentNode = ++heapSize;
    	while (currentNode != 1 && heap[currentNode / 2] < theElement)
    	{
    		//不能把元素theElement插入在heap[currentNode]
    		heap[currentNode] = heap[currentNode / 2];//把元素向下移动
    		currentNode /= 2;//currentNode移向双亲
    	}
    	heap[currentNode] = theElement;
    }
    

    从大根堆中删除最大元素

    template<class T>
    void maxHeap<T>::pop()
    {//删除最大元素
    	//如果堆为空,抛出异常
    	if (heapSize == 0)//堆为空
    		throw queueEmpty();
    	//删除最大元素
    	heap[1].~T();
    	//删除最后一个元素,然后重新建堆
    	T lastElement = heap[heapSize--];
    	//从根开始,为最后一个元素寻找位置
    	int currentNode = 1,
    		child = 2;
    	while(child <= heapSize)//currentNode的孩子
    	{
    		//heap[child]应该是currentNode的更大的孩子
    		if(child < heapSize && heap[child] < heap[child+1])
    			child++;
    		//可以把lastElement放在heap[currentNode]吗?
    		if(lastElement >= heap[child])
    			break;			//可以
    		//不可以
    		heap[currentNode] = heap[child];//把孩子child向上移动
    		currentNode = child;//向下移动一层寻找位置
    		child *= 2;
    	}
    	heap[currentNode] = lastElement;
    }
    

    初始化一个非空的大根堆

    template<class T>
    void maxHeap<T>::initialize(T *theHeap, int theSize)
    {//在数组theHeap[1:theSize]中建大根堆
    	delete [] heap;
    	heap = theHeap;
    	heapSize = theSize;
    
    	//堆化
    	for (int root = heapSize / 2; root >= 1; root--)
    	{
    		T rootElement = heap[root];
    		//为元素rootElement寻找为止
    		int child = 2 * root;//孩子child的双亲是元素rootElement的位置
    		while(child <= heapSize)
    		{
    			//heap[child]应该是兄弟中较小者
    			if (child < heapSize && heap[child]  < heap[child + 1])
    				child++;
    			//可以把元素rootElement放在heap[child/2]吗
    			if (rootElement >= heap[child])
    				break;//可以
    			//不可以
    			heap[child / 2] = heap[child];//把孩子向上移
    			child *= 2;//移到下一层
    		}
    		heap[child / 2] = rootElement;
    	}
    }
    

    左高树

    当两个优先级队列或多个长度不同的队列需要合并的时候,我们就需要其他数据结构了。左高树就能满足这种需要。
    考察一棵二叉树,它有一类特殊的节点叫做外部节点,它代替树中的空子树。其余节点叫做内部节点。增加了外部节点的二叉树被称为扩充二叉树
    在这里插入图片描述
    s(x)是从节点x到其子树的外部节点的所有路径中最短的一条。根据s(x)的定义,若x是外部节点,则s的值为0;若x为内部节点,则s值为min{s(L),s(R)}+1min\{s(L),s(R)\}+1。一棵二叉树称为高度优先左高树当且仅当其任何一个内部节点的左孩子的s值都大于或等于右孩子的s值。
    令x为HBLT的一个内部节点,则
    1)以x为根的子树的节点数目至少为2s(x)12^{s(x)}-1
    2)若以x为根的子树有m个节点,那么s(x)最多为log2(m+1)log_2(m+1)
    3)从x到一外部节点的最右路径(即从x开始沿右孩子移动的路径)的长度为s(x)。若一棵HBLE同时还是大根树,则称为最大HBLT
    WBLT是重量优先做概述,当且仅当其任何一个内部节点的左孩子的ω\omega值都大于或等于有孩子的ω\omega值。

    合并两棵最大HBLT

    合并策略用递归实现,令A、B为需要合并的两棵最大的HBLT,如果其中一个为空,则将另一个作为合并的结果,因此可以假设两者均不为空。为实现合并,先比较两个根元素,较大者作为合并后的HBLT的根。假定A具有较大的根,其左子树为L,C是A的右子树与B合并而成的HBLT。A与B合并所得结果即是以A的根为根,L与C为左右子树的最大HBLT。如果L的s值小于C的s值,则C为左子树,否则L为右子树。
    在这里插入图片描述

    template<class T>
    void maxHblt<T>::meld(binaryTreeNode<pair<int,T> >* &x,
    					  binaryTreeNode<pair<int,T> >* &y)
    {//合并分别以*x和*y为根的两棵左高树
    //合并后的左高树以x为根,返回x的指针
    	if(y==NULL)
    		return;			//y为空
    	if(x==NULL)
    		{x = y; return;}//x为空
    	//x和y都不为空,必要时交换x和y
    	if(x->element.second < y->element.second)
    		swap(x,y);
    	//x->element.second >= y->element.second
    	meld(x->rightChild,y);
    	//如果需要,交换x的子树,然后设置x->element.first的值
    	if(x->leftChild == NULL)
    	{//左子树为空,交换子树
    		x->leftChild = x->rightChild;
    		x->rightChild = NULL;
    		x->element.first = 1;
    	}
    	else
    	{//只有左子树的s值较小时才交换
    		if(x->leftChild->element.first < x->rightChild->element.first)
    			swap(x->leftChild,x->rightChild);
    		//更新x的s值
    		x->element.first = x->rightChild->element.first + 1;
    	}
    }
    

    最大HBLT的初始化

    线性时间的初始化算法是,首先创建n个仅含一个元素的最大HBLT,这n棵树组成一个FIFO队列,然后从队列中依次成对删除HBLT,然后将其合并后再插入队列末尾,直到队列只有一棵HBLT为止。

    应用

    堆排序

    堆可以用来实现n个元素的排序,所需时间为O(nlogn)O(nlogn)。先用n个待排序的元素来初始化一个大根堆,然后从堆中逐个提取(即删除)元素,结果,这些元素按非递增顺序排列。初始化时间为O(n)O(n)每次删除时间为O(logn)O(logn),所以总时间为O(nlogn)O(nlogn)
    在这里插入图片描述

    template<class T>
    void heapSort(T a[], int n)
    {//使用堆排序方法给数组a[1:n]排序
    	//在数组上建立大根堆
    	maxHeap<T> heap(1);
    	heap.initialize(a,n);
    	//逐个从大根堆中提取元素
    	for(int i = n - 1;i >= 1; i--)
    	{
    		T x = heap.top();
    		heap.pop();
    		a[i+1] = x;
    	}
    	//从堆的析构函数中保存数组a
    }
    

    机器调度

    一个工厂有m台一模一样的机器,我们有n个任务需要处理。设作业i的处理时间为tit_i,这个时间包括把作业放入机器和从机器上取下的时间。所谓调度是指按作业在机器上的运行时间分配作业,使得:

    • 一台机器在同一时间智能处理一个作业
    • 一个作业不能同时在两台机器上处理
    • 一个作业i的处理时间是tit_i个时间单位

    加入每台机器在0时刻都是可用的,完成时间(或调度长度)是指完成所有作业的时间。在一个非抢先调度中,作业从sis_i时刻起在某台机器上进行处理,其完成时间为si+tis_i+t_i,这里仅考虑非抢先调度。调度问题是臭名昭著的NP-复杂问题中的一个,NP-完全类问题是一类判定问题,也就是说,对这类问题的每个实例,答案为是或否。NP-复杂类问题经常用近似算法解决,在我们的调度问题中,采用了一个简单调度策略,称为最长处理时间(LPT),它的调度长度是最优调度长度的4/3-1/(3m)。在LPT算法中,作业按处理时间的递减顺序排列。当一个作业需要分配时,总是分配给最先变为空闲的机器。将作业按递减次序排列,结果为(4,2,5,6,3,7,1)分配结果如下,最终作业调度长度为17。
    在这里插入图片描述

    void makeSchedule(jobNode a[], int n, int m)
    {//输出一个基于n个作业a[1:n]的m台机器的LPT调度
    	if (n <= m)
    	{
    		cout << "Schedule each job on a different machine." << endl;
    		return;
    	}
    	heapSort(a,n); //按递增顺序排序
    	//初始化m台机器,建立小根堆
    	minHeap<machineNode> machineHeap(m);
    	for(int i = 1;i <= m; i++)
    		machineHeap.push(machineNode(1,0));
    	
    	//生成调度计划
    	for(int i = n;i >= 1;i--)
    	{//把作业i安排在第一台空闲的机器上
    		machineNode x = machineHeap.top();
    		machineHeap.pop();
    		cout << "Schedule job " << a[i].id
    			 <<" on machine " << x.id <<" from"<< x.avail 
    			 <<" to " << (x.avail + a[i].time) << endl;
    		x.avail += a[i].time;		//这台机器新的空闲时间
    		machineHeap.push(x);
    	}
    }
    

    霍夫曼编码

    霍夫曼编码(Huffman code)是另外一种文本压缩算法,这种算法根据的是不同符号在一段文本中相对出现的频率。假设一个文本是由字符a、u、x和z组成的字符串,它的长度为1000,每个字符用1字节来存储,工序1000个字节(即8000位),如果每个字符用2位二进制来编码(00=a,01=x,10=u,11=z),那么用2000位空间即可表示1000个字符。此外,还需要一定的空间来存放编码表,它可以采用如下的存储格式:符号个数,代码1,符号1,代码2,符号2.……,符号个数及每个符号分别占8位,每个代码占log2()\lceil log_2(符号个数) \rceil位。因此,在本例中,编码表需占用58 + 42 = 48位,压缩比为8000/2048=3.9。
    当不同字符出现的频率有很大差别时,我们可以通过可变长编码来缩短编码串的长度,编码方法是每次将频率(权值)最小的两个节点组成一个树,根节点为两节点频率之和,原来两个节点作为一个新的节点出现。
    在这里插入图片描述

    template<class T>
    linkedBinaryTree<int> * huffmanTree(T weight[], int n)
    {//用权weight[1:n]生成霍夫曼树,n>=1
    	//创建一组单节点树
    	huffmanNode<T> *hNode = new huffmanNode<T> [n+1];
    	linkedBinaryTree<int>> empthTree;
    	for(int i = 1; i <= n;i++)
    	{
    		hNode[i].weight = weight[i];
    		hNode[i].tree = new linkedBinaryTree<int>;
    		hNode[i].tree->makeTree(i, emptyTree, emptyTree);
    	}
    	//使一组单节点树构成小根堆
    	minHeap<huffmanNode<T> > heap(1);
    	heap.initialze(hNode, n);
    
    	//不断从小根堆中提取两个树并合并,直到剩下一棵树
    	huffmanNode<T> w,x,y;
    	linkedBinaryTree<int> *z;
    	for(i = 1; i < n; i++)
    	{
    		//从小根堆中取出两棵最轻的树
    		x = heap.top();heap.pop();
    		y = heap.top();heap.pop();
    		//合并成一棵树
    		z = new linkedBinaryTree<int>;
    		z->makeTree(0, *x.tree, *y.tree);
    		w.weight = x.weight + y.weight;
    		w.tree = z;
    		heap.push(w);
    		delete x.tree;
    		delete y.tree;
    	}
    	return heap.top().tree;
    }
    
    展开全文
  • // 蛇头根据方向处理,所以i不能等于0 this.run = function () { // 后一个元素到前一个元素的位置 for (var i = this.body.length - 1; i > 0; i--) { this.body[i].x = this.body[i - 1].x; this.body...
  • 初始状态通过判断0的移动方向可以得到不大于4中状态的子节点ÿ0c;同时需要维护一个对象来记录每个子节点的父节点是谁以此来反推出动画的运动轨迹及一个对象来负责判断当前子节点先前是否已出现过ÿ0c;出现过...
  • # 上升速度小于等于0, 改为下降状态 if self.up_speed <= 0: self.down() self.up_speed = 10 self.down_speed = 0 else: # 下降速度越来越大 self.down_speed += 30 * self.time_pass self.rect.bottom...
  • 自动循迹小车原理图

    2014-03-24 12:18:44
    float top_speed=0; float average_speed=0; uint RM_cap_new=0; uint RM_cap_old=0; uint RM_cap_count=0; uint RM_mai_kuai=0; float real_RM_speed=0.0; float total_distance=0; //测量值转化为实际值相关变量...
  • while(n) /* 当n不等于0 */ { Push(&s,n%8); /* 入栈n除以8的余数(8进制的低位) */ n=n/8; } while(!StackEmpty(s)) /* 当栈不空 */ { Pop(&s,&e); /* 弹出栈顶元素且赋值给e */ printf("%d",e); /* 输出e ...
  • 如今就这个功能未实现,简易计算器就是只包含+、-、*、/的状态,而科学计算器则包括开方、平方、幂运算、1/n等操作。各运算已实现,但就是不知道怎么切换界面。求大神添加一个能够让其变化界面的按钮函数来实现...
  • <div><p>前几个PR半天没动静ÿ0c;这次就不发PR了ÿ0c;还是发个issue记录下ÿ0c;给遇到同样问题的人。 假设有表单对象属性如下: <pre><code> form: { name: { firstName: '', lastName: &...
  • pygame.init() # 初始化所有导入的pygame模块 ai_settings = Settings() # 用ai_settings代替Settings() screen = pygame.display.set_mode( (ai_settings.screen_width, ai_settings.screen_height)) # ...
  • 只要给table设置width(style或本身的width属性),不管设置padding和border是多少,offsetWidth都等于width的值。 经测量offsetWidth是没错的,那就是说是table的width设置的问题。 w3c的table部分中说width属性是...
  • javascript函数的解释

    2011-02-26 11:03:52
    我们先设定一个初始时间值6秒:var t=6; 然后每过一秒t-1; 定义一定计时函数time2()和停止计时改变按钮属性函数time3(); function time2() { t=t-1; if(t){setTimeout('time3()',1);} else{ document....
  • 初始化:直接传入视图集合进行初始化 //获取控件 XBanner mXBanner = (XBanner) findViewById(R.id.xbanner); //添加轮播图片数据(图片数据不局限于网络图片、本地资源文件、View 都可以),刷新数据也是调用该...
  • css入门笔记

    2018-05-15 14:58:57
    取值:left左 right右 top上 bottom下 px (%)少用 取值:auto 则内容居中 2、外边距margin 6、背景颜色 1.背景色 属性:background: 取值:颜色 2.背景图片 属性:background-image:url(); 取值:url() ...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    <br>实验四 综合(课程设计) 内容及步骤: 1、假定一维数组a[n]中的每个元素值均在[0,200]区间内,用C++编写一个算法,分别统计出落在[0,20],[21,50],[51,80],[81,130],[131,200]等各区间内的元素...
  • zx_editor移动端编辑器

    2019-03-22 11:23:11
    等于0则不自动保存编辑内容。 #### # bottom: `Number` 底部距离。 #### # disableBackspaceDelete: `Boolean` 禁用键盘删除图片、链接等非文本、emoji内容。默认为true。 #### # fixed: `Boolean` 编辑器是否...
  •  法二:select top 0 * into b from a  2、说明:拷贝表(拷贝数据,源表名:a 目标表名:b) (Access可用) insert into b(a, b, c) select d,e,f from b;  3、说明:跨数据库之间表的拷贝(具体数据使用绝对路径) ...
  • C++MFC教程

    热门讨论 2013-05-21 13:37:15
    当用户进行了输入或是窗口的状态发生改变时系统都会发送消息到某一个窗口。例如当菜单转中之后会有WM_COMMAND消息发送,WPARAM的高字中(HIWORD(wParam))是命令的ID号,对菜单来讲就是菜单ID。当然用户也可以定义...
  • 2.2.4 int A[nSize],其中隐藏着若干0,其余非0整数,写一个函数int Func(int* A, int nSize),使A把0移至后面,非0整数移至数组前面并保持有序,返回值为原数据中第一个元素为0的下标。 2.2.5 写一个程序, 要求...
  • 实例011 在状态栏中显示检查框 9 实例012 带进度条的状态栏 10 实例013 状态栏中加入图标 11 1.4 导航菜单界面 11 实例014 OutLook界面 11 实例015 带导航菜单的主界面 12 实例016 图形化的导航界面 14 1.5 特色程序...
  • C#程序开发范例宝典(第2版).part02

    热门讨论 2012-11-12 07:55:11
    实例011 在状态栏中显示检查框 9 实例012 带进度条的状态栏 10 实例013 状态栏中加入图标 11 1.4 导航菜单界面 11 实例014 OutLook界面 11 实例015 带导航菜单的主界面 12 实例016 图形化的导航界面 14 1.5 ...
  • C#程序开发范例宝典(第2版).part13

    热门讨论 2012-11-12 20:17:14
    实例011 在状态栏中显示检查框 9 实例012 带进度条的状态栏 10 实例013 状态栏中加入图标 11 1.4 导航菜单界面 11 实例014 OutLook界面 11 实例015 带导航菜单的主界面 12 实例016 图形化的导航界面 14 1.5 ...
  • 实例011 在状态栏中显示检查框 9 实例012 带进度条的状态栏 10 实例013 状态栏中加入图标 11 1.4 导航菜单界面 11 实例014 OutLook界面 11 实例015 带导航菜单的主界面 12 实例016 图形化的导航界面 14 1.5 ...
  • 实例011 在状态栏中显示检查框 9 实例012 带进度条的状态栏 10 实例013 状态栏中加入图标 11 1.4 导航菜单界面 11 实例014 OutLook界面 11 实例015 带导航菜单的主界面 12 实例016 图形化的导航界面 14 1.5 ...
  • 实例011 在状态栏中显示检查框 9 实例012 带进度条的状态栏 10 实例013 状态栏中加入图标 11 1.4 导航菜单界面 11 实例014 OutLook界面 11 实例015 带导航菜单的主界面 12 实例016 图形化的导航界面 14 1.5 ...

空空如也

空空如也

1 2 3
收藏数 44
精华内容 17
关键字:

初始状态top等于0