手写堆排序算法

堆排序算法，是通过堆这种数据结构来实现排序。

堆，其实就是二叉树。由于排序有从小到大、从大到小两种排序方式，对应的堆也分为最小堆和最大堆。

最小堆，就是一颗完全二叉树，每个节点都比其左子节点和右子节点小，整个树的根节点最小。
最大堆，就是一颗完全二叉树，每个节点都比其左子节点和右子节点大，整个树的根节点最大。

用一个连续的数组内存空间，就能表示堆。如下图所示：

​数组中每个元素，代表最小(大)堆中的一个节点，每个节点最多有两个子节点: 左子节点和右子节点。

上图中的箭头，是从父节点指向子节点，并且位置下标小的子节点为左子节点。
箭头，只是用来描述父子关系的含义，实际代码实现中，并不存在这个箭头，而是用节点在数组中的位置下标，就可以从父节点下标计算出子节点下标，反之，从子节点下标也能计算出父节点下标。

假设父节点位置下标为 idx_parent，左子节点位置下标为 idx_left, 右子节点位置下标为 idx_right：

从父节点下标，计算出子节点下标：
idx_left = idx_parent * 2 + 1;
idx_right = idx_parent * 2 + 2;

从子节点下标，计算出父节点下标：
idx_parent = (idx_left - 1) / 2;
idx_parent = (idx_right - 1) / 2;    // 与 (idx_right - 2) / 2 的值相同

最小堆和最大堆的构建过程，是非常类似的。下面以最小堆为例，说明如何构建一个最小堆。

待排序的元素数量为N。
先分配N个元素的数组空间，用于存储堆数据。初始状态，堆是空的，元素个数为0。
插入第一个元素时，就放到数组位置0上，就是根节点。
插入第二个元素时，先放到位置1上。位置1是位置0的左子节点，因此左子节点和父节点进行比较，如果左子节点更小，则将其与父节点进行位置交换。
插入第三个元素时，先放到位置2上。位置1是位置0的右子节点，因此右子节点和父节点进行比较，如果右子节点更小，则将其与父节点进行位置交换。
插入第四个元素时，也是先放到数组的尾部，位置3上。将其与父节点(位置1)比较，如果比父节点小，则交换。交换后，还需与更上层的父节点进行比较，判断是否需要交换，一直至无需交换，或者到达根节点。

整个插入过程，总结起来，是非常简单的：
新的元素，先放到数组尾部。从这个元素的父元素，一直向树根方向，所有的元素实际上是一个从大到小的有序数列。因此最小堆的插入操作，就是向这个有序数列中进行插入。

最终，所有的元素都插入完成，最小堆的根节点，也就是数组位置0的元素，就是最小值。

可是，我们用其它排序算法(如冒泡、快速、插入、归并等)，最终的结果都是一个排好序的数列。最小堆排序，如果只提供一个最小值，那么第二小的值，第三小的值...., 怎么计算呢？

对于这些值，最小堆的算法为：
删除根节点，把数组尾部的节点放到根节点上，然后将根节点与左子节点进行比较，判断是否需要交换，调整位置。如有调整，会继续向下递归进行。此时根节点可能已经变了，不满足最小堆的要求了。因此，根节点还需要继续与右子节点进行比较，判断是否需要交换，调整位置。如有调整，会继续向下递归进行。左右两侧的比较和交换都完成时，根节点就是堆中的最小值了，也就是整个未排序数列中的第二小值了。
再次删除根节点，应用上面的算法，则会计算出第三小的值。
依次下去，就会产生从小到大的排序数列。

因此，最小(大)堆的核心算法中，插入操作是数据从树的叶子向树根方向逐层向上移动的过程，叫上移(shift_up)；而删除操作是从树根向叶子节点方向逐层向下移动的过程，叫下移(shift_down).
​

最小堆进行排序，用C实现的代码，如下：

// 最小堆排序
void minheap_sort(int* parr, int count) {
    int* pheap = (int*)malloc(count * sizeof(int));
    for (int i = 0; i < count; i++) {
        minheap_insert(pheap, i, parr[i]);
    }

    for (int i = 0; i < count; i++) {
        parr[i] = minheap_pop_root(pheap, count - i);
    }

    free(pheap);
}

// 向最小堆插入数据
static void minheap_insert(int* pheap, int count, int val) {
    pheap[count] = val;  // first, put it at tail

    // shift up
    int idx_child = count;
    while (idx_child > 0) {
        int idx_parent = (idx_child - 1) / 2;
        if (pheap[idx_parent] > pheap[idx_child]) {
            minheap_swap(pheap, idx_parent, idx_child);
            idx_child = idx_parent;
        } else {
            break;
        }
    }
}

// 最小堆，交换2个节点的数据
static void minheap_swap(int* pheap, int idx1, int idx2) {
    int val = pheap[idx1];
    pheap[idx1] = pheap[idx2];
    pheap[idx2] = val;
}

// 最小堆，弹出根节点数据，并通过下移调整为一个新的最小堆
static int minheap_pop_root(int* pheap, int count) {
    int val = pheap[0]; // root element

    pheap[0] = pheap[--count];  // put tail element to root position

    // shift down
    minheap_shift_down(pheap, count, 0);

    return val;
}

// 最小堆节点下移
static void minheap_shift_down(int* pheap, int count, int idx) {
    int idx_parent = idx;
    int idx_left = idx_parent * 2 + 1;
    int idx_right = idx_parent * 2 + 2;

    if (idx_left >= count) {    // both children are out of scope. the element is a leaf node
        return;
    } else if (idx_right >= count) {    // only left child is valid
        if (pheap[idx_parent] > pheap[idx_left]) {
            minheap_swap(pheap, idx_parent, idx_left);
        }
        return;
    } else {    // both children are valid
        if (pheap[idx_parent] > pheap[idx_left]) {    // left side shift down
            minheap_swap(pheap, idx_parent, idx_left);
            minheap_shift_down(pheap, count, idx_left);
        }

        if (pheap[idx_parent] > pheap[idx_right]) {  // right side shift down
            minheap_swap(pheap, idx_parent, idx_right);
            minheap_shift_down(pheap, count, idx_right);
        }
    }
}

​我的微信号是 实力程序员，欢迎大家转发至朋友圈，分享给更多的朋友。