堆排序算法实践

堆排序

这讲的目的不在于堆排序毕竟快排足够好，而在于数据结构堆。
所谓堆其实是指用一颗完全二叉树维护的一维数组（简单来说就是用一个一位数组储存一颗完全二叉树）。完全二叉树请自行百度
堆有着非常鲜明的特点，就是知道一个节点在数组中储存的位置后可以轻松得到其左右子叶（如果有的话）以及其父节点、相邻节点（两个节点有相同的父节点则为相邻节点）的储存位置

堆的储存方式

首先给一颗完全二叉树标号，规则为从上至下从左至右

然后将节点的数据按照标号-1（因为数组从第0位开始）存入数组a

堆的索引

例如上图中4号节点储存在a[3]，其父节点储存在a[1]，其左右子叶在a[7]、a[8]，相邻节点存在a[4]
有如下规律：
k号节点存在a[k-1]，其父节点存在a[k div 2 -1] (div代表求商)
其左右子节点存在a[2*(k-1)+1],a[2*(k-1)+2]。
k号节点的相邻节点存在与k相邻的位置

堆排序

大顶堆（小顶堆）

大顶堆：每个结点的值都大于或等于其左右孩子结点的值

小顶堆：每个结点的值都小于或等于其左右孩子结点的值

堆排序思路

1. 将待排序数列储存到数组a中
2. 将a看作一个完整二叉树的数组储存构建堆
3. 将该完整二叉树改造成大顶堆（小顶堆）
4. 取出a[0]位的根节点（当前最大值/最小值）
5. 重复第2-4步直到排序完成
6. 升序使用大顶堆，降序使用小顶堆（方便模块化）

代码实现

以升序为例

void change(int* a, int f, int s) {//交换数组中两元素位置
    int temp;
    temp = a[f];
    a[f] = a[s];
    a[s] = temp;
}

主程序负责读入输出以及调用建堆函数

int main()
{
    int n, i;
    int a[100];
    scanf("%d", &n);
    for (i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    for(i=n-1;i>0;--i) {//总共要取出n-1个数
        set_heap(a,i+1);//构建大顶堆，利用i缩小每次构建堆的规模
        change(a,0,i);//取出最大项放队尾
    }
    for (i = 0; i < n; ++i)
        printf("%d ", a[i]);
}

构建大顶堆

void set_heap(int* a, int p) {//构建大顶堆
    for (int i = p / 2 - 1; i >= 0; --i) {//p/2-1指找到第一个有子叶的节点
        if (i * 2 + 1 < p && a[i] < a[i * 2 + 1]) {//判别左子叶
            change(a, i, i * 2 + 1);
            if (((i * 2 + 1) * 2 + 1 < p && a[i * 2 + 1] < a[(i * 2 + 1) * 2 + 1]) || ((i * 2 + 1) * 2 + 2 < p && a[i * 2 + 1] < a[(i * 2 + 1) * 2 + 2])) {
                set_heap(a, p);
                return;
            }
        }
        if (i * 2 + 2 < p && a[i] < a[i * 2 + 2]) {//判别右子叶
            change(a, i, i * 2 + 2);
            if (((i * 2 + 2) * 2 + 1 < p && a[i * 2 + 2] < a[(i * 2 + 2) * 2 + 1]) || ((i * 2 + 2) * 2 + 2 < p && a[i * 2 + 2] < a[(i * 2 + 2) * 2 + 2])) {
                set_heap(a, p);
                return;
            }
        }
    }
}

以左子叶判别为例
if (i * 2 + 1 < p && a[i] < a[i * 2 + 1])

表示若左子叶存在且值比当前节点高，则：

change(a, i, i * 2 + 2);交换父子节点

if (((i * 2 + 1) * 2 + 1 < p && a[i * 2 + 1] < a[(i * 2 + 1) * 2 + 1])
|| ((i * 2 + 1) * 2 + 2 < p && a[i * 2 + 1] < a[(i * 2 + 1) * 2 + 2]))

表示如果交换后左叶子自己爆炸了（左叶子的左叶子存在且值比左叶子高或是左子叶的右子叶存在且值比左子叶高我自己都有点乱），则：

set_heap(a, p);
return;只能回到底层重新开始建堆

。。。完结