数据结构完全二叉树时间复杂度及堆排序详解

数据结构完全二叉树时间复杂度及堆排序详解

堆排序是一种基于二叉堆数据结构的高效排序算法，其时间复杂度为O(nlogn)。本文将详细介绍堆排序的原理、时间复杂度分析以及具体的代码实现。

一、建堆的时间复杂度

1. 向上调整算法建堆

我们以极端情况考虑时间复杂度（满二叉树+遍历所有层）：

假设所有节点个数为N，树的高度为h：

• N = 2^0 + 2^1 + 2^2 + ... + 2^(h-1)
• 即N = 2^h - 1
• h = log(N+1)

时间复杂度我们以交换次数为标准：

• 1 0
• 2 2^0*2^1
• 3 2^1*2^2
• ...
• h 2^(h-2)*2^(h-1)

F(h) = 2^02^1 + 2^12^2 + ... + 2^(h-2)2^(h-1)
= 2^h(h-2) + 2

F(N) = (N+1)(log(N+1)-2) + 2（这是详细的时间复杂度函数，粗略记为O(N*logN)）

2. 向下调整算法建堆

• 1 (h-1)
• 2 2^1*(h-2)
• 3 2^2*(h-3)
• ...
• h-1 2^(h-2)*1
• h 2^(h-1)*0

找到倒数第一个非叶节点开始向下调整：

F(h) = 2^h - 1 - (h-1)

F(N) = N - log(N+1)（粗略记为O(N)）

二、堆排序

1. 概念

堆排序（Heap Sort）是一种高效的排序算法，它利用了“二叉堆”这种数据结构来进行排序。堆是一种特殊的树状结构，分为最大堆和最小堆。在最大堆中，每个父节点的值都大于或等于其子节点的值；而在最小堆中，每个父节点的值都小于或等于其子节点的值。

堆排序的基本思想是：将待排序的序列构建成一个最大堆，然后将最大值（即堆的根节点）与序列的最后一个元素交换位置，并将剩余元素重新构建为一个最大堆。重复这个过程，直到整个序列有序。

堆排序的时间复杂度为 O(nlogn)，空间复杂度为 O(1)。它是一种不稳定的排序算法，适用于排序整数、浮点数或其他可比较的数据类型。

堆排序的优点包括：

1. 时间复杂度较低：堆排序的时间复杂度为 O(nlogn)，在平均情况下比其他一些排序算法（如冒泡排序、插入排序）快得多。
2. 空间复杂度低：堆排序的空间复杂度为 O(1)，它不需要额外的存储空间来保存排序后的结果，只使用了固定的辅助空间。
3. 适用于大型数据集：堆排序可以有效地处理大型数据集，因为它的时间复杂度和空间复杂度都比较低。

堆排序的缺点包括：

1. 不稳定：堆排序是一种不稳定的排序算法，这意味着在排序过程中可能会改变相同值元素的相对顺序。
2. 难以理解和实现：堆排序的概念和操作相对复杂，对于初学者来说可能比较难以理解和实现。

总的来说，堆排序是一种高效的排序算法，但在选择排序算法时需要根据具体情况考虑其优缺点。如果对排序的稳定性要求较高，则可能需要选择其他排序算法。

堆排序的平均性能为O(nlogn)。它的时间复杂度和空间复杂度都比较低，适用于排序整数、浮点数或其他可比较的数据类型。

在最坏情况下，堆排序的时间复杂度为O(nlog2n)。因此，堆排序的平均性能较接近于最坏性能。

2. 代码思路

这里我们采用向下调整法。比如这里有一个大堆，要把它排成升序数组：

7 4 5 1 4 3

首尾交换，把大数据放后面：

3 4 5 1 4 7

然后向下调整，把下一个大数据调到堆顶：

5 4 3 1 4 7

首尾交换，把大数据放后面：

4 4 3 1 5 7

1 4 3 4 5 7

4 1 3 4 5 7

3 1 4 4 5 7

1 3 4 4 5 7

3. 代码实现

以下是使用C语言实现的堆排序代码：

void adjustDown(HeapDataType* p, int size, int parent)
{
    int child = parent * 2 + 1;
    if (p[child] < p[child + 1])
        child++;
    while (child <= size)
    {
        if (child + 1 <= size && p[parent] < p[child])
        {
            Swap(&p[parent], &p[child]);
            parent = child;
            child = child * 2 + 1;
            if (p[child] < p[child + 1])
                child++;
        }
        else break;
    }
}

void heapSort(HeapDataType* p, int size)
{
    // 建堆，一般采用向下调整法
    // 向下调整法建堆的时间复杂度为O(N)
    // 向上调整法时间复杂度为O(N*logN)
    for (int i = (size - 1 - 1) / 2; i >= 0; i--)
        adjustDown(p, size, i);

    // 堆排序，升序用大堆，降序用小堆
    while (size > 0)
    {
        Swap(&p[0], &p[size - 1]);
        size--;
        adjustDown(p, size, 0);
    }
}

本文参与 腾讯云开发者社区内容同步计划，原文发表于腾讯云开发者社区，点击这里查看原文。