堆排序及调整算法详解

堆排序及调整算法详解

引用

CSDN

1.

https://blog.csdn.net/2301_77479435/article/details/137403664

堆排序是一种基于二叉堆的排序算法，其核心思想是通过构建最大堆（大顶堆）或最小堆（小顶堆）来实现排序。堆排序的时间复杂度为O(nlogn)，是一种高效的排序算法。本文将详细介绍堆排序的基本原理以及相关的调整算法。

调整算法

向上调整

向上调整算法用于维护堆的性质，确保父节点的值大于或等于其子节点的值（对于最大堆）。以下是向上调整的具体实现：

void adjust_up(int* a, int child)
{
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (a[child] > a[parent])
        {
            swap(a[child], a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else//默认是大堆
        {
            break;
        }
    }
}

向下调整

向下调整算法假设左右子树已经是堆，然后调整当前节点及其子树以保持堆的性质。以下是向下调整的具体实现：

void adjust_down(int* a, int n, int root)
{
    int parent = root;
    int child = parent * 2 + 1;
    while (child < n)
    {
        if (child + 1 < n && a[child + 1] > a[child])//在不是满二叉树的情况下，可能出现只有左孩子没有右孩子
        {
            child++;
        }
        if (a[parent] < a[child])
        {
            swap(a[parent], a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else//已经是小堆的情况下，如果左右孩子中小的那个比父亲大，则跳出循环
        {
            break;
        }
    }
}

堆排序

堆排序的核心思想是通过构建最大堆（大顶堆）来实现排序。具体步骤如下：

1. 构建最大堆：从最后一个非叶子节点开始，依次对每个节点进行向下调整，直到根节点。
2. 排序：将堆顶元素（最大值）与最后一个元素交换，然后对剩余元素重新构建最大堆，重复此过程直到排序完成。

以下是堆排序的具体实现：

void heap_sort(int* a, int n)
{
    for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    {
        adjust_down(a, n, i);
    }
    int end = n - 1;
    while (end > 0)
    {
        swap(a[0], a[end]);
        adjust_down(a, end, 0);
        --end;
    }
}

通过以上步骤，可以实现对数组的升序排序。堆排序算法的时间复杂度为O(nlogn)，是一种高效的排序算法。