数据结构之堆(Heap)详解

数据结构之堆(Heap)详解

引用

CSDN

1.

https://blog.csdn.net/qq_61820853/article/details/138626255

堆（Heap）是一种特殊的数据结构，广泛应用于计算机科学领域。本文将详细介绍堆的概念、实现方法及其在堆排序和Top-K问题中的应用。

一、堆的概念及结构

堆（Heap）是一种特殊的非线性结构，其元素按照完全二叉树的顺序存储方式存储在数组中。堆可以分为大根堆和小根堆：

• 大根堆：所有父结点都大于等于左右孩子结点。
• 小根堆：所有父结点都小于等于左右孩子结点。

堆具有以下性质：

1. 堆是一棵完全二叉树。
2. 堆中某个节点的值总是不大于或不小于其父节点的值。
3. 如果一个堆为大（小）根堆，则它的左右子树也都是大（小）根堆。
4. 小堆的存储结构不是升序，大堆的存储结构也不是降序。
5. 堆中任意结点下标为 i，则它的左孩子结点下标为2i+1，右孩子结点下标为2i+2，父结点下标为(i-1)/2。

二、堆的实现

堆的实现主要依赖两个重要算法：向上调整和向下调整。

1. 向上调整算法

向上调整算法通常在堆中插入元素时使用。具体实现如下：

1. 给定一个数组和一个结点下标，该结点与其父结点的值进行比较。
2. 如果该结点的值 ≥ 其父结点的值，已经是小堆了，则不再继续调整；
3. 如果该结点的值 < 其父结点的值，需要将二者交换，然后将父结点当做孩子结点，继续向上对比和交换，直到调整到堆顶。

//小根堆 向上调整
void AdjustUp(DataType* a, int child)
{
    int parent = (child - 1) / 2;//父结点下标
    while (a[child] < a[parent])//建大堆
    {
        Swap(&a[child], &a[parent]);
        child = parent;
        parent = (child - 1) / 2;
    }
}
//交换函数
void Swap(DataType* p1, DataType* p2)
{
    DataType tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

向上调整算法的时间复杂度为O(logN)。

2. 向下调整算法

向下调整算法在堆排序和堆的创建中经常使用。其前提条件是左右子树必须是一个堆。

具体实现如下：

1. 从该结点开始，与其左右孩子结点中较大（较小）的结点进行比较。
2. 如果该结点的值 ≤ 其较小（较大）孩子结点的值，已经是小堆了，则不再继续调整；
3. 如果该结点的值 > 其较小（较大）孩子结点的值，需要将二者交换，然后将较小的孩子结点当做父结点，继续向下对比和交换，直到调整到叶子结点。

//向下调整
void AdjustDown(DataType* a, int parent, int n)
{
    int child = 2 * parent + 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 = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}

向下调整算法的时间复杂度也为O(logN)。

3. 堆的创建

向上调整建堆

从根结点的左孩子结点开始，每个结点都向上调整，直到调整到最后一个结点，就可以调整成堆。时间复杂度为O(N*logN)。

向下调整建堆

从最后一个非叶子结点开始倒着调整，时间复杂度为O(N)。实际应用中，一般都使用向下调整算法建堆。

//向下调整建堆 效率O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
    AdjustDown(a, i, n);
}

4. 堆的插入

堆的插入需要用到向上调整算法。

1. 在堆的末尾插入一个元素；
2. 该元素向上调整，直到满足堆的性质。

//入堆
void HeapPush(Heap* php, HDataType x)
{
    assert(php);
    //扩容
    if (php->size == php->capacity)
    {
        HDataType* tmp = (HDataType*)realloc(php->a, sizeof(HDataType) * (INC_SZ + php->capacity));
        if (NULL == tmp)
        {
            perror("malloc");
            return;
        }
        php->a = tmp;
        php->capacity += INC_SZ;
    }
    php->a[php->size++] = x;//尾插
    AdjustUp(php->a, php->size - 1);//向上调整
}

5. 堆的删除

删除的是堆顶的元素，删除之后仍然保证是堆。

1. 将堆顶元素与最后一个元素交换；
2. 堆长度-1，即删除最后一个位置；
3. 将交换后的堆顶元素向下调整。

//出堆
void HeapPop(Heap* php)
{
    assert(php);
    assert(!HeapEmpty(php));
    //将尾数据和堆顶数据交换，交换后的堆顶元素再向下调整
    Swap(&php->a[php->size - 1], &php->a[0]);
    php->size--;//堆的有效长度-1
    AdjustDown(php->a, 0, php->size);
}

6. 堆的其他操作

//返回堆顶元素
HDataType HeapTop(Heap* php)
{
    assert(php);
    return php->a[0];
}
//判堆空
bool HeapEmpty(Heap* php)
{
    assert(php);
    return php->size == 0;
}
//堆的元素个数
int HeapSize(Heap* php)
{
    assert(php);
    return php->size;
}

三、堆的应用

1. 堆排序

堆排序的实现步骤：

1. 先将数组建堆；
2. 将堆顶元素与堆末尾元素交换；
3. 堆有效长度-1；
4. 再将堆顶元素向下调整，直到调整到成堆

堆排序的时间复杂度是O(N*logN)。

//堆排序
void HeapSort(int* a, int n)
{
    //建堆：排升序建大堆，排降序建小堆
    //倒着调整，从最后一个非叶子结点开始向下调整建堆 效率O(N)
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, i, n);
    }
    //O(N*logN)
    int end = n - 1;//堆的有效长度
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, 0, end);
        end--;
    }
}

2. Top-K问题

Top-K问题：求集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

实现方法：

1. 用数据集合中前K个元素来建堆。

• 前k个最大的元素，则建小堆
• 前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素。比较完后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

void TopK(int* a, int n, int k)
{
    //用a中前k个元素建堆
    for (int i = (k - 2) / 2; i >= 0; i--)
        AdjustDown(a, i, k);
    for (int i = k; i < n; i++)
    {
        if (a[i] < a[0])
        {
            Swap(&a[i], &a[0]);//不满足则交换
            AdjustDown(a, 0, k);//向下调整
        }
    }
    for (int i = 0; i < k; i++)
        printf("%d ", a[i]);
}

堆的完整代码可以参考：https://gitee.com/ncu-ball/study/tree/master/24_4_19