题目链接:https://pta.patest.cn/pta/test/1342/exam/4/question/21731
本题即考察最小堆的基本操作:
#include "iostream"
#include "algorithm"
using namespace std;
typedef int ElementType;
typedef struct HeapStruct * MinHeap;
#define MAXN 1001
#define MINH -10001
int h[MAXN], Size;
/* 堆为完全二叉树 */
void Create() {
Size = 0;
h[0] = MINH; /* 建立哨兵 比堆中的所有元素都要小 */
}
void Insert(int x) { /* 在堆中插入元素*/
int i;
for (i = ++Size; h[i / 2] > x; i /= 2) /*找到要插入的位置即++Size 和父节点比较 直到找到比要插入节点要小的节点 */
h[i] = h[i / 2];
h[i] = x; /* 插入元素 */
}
int main() {
int n, m;
int x;
int i, j;
cin >> n >> m;
Create();
for (i = 0; i < n; i++) {
cin >> x;
Insert(x);
}
for (i = 0; i < m; i++) {
cin >> j;
cout << h[j];
while (j > 1) {
j /= 2;
cout << " " << h[j];
}
cout << endl;
}
}