7-5堆中的路径

题目描述

题目地址为:https://pintia.cn/problem-sets/15/problems/713

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

输入格式:

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

输出格式:

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

输入样例:

5 3
46 23 26 24 10
5 4 3

输出样例:

24 23 10
46 23 10
26 10

思考

小顶堆

这道题首先应该创建一个小顶堆，有点像之前看过的那个视频。BiliBili视频地址

和视频中不同的是，这里需要的是插入而不是存储之后再堆化。

那么首先就来新建一个小顶堆，因为是完全二叉树，所以每次插入数据都是在数组的末尾。

插入之后进行变换，也就是和父节点进行比对，然后看是否交换顺序，直到根节点。

因为是完全二叉树就能够通过下标找到子结点和父结点，再加上题目是从下标1开始算的。那么求父结点方法就是下标/2,求子结点的方法就是下标 * 2和 下标 * 2 + 1

具体代码

#include <stdio.h>
#include <stdlib.h>

void swap(int arr[] , int i , int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp; 
}

void heapify(int heap[], int i) {
	int p = i / 2;
	while(p >= 1) {
		if (heap[i] < heap[p]) {
			swap(heap,i,p);
			i = p;
			p = p / 2;
		} else {
			break;
		}
	}
}

int main() {
	int N,M;
	scanf("%d %d",&N,&M);
	int* heap = (int*)malloc(sizeof(int) * (N+1));
	for(int i = 1; i <= N; i++) {
		scanf("%d",&heap[i]);
		heapify(heap,i);
	}
	int* way = (int*)malloc(sizeof(int) * M);
	for (int i = 0; i < M; i++) {
		scanf("%d",&way[i]);
	}
	for (int i = 0; i < M; i++) {
		while (way[i] > 0) {
			printf("%d",heap[way[i]]);
			if(way[i] != 1) {
				printf(" ");
			}
			way[i] /= 2;
		}
		printf("\n");
	}
    return 0;
}