首页 > 代码库 > 建堆[HihoCoder-1405]

建堆[HihoCoder-1405]

Building Heap HihoCoder-1405

hihoCoder太阁最新面经算法竞赛11

问题大意:给定一个$N$个元素的数组$A$(元素互不相同),要求你建立满足下列要求的二叉树$T$,并输出其前序遍历:

1)$T$满足最小堆性质;

2)输入的数组$A$满足$T$的中序遍历。

这是一道数据结构基础题,主要是解决如何建堆。题目要求最小堆,其树根必然是整个树的最小值。因此在建堆过程中,只需寻找最小值,根据找到的最小值的位置将中序遍历的序列一分为二,继续对这两个子序列建堆,直到子序列没有元素为止。利用递归很容易写出程序。这道题要求输出前序遍历结果,因此可以不用实际建堆而直接在建堆的同时输出即可。时间复杂度为$O(n\rm{log}n)$。

 

 1 #include<iostream>
 2 using namespace std;
 3 template<typename T>
 4 int findmin(T A[], int size)
 5 {
 6     int min = 0;
 7     for (int i = 1; i < size; i++)
 8         if (A[i] < A[min])
 9             min = i;
10     return min;
11 }
12 void bheap(int A[], int size)
13 {
14     int minpos = findmin(A, size);
15     cout << A[minpos] << " ";
16     if (minpos!=0)
17         bheap(A, minpos);
18     if (minpos != size - 1)
19         bheap(A + minpos + 1, size - minpos - 1);;
20 }
21 int main()
22 {
23 #define TMAX 150
24     int A[TMAX];
25     int n;
26     cin >> n;
27     for (int i = 0; i < n; i++)
28         std::cin >> A[i];
29     bheap(A, n);
30     return 0;
31 }

 

建堆[HihoCoder-1405]