浙大数据结构的编程题——堆中的路径

堆中的路径

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

思路

什么是堆？？

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

堆与优先队列的关系

  1. 堆是优先队列（Priority Queue）的一种实现形式。另、普通队列（Queue），先进先出。
  2. 堆是一种具体的数据结构，而优先队列时一种抽象的数据结构，可以使用不同的底层数据结构来实现
  3. 二叉树可以和二叉树一样使用左右节点的方式来实现，但是我们可以看到我们现在是一层一层按顺序排放的，所以我们可以用更巧妙的方式来实现（数组）————即当前结点n的左子结点为2 * n，右结点为2 * n+1

heap的实现

heap是完全二叉树,可用数组来实现其存储。

每次插入时，新增结点的位置是确定的，所要做的是比较插入的结点与其父节点的大小关系。若是满足最小或者最大堆的关系，则进行插入。否则，将交换位置，将其父节点与新结点交换。此时继续与父节点比较，符合则插入，不符则交换。以此循环。

Code

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <iterator>
#include <math.h>
#include <stack>
#include <queue>
using namespace std;

#define MAXN 1001
#define MINH -10001


int H[MAXN], size1;

void Create() {
	size1 = 0;
	H[0] = MINH;
}

void Insert(int X) {
	int i = ++size1;
	for (; X < H[i / 2]; i /= 2) {
		H[i] = H[i / 2];
	}
	H[i] = X;
}

int main() {
	//begin:			end:
	ios::sync_with_stdio(false);

	int n, m, x;

	cin >> n >> m;
	Create();
	for (int i = 0; i < n; i++) {
		cin >> x;
		Insert(x);
	}
	for (int i = 0; i < m; i++) {
		int j;
		cin >> j;
		cout << H[j];
		while (j > 1) {
			j /= 2;
			cout << " " << H[j];
		}
		cout << endl;
	}
	return 0;
}