05-树7 堆中的路径

我会带着你远行 2022-08-21 10:52 118阅读 0赞

将一系列给定数字插入一个初始为空的小顶堆`H[]`。随后对任意给定的下标`i`，打印从`H[i]`到根结点的路径。

### 输入格式: ###

每组测试第1行包含2个正整数NNN和MMM(≤1000\\le 1000≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间\[-10000, 10000\]内的NNN个要被插入一个初始为空的小顶堆的整数。最后一行给出MMM个下标。

### 输出格式: ###

对输入中给出的每个下标`i`，在一行中输出从`H[i]`到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。

### 输入样例: ###

5 3
    46 23 26 24 10
    5 4 3

### 输出样例: ###

24 23 10
    46 23 10
    26 10

运行超时了。。。。

#define MAXN 1001
    #define MINH -10001
    
    int H[MAXN],size    //数组来装堆（完全二叉树），i为父节点，左儿子为i*-1，右儿子为i*2
    
    void Create()
    {
    	size = 0;
    	H[0] = MINH;
    }
    
    void Insert(int X)
    {
    	int i;
    	if(size==1000) // 堆已满
            return;
    	for(i=++size;H[i/2]>X;i/2){
    		H[i] = H[i/2];      //从1开始插入，对比每个节点的父节点与当前插入的节点哪个大，哪个小，这是一个最小堆，要求父节点都小于子节点
    	}
    	H[i] = X;
    }
    
    int main()
    {
    	int n,m,x,i,j;
    	scanf("%d %d",&n,&m);
    	Create();
    	for(i=0;i<n;i++){
    		scanf("%d",&x);
    		Insert(x);
    	}
    	for(i=0;i<m;i++){
    		scanf("%d";&j);
    		printf("%d",H[j]);
    		while(j>1){
    			j /= 2;
    			printf("%d",H[j]);
    		}
    		printf("\n");
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，118人围观）

还没有评论，来说两句吧...

相关阅读

相关第五章树 22 AcWing 1649. 堆路径

第五章树 22 AcWing 1649. 堆路径原题链接 [AcWing 1649. 堆路径][AcWing 1649.] 算法标签堆树的遍历

我会带着你远行/ 2023年09月24日 14:06/ 0 赞/ 42 阅读

相关 124. 二叉树中的最大路径和(树上的路径)

\\\ 解题思路求整棵树上的最长路径,我们可以把这个问题化为若干个子问题,即求经过每个子节点的最长路径设x为树上的一个子节点,那么经过该点的最大路径可以表示为f(x)

比眉伴天荒/ 2023年01月10日 01:21/ 0 赞/ 147 阅读

相关 JVM05 - 堆

目录 1.堆的核心概述 1.1 堆的基本概念 1.2 堆内存分区 2.年轻代与老年代 2.1 Java对象分类 2.2 配置

阳光穿透心脏的1/2处/ 2023年01月05日 03:56/ 0 赞/ 126 阅读

相关 2021-01-05 | 124. 二叉树中的最大路径和

1. 题目描述给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且

分手后的思念是犯贱/ 2023年01月02日 12:30/ 0 赞/ 107 阅读

相关 05-树7 堆中的路径

将一系列给定数字插入一个初始为空的小顶堆`H[]`。随后对任意给定的下标`i`，打印从`H[i]`到根结点的路径。输入格式: 每组测试第1行包含2个正整数NNN和MM

我会带着你远行/ 2022年08月21日 10:52/ 0 赞/ 119 阅读

相关树-堆结构

think： 1 今天上午学习了树中的堆结构将一些对结构的基本操作写了写，记录下来，后续继续优化。 include <stdio.h> include <

红太狼/ 2022年07月12日 03:36/ 0 赞/ 105 阅读

相关《数据结构》05-树7 堆中的路径

题目将一系列给定数字插入一个初始为空的小顶堆H\[\]。随后对任意给定的下标i，打印从H\[i\]到根结点的路径。输入格式: 每组测试第1行包含2个正整数N和M

绝地灬酷狼/ 2022年04月22日 10:18/ 0 赞/ 147 阅读

相关数据结构——树——堆的学习

首先要知道堆是什么：优先队列（Priority Queue）：特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。 ![在这

淡淡的烟草味﹌/ 2022年04月16日 00:37/ 0 赞/ 180 阅读

相关 7-5 堆中的路径（25 分）

将一系列给定数字插入一个初始为空的小顶堆H\[\]。随后对任意给定的下标i，打印从H\[i\]到根结点的路径。输入格式: 每组测试第1行包含2个正整数N和M(≤100

布满荆棘的人生/ 2022年04月16日 00:36/ 0 赞/ 113 阅读

相关 leetcode:124. 二叉树中的最大路径和(树)

给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。示例 1:

╰半橙微兮°/ 2021年09月28日 12:58/ 0 赞/ 221 阅读