将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i,打印从H[i]到根结点的路径。
输入格式:
每组测试第1行包含2个正整数N和M(≤1000),分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。
输出格式:
对输入中给出的每个下标i,在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔,行末不得有多余空格。
输入样例:
1 2 3
| 5 3 46 23 26 24 10 5 4 3
|
输出样例:
思路
这道题是不断插入,不断调整,最后形成一个小顶堆。左子树的节点下标为 2 * i , 右子树的节点下标为 2 * i + 1。父节点下标为 i /2; 堆顶下标为1.
代码
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
| #include<bits/stdc++.h> using namespace std; const int maxn = 1010; int heap[maxn]; int n,m,cnt; void upAdjust(int low,int high) { int i = high , j = i /2; while(j >= low) { if(heap[j] > heap[i]){ swap(heap[j],heap[i]); i = j; j = i /2; }else break; } } void insert(int x) { heap[++cnt] = x; upAdjust(1,cnt); } int main() { cin >> n >> m; for(int i=0;i<n;i++){ int x; cin >> x; insert(x); } while(m --) { int x; cin >> x; bool flag = false; while(x > 0){ if(flag) cout << " "; else flag = true; cout << heap[x]; x /= 2; } cout << endl; } return 0; }
|