pta 编程题12 堆中的路径

其它pta数据结构编程题请参见：pta

这道题考察的是最小堆。

堆是一个完全二叉树，因此可用数组表示，一个下标为 i 的结点的父节点下标为 i / 2，子结点下标为 2i 和 2i + 1。

插入元素：先把元素放到数组的最后面，然后不断循环和父节点比较，如果小于父节点则交换。

数组的下标为0存放一个很小的值作为哨兵，当进行插入操作时，如果插入的元素需要放到下标为1的位置时，和下标为0的值比较时会大于这个很小的值，因而会停止。

 #include <iostream>

 #include <vector>

 using namespace std;

 int heap[];

 int size = ;

 void insert(int x);

 void printTrace(int i);

 int main()

 {

     int n, m, i, t;

     cin >> n >> m;

     heap[] = -;//哨兵

     for (i = ; i < n; i++)

     {

         cin >> t;

         insert(t);

     }

     for (i = ; i < m; i++)

     {

         cin >> t;

         printTrace(t);

     }

     return ;

 }

 void insert(int x)

 {

     int i;

     for (i = ++size; heap[i / ] > x; i /= )

         heap[i] = heap[i / ];

     heap[i] = x;

 }

 void printTrace(int i)

 {

     vector<int> v;

     while (i)

     {

         v.push_back(heap[i]);

         i /= ;

     }

     for (int j = ; j < v.size(); j++)

     {

         if (j) cout << " ";

         cout << v[j];

     }

     cout << endl;

 }

巴特西

pta 编程题12 堆中的路径

最新文章

热门文章