重拾数据结构之堆排序

大学的时候很多学长就跟我们讲打好基础，基础决定了未来的成长的高度，工作几年来也参加了不少面试，那么多面试，首先都是基础，甚至有的面试全部算法和数据结构，也许大学里学的挺扎实的，工作后算法用的少，很多东西都忘了。所以需要慢慢的拾起来。
排序中被问得最多的是快速排序和堆排序，对于堆排序，大学都学过，大概知道就是有大根堆，小根堆以及重建堆，很多人也就记得一个大概，让具体写就不知道怎么写了。

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;
}

也算自己的一次加深理解吧，理解记忆，只有真的理解了，才能记忆的更长久！