将一系列给定数字插入一个初始为空的小顶堆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
这是补的之前的一个题，后面发现漏写这一道了，可能因为太简单了把。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<iostream> #include<malloc.h> typedef struct HNode* Heap; /* 堆的类型定义 */ typedef int ElementType; using namespace std; struct HNode { ElementType* Data; /* 存储元素的数组 */ int Size; /* 堆中当前元素个数 */ int Capacity; /* 堆的最大容量 */ }; typedef Heap MaxHeap; /* 最大堆 */ typedef Heap MinHeap; /* 最小堆 */ #define MINDATA -10001 /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */ MaxHeap CreateHeap(int MaxSize) { /* 创建容量为MaxSize的空的最大堆 */ MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode)); H->Data = (ElementType*)malloc((MaxSize + 1) * sizeof(ElementType)); H->Size = 0; H->Capacity = MaxSize; H->Data[0] = MINDATA; /* 定义"哨兵"为大于堆中所有可能元素的值*/ return H; } bool IsFull(MaxHeap H) { return (H->Size == H->Capacity); } bool Insert(MaxHeap H, ElementType X) { /* 将元素X插入最大堆H，其中H->Data[0]已经定义为哨兵 */ int i; if (IsFull(H)) { /*printf("最大堆已满");*/ return false; } i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */ for (; H->Data[i / 2] > X; i /= 2) H->Data[i] = H->Data[i / 2]; /* 上滤X */ H->Data[i] = X; /* 将X插入 */ return true; } int main() { int n, m, tmp; cin >> n >> m; MinHeap h; h = CreateHeap(10001); for (int i = 1; i <=n; i++) { cin >> tmp; Insert(h, tmp); } while (m--) { cin >> tmp; bool flag = true; while (tmp) { if (!flag) cout << " "; cout << h->Data[tmp]; flag = false; tmp /= 2; } cout << endl; } } |
