欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

堆排序(Heap Sort)

程序员文章站 2022-06-06 21:03:06
...

堆排序(Heap Sort)

堆可以分为两种:大根堆以及小根堆。

大根堆指父节点值总是比其子节点值大;
小根堆指父节点值总是比其子节点值小。

如下是一个大根堆:

堆排序(Heap Sort)

每个父节点的值都比其子节点值大。

如下是一个小根堆:

堆排序(Heap Sort)

每个父节点的值都比其子节点值小。

一个大根堆,其根节点总是所有节点中最大值;
一个小根堆,其根节点总是所有节点中最小值。

例如上面大根堆中99为最大值,小根堆中1为最小值。

关于堆排序,关键在于三个函数:

建堆、向上调整,向下调整。

我们这里以从小到大排序为例来说明。

我们要对n个元素进行排序,可以先将n个元素建立成小根堆;

然后将根节点值保存(这个根节点就是n个元素最小的值),这个时候其实已经确定了最后的结果中0位置的元素的值;

然后将最末尾的节点值覆盖到根节点,将根节点进行向下调整,使其形成n-1个元素的小根堆;

再将根节点的值保存(这个根节点就是n-1个元素最小的值),这个时候其实已经确定了最后的结果中1位置的元素的值;

……

直到将n个元素都依次挑选出来,也就排序完毕。

堆是一种特殊的完全二叉树,而完全二叉树使用数组来存放时,有以下规律:

PS:图中的数字代表节点存储在数组中的位置

堆排序(Heap Sort)

可以发现每个节点与其子节点的关系总是:

堆排序(Heap Sort)

知道了父节点的存储位置是k,那么其子节点的存储位置就是k*2以及k*2+1。

知道了子节点的存储位置是k,那么其父节点的存储位置就是k/2,取整。

现在我们是从0开始存储,而不是从1开始存储(当然你可以从1开始存储,舍弃0位置),其关系如下:

堆排序(Heap Sort)

如何建堆。

可以从0位置开始遍历每个数组元素;

在每次遍历中,将当前的元素放置到堆的末尾(最开始堆大小是0,那么放置到0位置即可),然后向上调整,使堆的规模增大1;

当n个元素遍历完成,我们也就有了n个元素的最小堆。

如何向上调整。

假设要向上调整的元素存储在i,我们只需要对比i处的元素值和其父节点元素值。

若i处元素值比其父节点元素值大,则不调整(因为我们建立的是小根堆嘛),并且退出(仔细想想,是因为再比较下去也没有意义了,我只是想让最原始的i处的值像泡泡一样向上“冒”,现在 已经早到了其对应的位置,也就没有比较下去的意义了,而且也不必要比较,因为原本就是小根堆呀!);

若i处元素值比其父节点元素值小,则应该调整,交换i与其父节点的值。

如何向下调整。

假设要向下调整的元素存储在i,我们需要比较i处的元素值和其子节点(如果子节点存在,或者说合法的话)的值,取最小的放置在i处。

OK,上代码,其他都是虚的,看看代码最好理解:

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define SAFE_FREE(x) free(x);x=NULL;

/*************************************************
 * 函数名称:printHeap
 * 函数描述:输出数组中所有元素的值
 * 参数列表:arr-代表数组起始地址;
 *           arrLen-代表数组的长度;
 * 返回值  :
 * 备注    :
 * Author  :test1280
 * History :2017/05/24
 * **********************************************/
