计算机基础
排序
排序算法的复杂度
二叉树：
树：不包含回路的连通无向图
二叉树：特殊的树，不为空则有根节点，左子树与右子树组成
满二叉树： 每个分支节点都有左子树和右子树，所有叶子都在同一层上。
完全二叉树： 从右向左减少叶子节点的满二叉树。
堆排序：
堆:一种特殊的完全二叉树
大顶堆：所有父节点都大于等于子节点
小顶堆：所有父节点都小于等于子节点
推的存储： 从上到下，从左到右，父节点编号为k,左儿子编号为2k,右儿子编号为2k+1.
堆排序的基本思想：将序列构成大顶推，将根节点与末尾元素进行交换； 将剩余n-1个元素重新构造堆，反复执行，得到有序序列。
说明：内容节选自以下链接，若有侵权，告知立删
MaxineZhou：什么是堆以及堆排序原理
dreamcatcher-cx：图解排序算法(三)之堆排序
编程题
题1
来源：牛客网 链接：车站建造问题
有10^8个村庄排在一条公路上，依次编号为010^8-1，相邻村庄距离为1，其中有n个村庄居住着牛牛，居住着牛牛的村庄从小到大依次为a0an-1，其中保证a0=0.
现在需要建设车站，有两个要求必须被满足：
1、每个有牛牛居住的村庄必须修建车站。
2、相邻车站的距离必须为1或为某个质数。
现给出n和a数组，求需要建设车站的最小数量。
解题思路来源于牛客网用户_hzy1721： 车站数最少为n， 若相邻车站的距离不是1或者质数，则在中间插入一个或多个车站，使得距离为1或者质数;该题等同于把一个非素数分解为素数的个数，考核内容为哥德巴赫猜想。