堆中的路径

问题描述来自PTA-数据结构与算法题目集（中文）7-5 堆中的路径：
将一系列给定数字插入一个初始为空的小顶堆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

小顶堆的操作参考自shuaixio-算法与数据结构-堆的基本操作C语言实现

博客中主要为思路与算法思想，完整的代码参看我的github

堆的概念与性质

堆是一棵完全二叉树，所以我们可以用数组H[]表示堆，这样可以简化我们许多操作。
对于从0开始下标为i的元素，我们可以得到
$parent(i)=(i-1)/2 \newline leftchild(i)=i*2+1 \newline rightchild(i)=i*2+2$
小顶堆就是树的叶子节点大于树的根节点，大顶堆就是树的根节点大于其叶子节点

小顶堆构造

堆中的路径
假设有如上图所示小顶堆,我们往其中插入一元素

那么会先插入到数组的最后一个，即10的下面，但其实叶子节点比双亲节点要大，所以要调整位置，我们将10下调

10下调后，原来10的位置被认为空缺了，如果将2放在这里，依旧是比当前的双亲节点要大，所以要继续调整，把7下调
堆中的路径
7下调后，原来7的位置被认为空缺了，如果将2放在这里，依旧是比当前的双亲节点要大，所以要继续调整，把3下调

3下调后，2到达了根节点，即下标为0，调整停止

用graphviz绘图，左右不是很会调整，望包涵
上述过程可以得出调整算法

1.将节点放在数组最后一位
2.节点为根节点的话直接放入，程序终止
3.节点与该叶子节点的双亲节点比较
4.比双亲节点大，无需调整，程序终止
5.比双亲节点小，将双亲节点下移，节点预计放入新的叶子节点
6.重复3-5步，如若节点已到根节点，那么程序终止

对应的代码如下

if(len == 0){
    heap[0] = cur;
    len++;
}else{
    heap[len]=cur;
    len++;
    int idx = len-1;
    while(idx != 0){
        // printf("%d %d\n",cur,idx);
        int parent = (idx-1)/2;
        if(cur >= heap[parent]) {
            // printf("heap[idx]:%d idx:%d heap[parent]:%d parent:%d and break\n",heap[idx],idx,heap[parent],parent);
            break;
            }
        heap[idx] = heap[parent];
        idx = parent;
    }
    heap[idx] = cur;
    // printf("finally:%d %d\n",cur,idx);
}

注意每次比较都是拿当前读入的元素cur与新的位置的双亲节点比较，即if(cur >= heap[parent])

路径生成

路径生成相对比较简单，根据 $parent(pos)=(pos-1)/2$ 可以求解出双亲节点，循环至根节点，即 $parent(pos)=0$
但是要注意，小顶堆一般下标从1开始，但是我从0开始了，所以对pos需要进行-1操作，转化为题意的标准
代码如下

int pos;
scanf("%d",&pos);
pos = pos -1;
while(pos!=0){
	printf("%d ",heap[pos]);
	pos = (pos-1)/2;
	}
printf("%d\n",heap[pos]);

堆中的路径

文章目录

堆中的路径

堆的概念与性质

小顶堆构造

路径生成

相关推荐