void printHeap(int *arr, int arrLen)
{
    for (int i = 0; i < arrLen; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

/****************************************************
 * 函数名称:siftup
 * 函数描述:向上调整,形成最小堆
 * 参数列表:arr-代表数组起始地址;
 *           pos-指明当前要向上调整的元素在数组中位置
 * 返回值  :
 * 备注    :
 * Author  :test1280
 * History :2017/05/24
 * *************************************************/
void siftup(int *arr, int pos)
{
    if (pos == 0)
        return;

    do
    {
        int upPos = (pos - 1) / 2;
        if (arr[upPos] > arr[pos])
        {
            int tmp = arr[upPos];
            arr[upPos] = arr[pos];
            arr[pos] = tmp;

            pos = upPos;
        }
        else
            break;
    } while (pos != 0);
}

/****************************************************
 * 函数名称:siftdown
 * 函数描述:向下调整,形成最小堆
 * 参数列表:arr-代表数组起始地址;
 *           pos-指明当前要向上调整的元素在数组中位置;
 *           arrLen-指明数组大小,或者说有效长度
 * 返回值  :
 * 备注    :
 * Author  :test1280
 * History :2017/05/24
 * *************************************************/
void siftdown(int *arr, int arrLen, int pos)
{
    int left, right, tmpIdx;
    while (1)
    {
        left = pos * 2 + 1;

        if (left >= arrLen)
            break;

        tmpIdx = pos;
        if (arr[tmpIdx] > arr[left])
            tmpIdx = left;

        right = pos * 2 + 2;
        if (right < arrLen && arr[tmpIdx] > arr[right])
            tmpIdx = right;

        if (tmpIdx != pos)
        {
            int tmp = arr[tmpIdx];
            arr[tmpIdx] = arr[pos];
            arr[pos] = tmp;

            pos = tmpIdx;
        }
        else
            break;
    }
}

/****************************************************
 * 函数名称:creat
 * 函数描述:创建最小堆
 * 参数列表:arr-代表数组起始地址;
 *           arrLen-指明数组大小
 * 返回值  :
 * 备注    :
 * Author  :test1280
 * History :2017/05/24
 * *************************************************/
void creat(int *arr, int arrLen)
{
    int *p = (int *)malloc(sizeof(int) * arrLen);
    memset(p, 0, sizeof(int) * arrLen);

    for (int i = 0; i < arrLen; i++)
    {
        p[i] = arr[i];
        siftup(p, i);
    }
    memcpy(arr, p, sizeof(int) * arrLen);

    SAFE_FREE(p);
}

/****************************************************
 * 函数名称:heapSort
 * 函数描述:堆排序
 * 参数列表:arr-代表待排序数组起始地址;
 *           arrLen-指明待排序数组大小
 * 返回值  :
 * 备注    :
 * Author  :test1280
 * History :2017/05/24
 * *************************************************/
void heapSort(int *arr, int arrLen)
{
    creat(arr, arrLen);

    int *p = (int *)malloc(sizeof(int) * arrLen);
    memset(p, 0, sizeof(int) * arrLen);

    for (int i = 0; i < arrLen; i++)
    {
        p[i] = arr[0];
        arr[0] = arr[arrLen - 1 - i];
        siftdown(arr, arrLen - 1 - i, 0);
    }

    memcpy(arr, p, sizeof(int) * arrLen);

    SAFE_FREE(p);
}

int main()
{
    int arr[9] = {36, 7, 22, 46, 12, 2, 19, 25, 28};
    heapSort(arr, 9);
    printHeap(arr, 9);
    return 0;
}

当待排序元素n比较小时,完全可以使用递归来去做siftup以及siftdown的操作:

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define SAFE_FREE(x) free(x);x=NULL;

/*************************************************
 * 函数名称:printHeap
 * 函数描述:输出数组中所有元素的值
 * 参数列表:arr-代表数组起始地址;
 *           arrLen-代表数组的长度;
 * 返回值  :
 * 备注    :
 * Author  :test1280
 * History :2017/05/24
 * **********************************************/
void printHeap(int *arr, int arrLen)
{
    for (int i = 0; i < arrLen; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

/****************************************************
 * 函数名称:siftup
 * 函数描述:向上调整,形成最小堆
 * 参数列表:arr-代表数组起始地址;
 *           pos-指明当前要向上调整的元素在数组中位置
 * 返回值  :
 * 备注    :
 * Author  :test1280
 * History :2017/05/24
 * *************************************************/
void siftup(int *arr, int pos)
{
    if (pos == 0)
        return;

    int upPos = (pos - 1) / 2;
    if (arr[upPos] > arr[pos])
    {
        int tmp = arr[upPos];
        arr[upPos] = arr[pos];
        arr[pos] = tmp;

        siftup(arr, upPos);
    }
}

/****************************************************
 * 函数名称:siftdown
 * 函数描述:向下调整,形成最小堆
 * 参数列表:arr-代表数组起始地址;
 *           pos-指明当前要向上调整的元素在数组中位置;
 *           arrLen-指明数组大小,或者说有效长度
 * 返回值  :
 * 备注    :
 * Author  :test1280
 * History :2017/05/24
 * *************************************************/
void siftdown(int *arr, int arrLen, int pos)
{
    int left, right, tmpIdx;

    left = pos * 2 + 1;

    if (left >= arrLen)
        return;

    tmpIdx = pos;
    if (arr[tmpIdx] > arr[left])
        tmpIdx = left;

    right = pos * 2 + 2;
    if (right < arrLen && arr[tmpIdx] > arr[right])
        tmpIdx = right;

    if (tmpIdx != pos)
    {
        int tmp = arr[tmpIdx];
        arr[tmpIdx] = arr[pos];
        arr[pos] = tmp;

        siftdown(arr, arrLen - 1, tmpIdx);
    }
}

/****************************************************
 * 函数名称:creat
 * 函数描述:创建最小堆
 * 参数列表:arr-代表数组起始地址;
 *           arrLen-指明数组大小
 * 返回值  :
 * 备注    :
 * Author  :test1280
 * History :2017/05/24
 * *************************************************/
void creat(int *arr, int arrLen)
{
    int *p = (int *)malloc(sizeof(int) * arrLen);
    memset(p, 0, sizeof(int) * arrLen);

    for (int i = 0; i < arrLen; i++)
    {
        p[i] = arr[i];
        siftup(p, i);
    }
    memcpy(arr, p, sizeof(int) * arrLen);

    SAFE_FREE(p);
}

/****************************************************
 * 函数名称:heapSort
 * 函数描述:堆排序
 * 参数列表:arr-代表待排序数组起始地址;
 *           arrLen-指明待排序数组大小
 * 返回值  :
 * 备注    :
 * Author  :test1280
 * History :2017/05/24
 * *************************************************/
void heapSort(int *arr, int arrLen)
{
    creat(arr, arrLen);

    int *p = (int *)malloc(sizeof(int) * arrLen);
    memset(p, 0, sizeof(int) * arrLen);

    for (int i = 0; i < arrLen; i++)
    {
        p[i] = arr[0];
        arr[0] = arr[arrLen - 1 - i];
        siftdown(arr, arrLen - 1 - i, 0);
    }

    memcpy(arr, p, sizeof(int) * arrLen);

    SAFE_FREE(p);
}

int main()
{
    int arr[14] = {99, 5, 36, 7, 22, 17, 46, 12, 2, 19, 25, 28, 1, 92};
    heapSort(arr, 14);
    printHeap(arr, 14);
    return 0;
}

仔细想想,建堆的方法只有一种吗?

》》》》》》后续补充。