首页 > 代码库 > 建堆[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]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。