【天梯pta】堆中的路径 (25 分)

求堆中的路径，其实是可以看作是一道最小堆（小顶堆）的板子题。主要问题是解决建立最小堆，问题就可以迎刃而解了。

因此我们将此问题分解成两个子问题，第一步是建立最小堆，第二步是输出路径。其中建立最小堆更为关键，输出路径则容易得多。

零、题目

将一系列给定数字插入一个初始为空的小顶堆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
结尾无空行

一、建立最小堆

【关键词】最小堆，在线处理，一维数组，递归，完全二叉树

【知识点Tips】

　　1.在线处理：每当输入一个数字，就实时进行操作。

　　2.完全二叉树：一层一层按照顺序填入的二叉树。当不能全部填满的时候，最后一层靠左填满。（表达能力有限，类似下图的既为完全二叉树）

　　3.最小堆：最小堆一定是一颗完全二叉树的结构。最小堆中，其父结点的数字比它的左右子结点的数字小即可。至于左右子结点的大小与它们在左在右并无关系。按照层的从上到下从左到右编号，即可获取规律：左子结点的编号/2==父结点的编号，右子结点的编号/2==父结点的编号。例：2/2=1，3/2=1（整数相除则答案取整）；6/2=3，7/2=3。

【最小堆建立的背景】给定数字个数与一列数字，要求输出按照最小堆方法的数组。

【例】

输入样例

　　5

　　46  23  26  24  10

输出样例

　　10  23  26  46  24

【思考步骤】

　　第一步：获取46后，因为是空堆，所以我们直接将其插入数组第一位。a[1]=46。

　　第二步：获取23后，我们先将其直接接在数组a的最后一个元素46后面。a[2]=23，数组a暂时为46  23。

　　我们要保证，每次新插入一个数字后的数组是一个标准的最小堆数组，因此要实时给出操作。所以我们要比较编号为2与其编号为2/2=1的父结点的大小。若比父结点小，则交换两者位置，从而保证小的结点总在上面。于是比较46与23的大小，23<46，则交换23与46的位置。因为23已经是数组第一位了，则数组a为23  46。

　　第三步：获取26后，我们先将其直接接在数组a的最后一个元素46后面。注意，在树状图中，接是按照父子关系接，因此在树状图中是连在父结点23上。a[3]=26，数组a暂时为23  46  26。按照上面所讲述原则，我们比较编号为3与其编号为3/2=1（至于为什么3/2=1则参照上文Tips3）的父结点的大小。26>23，则我们不改变数组位置。因为23已经是数组第一位了，则数组a为23  46  26。

　　第四步：获取24后，直接接在a数组后面。a[4]=24，数组a暂时为23  46  26  24。

　　比较编号为4的24与其编号为4/2=2的父结点46的大小。24<46，则交换24与46的位置，数组a暂时为23  24  26  46。

　　请注意，我们并没有比较到数组的开头，因此依旧无法保证此数组为目前的最小堆数组。因此我们再次比较编号为2的24与其父结点2/2=1的23大小，得出不用改变，则数组a为23  24  26  46。

　　第五步：获取10后直接接在a数组后面，则数组a暂时为23  24  26  46  10。

　　比较编号为5的10与其编号为5/2=2的父结点24的大小。10<24，则交换10与24的位置，数组a暂时为23  10  26  46  24。

　　比较编号为2的10与其编号为2/2=1的父结点23的大小。10<23，则交换10与23的位置。因为此时已经比较到数组的首位，所以数组a结果为10  23  26  46  24。

【关键提要】

　　可见，我们对于每一个新加入的数字进行的操作都是相同的，即：先接在数组后面，再把新数字像“冒泡”一样跟其父结点比较，若比父结点小则交换，直至数组首位。以及子结点跟父结点有关系，则我们很容易想到用递归来解决此问题。

二、输出路径

　　既然我们已经成功建立了最小堆的数组，以及清楚了子结点与父结点的关系后，输出路径已经不是难事了。输出即：子结点，每次的子结点的编号/2的结点值，直至编号到1.

　　在这里我用了一个小技巧。添加了一个bool值来将建立最小堆和输出路径在一个函数里解决。建立的标志是0，要输出的标志是1.要记得每次输出要放在函数的开头，要不然在结点编号为1的时候直接return则没机会输出了。

三、AC代码

#include 
using namespace std;

int n, m;
int a[100001];
bool flag;

void func(int index,bool f) {
    if (flag) {
        cout << a[index];
        if (index != 1) {
            cout << " ";
        }
    }
    if (index == 1) {
        return;
    }
    if (a[index / 2] > a[index]) {
        int t = a[index];
        a[index] = a[index / 2];
        a[index / 2] = t;
    }
    func(index / 2, flag);
}
int main()
{
    cin >> n  >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        func(i, flag);
    }
    int t;
    flag = 1;
    while (m--) {
        cin >> t;
        func(t, flag);
        cout << endl;
    }
    return 0;
}