大学的时候很多学长就跟我们讲打好基础，基础决定了未来的成长的高度，工作几年来也参加了不少面试，那么多面试，首先都是基础，甚至有的面试全部算法和数据结构，也许大学里学的挺扎实的，工作后算法用的少，很多东西都忘了。所以需要慢慢的拾起来。
排序中被问得最多的是快速排序和堆排序，对于堆排序，大学都学过，大概知道就是有大根堆，小根堆以及重建堆，很多人也就记得一个大概，让具体写就不知道怎么写了。
1.定义
堆逻辑上可以看成满二叉树，所以有k个节点，那么父节点就是k/2，堆的定义中要求每个节点
大根堆：1.a[k] >= a[2k] && a[k] >= a[2k+1]
小根堆：1.a[k] <= a[2k] && a[k] <= a[2k+1]
堆
堆排序并不是指这个堆是有序的，它的排序是不断的把根节点移到末尾然后重建剩余的堆，使之继续构造大根堆或者小根堆，再次移除，重建，每次移出来的都是剩余中最大的或者最小的，数据就有序了。
2.建初始堆
堆排序首先要解决的问题，建初始堆，就是把最初的数据建成大根堆或者小根堆。那小根堆来说，根据定义，需要让父节点小于子节点，所以我们重建堆或者调整堆就是调整父节点和子结点的位置。
//调整lst[s..m]为一个小根堆
void HeadAdjust(int *lst, int s, int m) {
int t = lst[s];
for (int j = 2 * s; j < m; j *= 2) { //对j的子结点进行筛选
//如果右结点小于左节点，j+1,j始终记录的是最小的结点下标
if (j < m && lst[j] > lst[j+1])
++j;
//如果左右结点中最小的结点都比父节点小，不用调整
if (t <= lst[j]) break;
//需要调整，t已经记录了最初的lst[s]的值,直接覆盖，s记录了上次调整的下标
lst[s] = lst[j];
s = j;
}
lst[s] = t; //调整结束，s就是t最终的位置。
}
设想如果一个二叉树，如果最下层的结点都是小根堆，那么只需依次从最下层往上调整，最终就能调整为一个小根堆，即根节点就是最小的结点。所以建初始堆的代码：
void InitHeap(int *lst, int size) {
//从最下层开始调整，依次往上，直到根节点
for (int i = size/2; i > 0; --i) {
HeadAdjust(lst, i, size);
}
}
3.调整堆
初始小根堆建成以后，根节点就是最小的节点，我们取出根节点移到数组尾部，然后重建剩余的堆，使之成继续为小根堆，如此往复直到只剩最后一个节点。
void ReBuildHeap(int *lst, int size) {
//从最下层开始调整，依次往上，直到根节点
for (int i = size; i > 1; --i) {
//根结点和最后一个节点交换，调整1..i-1为小根堆。
std::swap(lst[i], list[1];
HeadAdjust(lst, 1, i-1);
}
//执行结束，lst从1到size依次从大到小
}
完整代码：
int main(int argc, char* argv[])
{
int list[10];
for (int i = 1; i < 10; ++i) {
list[i] = rand() % 10;
printf("%d ", list[i]);
}
for (int i = 9/2; i > 0; --i) {
HeadAdjust(list, i, 9);
}
std::cout << list[1] << std::endl;
for (int i = 9; i > 1; --i) {
std::swap(list[1], list[i]);
printf("\n%d", list[i]);
HeadAdjust(list, 1, i - 1);
}
return 0;
}
也算自己的一次加深理解吧，理解记忆，只有真的理解了，才能记忆的更长久！
