Question

C语言算法设计

C语言算法设计已知整数序列a[1],a[2],,,,,,,,,,a[n]已被整理成最大化堆，请用C语言设计一个算法，找出a[1],a[2],,,,,,,,,,a[n]这n个数组元素中最小的元素的下标。要求：
1.算法的时间复杂度为O([n/2])
2.证明你的算法时间代价符合要求。

Answer 1

Answer 2

由于是最大堆，则根节点（a[1]）储存最大值，所有叶子节点存储的为最小的m个值。
假设这个堆对应一颗满二叉树（n个节点），即叶子节点最多为m=n/2+1。
故只要遍历数组a[n/2-1]到a[n]即可。
所以时间复杂度为O([n/2])
遍历的算法就不写了

Answer 3

看看谭浩强的C把讲的很全面