精华内容
下载资源
问答
  • 判断一个数据序列是否构成一个小根堆
    千次阅读
    2017-12-07 22:54:26

    判断一个数据序列是否构成一个小根堆

    实现代码:
    #include <stdio.h>//判断一个数据序列是否构成一个小根堆 
    bool IsMinHeap(int A[],int len){//将二叉树结点序列看成一个循序表 
    	int i;
    	if(len%2==0){//结点个数为偶数个时的判断 
    		if(A[len/2]>A[len])
    			return false;
    		for(i=len/2-1;i>=1;i--){
    			if(A[i]>A[2*i]||A[i]>A[2*i+1])
    				return false;
    		}
    	}else if(len%2==1){//结点个数为奇数个时的判断
    		for(i=len/2-1;i>=1;i--){
    			if(A[i]>A[2*i]||A[i]>A[2*i+1])
    				return false;
    		}
    	}else{
    		return true;
    	}
    	
    } 
    int main(int argc, char *argv[])
    {
    	int a[8]={0,3,6,7,8,9,10,11};//为了方便从数组下标为1的结点开始比较 
    	printf("%d\n",IsMinHeap(a,7));
    	return 0;
    }
    输出结果:
    1
    请按任意键继续. . .



    更多相关内容
  • 判断序列是否为堆

    2021-12-08 14:57:05
    堆分为最大堆和最小堆,也成为大根堆和小根堆,将序列看成完全二叉树, 1.若所有父节点都比其左子树和右子树大则最大堆(大根堆) 2.若所有父节点都比起左子树和右子树最小堆(小根堆) ...

    堆分为最大堆和最小堆,也成为大根堆和小根堆,将序列看成完全二叉树,
    1.若所有父节点都比其左子树和右子树大则为最大堆(大根堆)
    2.若所有父节点都比起左子树和右子树小则为最小堆(小根堆)
    在这里插入图片描述

    展开全文
  • 前言 关于选择排序 正文 题目一 判断一个数据序列是否构成一个小根堆 ...判断是否为小根堆,只要满足双亲结点的左右孩子均小于该结点即可。 //数组a[1...n] bool judge(int a[],int n){ if(n%2==0){

    前言

    关于选择排序

    正文

    题目一

    判断一个数据序列是否构成一个小根堆
    前提需知,一个“堆”是一颗“完全二叉树”(编号从1…n的完全二叉树存储结构的数列)
    故利用以下性质解题:

    1. 当i>1时,结点i的双亲结点为i/2(向下取整)
    2. 当2i<=n时,结点i的左孩子编号为2i
    3. 当2i+1<=n时,结点i的右孩子编号为2i+1

    判断是否为小根堆,只要满足双亲结点的左右孩子均小于该结点即可。

    //数组a[1...n]
    bool judge(int a[],int n){
    	if(n%2==0){			//len为偶数,有一个单分支
    		for(A[n/2]>A[n])//判断单分支
    		    return false;
    		for(i=n/2-1;i>=0;i--)//判断所有双分支
    		    if(A[i]>A[2*i]||A[i]>A[2*i+1])
    			   return false;		 
    	}
    	else{
    		for(i=len/2;i>=0;i--){//len为奇数,没有单分支结点
    			if(A[i]>A[2*i]||A[i]>A[2*i+1])//判断所有双分支结点
    			   return false;
    		}
    	}
    	return true;
    } 
    

    题目二

    编写简单选择排序的单链表版(不带头结点)

    void sort(linklist *L){
    	 linkNode * p,*pre,*max,*maxpre;
    	 linlist *h=L;
    	 L=NULL;
    	 while(h!=NULL){				//持续扫描原链表
    	 	p=max=h;pre=maxpre=NULL;
    	    while(p!=NULL){
    	    	if(p->data>max->data){  //找到更大的,记忆它和它的前驱
    			   max=p;
    			   maxpre=pre;
    	     	}
    			 pre=p;					//继续寻找
    			 p=p->next;
    		}
    		if(s==h)					//最大结点在原链表前段
    		   h=h->next;
    		else
    		   maxpre->next=max->next;//最大结点在原链表内
    		   max->next=L;//头插	
    		   L=max; 
    	 }
    }
    
    展开全文
  • 1、如何判断一个序列是不是? 把这个序列看成是数组型的二叉树,如果节点是i,左子数是2*i,右子数是2*i+1。 2、分为最大和最小。 (1)最大 以{100,60,70,50,32,65}例分析: 最大中所有父节点...
    1、如何判断一个序列是不是堆?
    把这个序列看成是数组型的二叉树, 如果根节点是i,左子数是2*i,右子数是2*i+1
    2、 堆分为最大堆和最小堆
    (1)最大堆
    当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。画成堆形式如下: 
    (2)最小堆
    当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆,画成堆形式如下: 
    展开全文
  • 【顺序表】判别小根堆

    千次阅读 2019-12-26 14:25:52
    设计一个算法,判断一个数据序列是否构成一个小根堆。 算法思想: 将顺序表L[1...n]视一个完全二叉树,扫描所有分支结点,遇到孩子结点的关键字小于根结点的关键字时,返回false,扫描完后,返回true。 bool ...
  • ===========如何判断一个序列是否为堆?参考答案是C,说A和D都是大根,但觉得答案有问题,按照“大根大于等于左右子节点的值”,A中的36小于47,大于30;同样地,D中的12小于24和36,这有问题吧?求大侠指教,...
  • 堆(大根堆、小根堆

    万次阅读 多人点赞 2020-05-26 20:51:02
    本文介绍完全二叉堆,包括大根堆、小根堆。相关的算法堆(大根堆、小根堆)的插入、删除、批量建立。
  • 怎么判断一个序列是不是

    千次阅读 2018-05-16 18:08:53
    答案:把这个序列看成数组型的二叉树,如果结点是i,左子树是2*i,右子树是2*i+1。...最小中所有父节点都比左子树、右子树,比如{32,50,60,70,100,65},画成堆: 符合以上两种情况的序列就是...
  • 判断一组序列数据是否

    千次阅读 2018-03-30 14:17:00
    判断一组序列数据是否: 把序列看成数组型的二叉树,如果节点是i,左子树是2*i,右子树是2*i+1最大:...EG:判断一下序列是否为堆A(10,50,80,30,60,20,15,18)B(10,18,15,20,50,80,30,60)C(10,15,18,50,80,...
  • 堆排序之小根堆

    千次阅读 2018-07-26 20:16:37
    一、  1.概念:它是一种完全二叉树(即前n-1层是满的,最后一层连续缺失右边的结点)  2.的目的:排序  3.的创建:创建一棵完全二叉树  4.存储方式:链式存储,按层存储  5.算法:建立结构体,声明...
  • [PAT] Heap 判断大小根堆

    千次阅读 2018-07-08 22:54:36
    就是给一个堆,判断是大根堆还是小根堆,然后输出它的后序遍历序列。关于堆和堆排序我这几天就写篇文章介绍一下。 给的原始数据是数组形式,所以用到堆的数组表示,从1开始,i左右孩子分别是2*i和2*i+1,写个判定抠...
  • 大根堆和小根堆的区别

    千次阅读 2018-03-13 21:07:32
    的概念实际上是一棵完全二叉树,其任何一非叶节点满足性质:Key[i]&lt;=key[2i+1]&amp;&amp;Key[i]&...分为大顶堆和顶堆,满足Key[i]&gt;=Key[2i+1]&amp;&...
  • 堆排序—大根堆,小根堆

    千次阅读 2015-02-02 20:40:02
    1.小根堆 若根节点存在左子女则根节点的值小于左子女的值;若根节点存在右子女则根节点的值小于右子女的值。 2.大根堆 若根节点存在左子女则根节点的值大于左子女的值;若根节点存在右子女则根节点的值大于右子女的...
  • 最小

    千次阅读 2020-10-16 10:45:05
    一个深度k,节点个数2^k-1的二叉树满二叉树,即一棵树深度k,没有空位。 二、完全二叉树 一棵深度k有n个节点的二叉树,对树中节点按从上至下、从左至右的顺序进行编号,如果编号i(1<=i<=n)的...
  • class Solution: def judgeIt(self , root ): ... def search(root,lower,higher): #二叉搜索树判断 if not root: return True val = root.val if val<=lower or val>=higher: return .
  • //将剩下的无序元素继续调整为小顶堆 } } //////////////////////////////////////////////////////////////////////////////////////////// 带左右孩子判断的小根堆排序 void adjustMinHeap(int *a, ...
  • 西南科技大学OJ题 判断1098

    千次阅读 2019-04-11 16:45:25
    堆的判断 1000(ms) 10000(kb) 2096/5077 编写程序判断以下给出的整数序列是否为...如果是小根堆,输出Yes,否者输出No。 样例输入 10 100 86 48 73 35 39 42 57 66 21 样例输出 No #include<s...
  • java堆排序算法(小根堆

    千次阅读 2016-12-30 20:33:10
    这几天学习排序算法,主要是引用老师的方法进行编写的,通过多线程和管道通信(即java的PipedInputStream和...通过计算得到这个排序结构的层次,每个排好序的块再进行merge,得到整个序列,下图显示的是这个模拟层次,
  • 问题描述: ...使用大根堆维护序列的前半部分,使用小根堆维护序列的后半部分。序列是指的从小到大排列。首先向大根堆里面加入元素,如果加入元素不满足条件,那么再进行下一步操作,其中条件是:1)大根堆
  • 序列——排序-大根(大顶)

    千次阅读 2015-07-18 12:15:00
    1.小根堆 如果根是儿童的存在留下的根值左孩子小于值;如果根是儿童的权利的存在的根值比他们的孩子的权利少值。 2.大根堆 如果根是儿童的存在留下的根值多名离开自己的孩子值。子女则根节点的值大于右子女的值。...
  • 在整理算法题的时候发现,大根堆(小根堆)这种数据结构在各类算法中应用比较广泛,典型的堆排序,以及利用大小根堆这种数据结构来找出一个解决问题的算法最优解。因此,我打算单独将关于堆的应用独立总结出来,...
  • Python-的实现与heapq(最小库函数)

    千次阅读 2020-12-31 17:26:52
    heapq 简介 是一个二叉树,它的每个父节点的值都只会小于... 最有趣的特性在于最小的元素总是在结点:heap[0]。 创建 heapq.heapify(x) 将list x 转换成堆,原地,线性时间内。 >>> from heapq i
  • dfs每次插入一个当前点,检测到当前节点...最后如果gt和lt都为true,说明路径的序列有递增也有递减,则不是堆,若只有gt为true,则说明路径是递增的,则为小根堆,否则为大根堆。 #include <bits/stdc++.h> usi
  • 排序(最大)的理解和实现(Java)

    千次阅读 2019-03-16 17:07:17
    通过的定义可知,节点一定是对中所有节点的最大()值。较大()的节点靠近节点(并不绝对,比如上图顶堆中60, 40均小于70,但它并没有70靠近节点) 按层序方式给节点从1开始编号,则节点之间满足下列关系: ...
  • 树1.基本概念 什么是树? 树是一种数据结构,可以表示层次关系。形状像一棵树。 最上面;树根 中间:树枝 ...它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看...除了节点外,每个

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 35,753
精华内容 14,301
关键字:

判断序列是否为小根堆