当前位置：首页 > article >正文

【数据结构】堆（Heap）详解

article 2024/11/18 12:45:19

在深入了解堆这一重要的数据结构之前，不妨先回顾一下我之前的作品 ——“二叉树详解”。

上篇文章👉剖析二叉树（Binary Tree）

二叉树作为一种基础的数据结构，为我们理解堆以及其他更复杂的数据结构奠定了坚实的基础。它的结构特点、遍历方式以及在不同场景下的应用，都与堆有着千丝万缕的联系。通过对二叉树的深入学习，能更好地帮助我们掌握堆的相关知识。

一、引言

二、堆的基础概念

（一）完全二叉树与满二叉树

（二）堆的定义与性质

三、堆的操作

（一）堆的插入

（二）堆的删除

（三）最大堆

（四）最小堆

四、堆的应用

（一）堆排序

（二）优先队列

五、总结

一、引言

堆是计算机科学中一种非常重要的数据结构，它在众多算法和应用中发挥着关键作用。本文将深入探讨堆的相关概念、操作及其应用。

二、堆的基础概念

（一）完全二叉树与满二叉树

1.完全二叉树

若二叉树的深度为 $h$ ，则除第 $h$ 层外，其他层的结点全部达到最大值，且第 $h$ 层的所有结点都集中在左子树。

2.满二叉树

满二叉树是一种特殊的完全二叉树，所有层的结点都是最大值。

（二）堆的定义与性质

1.堆的定义

堆（英语：heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
$n$ 个元素的序列 $\left \{ k_{1},k_{2},k_{i},\cdot\cdot\cdot ,k_{n}\right \}$ 当且仅当满足下关系时，称之为堆：

堆分为大顶堆和小顶堆。在大顶堆中，父节点的值总是大于或等于子节点的值；在小顶堆中，父节点的值总是小于或等于子节点的值。

2.堆的性质

堆中某个节点的值总是不大于或不小于其父节点的值。

堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

注意：在二叉树中，若当前节点的下标为，则其父节点的下标为 $i/2$ ，其左子节点的下标为 $i*2$ ，其右子节点的下标为 $i*2+1$ 。

三、堆的操作

（一）堆的插入

1.插入过程

每次插入都是将先将新数据放在数组最后。由于从这个新数据的父结点到根结点必然为一个有序的序列，现在的任务是将这个新数据插入到这个有序序列中，类似于直接插入排序中将一个数据并入到有序区间中。
例如，将数字 $16$ 插入到堆中，堆的数组是 $\left [ 10,7,2,5,1\right ]$
第一步是将新的元素插入到数组的尾部，数组变成，相应的树变成了： $\left [ 10,7,2,5,1,16 \right ]$

       10
       7  2
       5 1 16

此时堆属性不满足，因为 $2$ 在的 $16$ 上面（这是一个最大堆），需要交换和。得到：

       10
       7 16
       5 1 2

现在还未完成，因为 $10$ 也比 $16$ 小。继续交换插入元素和它的父节点，直到父节点比它大或者到达树的顶部。这就是所谓的 shift-up，每一次插入操作后都需要进行，它将一个太大或者太小的数字 “浮起” 到树的顶部。
最后得到的堆：

       16
       7 10
       5 1 2

插入操作的 C 语言代码示例

void insertHeap(int heap[], int *size, int value) {
    heap[*size] = value;
    int index = *size;//将孩子标为index
    (*size)++;
    while (index > 0) //将孩子调整到正确位置
    {
        int parentIndex = (index - 1) / 2;
        if (heap[index] > heap[parentIndex]) //如果孩子比父亲大，则交换
        {
            int temp = heap[index];
            heap[index] = heap[parentIndex];
            heap[parentIndex] = temp;
            index = parentIndex;//再次与其父亲比较直到break
        }
         else break;//孩子比父亲小则退出
    }
}

（二）堆的删除

1.删除过程

堆中每次都只能删除堆顶元素。为了便于重建堆，实际的操作是1.将最后一个数据的值赋给根结点，2.然后再从根结点开始进行一次从上向下的调整。3.调整时先在左右子结点中找最小的（对于最大堆），如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于根结点数据的 “下沉” 过程。
例如，删除树中的：
       16
       7 10
       5 1 2
顶部有一个空的节点，取出数组中的最后一个元素 $1$ ，将它放到树的顶部。
然后进行 shift-down 操作。为了保持最大堆的堆属性，需要树的顶部是最大的数据。现在有两个数字 $7$ 和 $2$ 可用于交换，选择两者中的较大者 $7$ 放在树的顶部， $7$ 交换和 $1$ ，树变成了：

       7
       1  2
       5

继续堆化直到该节点没有任何子节点或者它比两个子节点都要大为止。对于这个堆，只需要再有一次交换就恢复了堆属性：

       7
       5  2

删除操作的 C 语言代码示例

int deleteHeap(int heap[], int *size) {
    if (*size == 0) {
        return -1;
    }
    int value = heap[0];
    heap[0] = heap[*size - 1];
    (*size)--;
    int index = 0;
    while (1) {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int largestIndex = index;
        if (leftChildIndex < *size && heap[leftChildIndex] > heap[largestIndex]) {
            largestIndex = leftChildIndex;
        }
        if (rightChildIndex < *size && heap[rightChildIndex] > heap[largestIndex]) {
            largestIndex = rightChildIndex;
        }
        if (largestIndex!= index) {
            int temp = heap[index];
            heap[index] = heap[largestIndex];
            heap[largestIndex] = temp;
            index = largestIndex;
        } else {
            break;
        }
    }
    return value;
}

（三）最大堆

1.构造最大堆

基本思想：首先将每个叶子节点视为一个堆，再将每个叶子节点与其父节点一起构造成一个包含更多节点的堆。所以，在构造堆的时候，首先需要找到最后一个节点的父节点，从这个节点开始构造最大堆；直到该节点前面所有分支节点都处理完毕，这样最大堆就构造完毕了。
假设树的节点个数为 $n$ ，以 $1$ 为下标开始编号，直到结束。对于节点 $i$ ，其父节点为 $i/2$ ；左孩子节点为 $i*2$ ，右孩子节点为 $i*2+1$ 。最后一个节点的下标为 $n$ ，其父节点的下标为 $n/2$ 。
例如，原始数据为 $a\left [ \right ]=\left \{ 4,1,3,2,16,9,10,14,8,7 \right \}$ ，采用顺序存储方式，对应的完全二叉树构建最大堆的过程如下：
首先，最后一个节点为 $7$ ，其父节点为 $16$ ，从 $16$ 这个节点开始构造最大堆。
构造完毕之后，转移到下一个父节点 $2$ ，直到所有父节点都构造完毕。
具体过程如下图所示（括号内为每次调整后的结果）

       4
       1 3 (3 1)
       2 16 9 10 (14 16 9 10)
       14 8 7 (2 8 7)
       (a)       (b)
       4
       1 10 (10 1)
       14 16 9 3 (14 16 9 3)
       2 8 7 (2 8 7)
       (c)       (d)
       16
       14 10
       8 7 9 3
       2 4 1
       (e) 堆的初始化步骤

代码实现：

struct MaxHeap {
    Etype *heap; //数据元素存放的空间，下标从1开始存数数据，下标为0的作为工作空间，存储临时数据
    int HeapSize; //数据元素的个数
    int MaxSize; //存放数据元素空间的大小
};
MaxHeap H;

void MaxHeapInit(MaxHeap &H) {
    for (int i = H.HeapSize / 2; i >= 1; i--) {
        H.heap[0] = H.heap[i];
        int son = i * 2;
        while (son <= H.HeapSize) {
            if (son < H.HeapSize && H.heap[son] < H.heap[son + 1])
                son++;
            if (H.heap[0] >= H.heap[son])
                break;
            else {
                H.heap[son / 2] = H.heap[son];
                son *= 2;
            }
        }
        H.heap[son / 2] = H.heap[0];
    }
}

2.最大堆插入节点

思想：先在堆的最后添加一个节点，然后沿着堆树上升。跟最大堆的初始化过程大致相同。

代码实现：

void MaxHeapInsert(MaxHeap &H, EType &x) {
    if (H.HeapSize == H.MaxSize)
        return false;
    int i = ++H.HeapSize;
    while (i!= 1 && x > H.heap[i / 2]) {
        H.heap[i] = H.heap[i / 2];
        i = i / 2;
    }
    H.heap[i] = x;
    return true;
}

3.最大堆堆顶节点删除

思想：将堆树的最后的节点提到根结点，然后删除最大值，然后再把新的根节点放到合适的位置。

代码实现：

void MaxHeapDelete(MaxHeap &H, EType &x) {
    if (H.HeapSize == 0)
        return false;
    x = H.heap[1];
    H.heap[0] = H.heap[H.HeapSize--];
    int i = 1, son = i * 2;

    while (son <= H.HeapSize) {
        if (son <= H.HeapSize && H.heap[0] < H.heap[son + 1])
            son++;
        if (H.heap[0] >= H.heap[son])
            break;
        H.heap[i] = H.heap[son];
        i = son;
        son = son * 2;
    }
    H.heap[i] = H.heap[0];
    return true;
}

（四）最小堆

整体操作和最大堆类似，主要区别在于比较大小的规则相反。在最小堆中，每个节点的值都不大于其子节点的值。插入和删除操作时，调整堆的方向也与最大堆相反，以保持最小堆的性质。

四、堆的应用

（一）堆排序

1.原理

堆排序利用了堆（通常是最大堆或最小堆）的特性来实现排序。对于最大堆，每次可以取出堆顶元素（即当前堆中的最大值），然后将堆的最后一个元素放到堆顶，再进行调整使堆保持最大堆性质。重复这个过程，就可以得到一个有序的序列。

2.示例

例如，对数组进行堆排序。首先根据该数组元素构建一个完全二叉树，具体过程如下（从左到右，从上到下按顺序一步一步的详细过程）：

初始完全二叉树：

构建最大堆过程：

       16 16 20
       7 8 20 8 16 8
       20 17 3 7

       3
       17 8
       16 20
       17
       3 8
       7 16 20
       17 3 16
       16 8 16 8 3 8
       7 3 7 20 7
       16 3 8
       7 8 7 8 7 3
       3 20 16
       3 7 3
       7 8 3 9 8
       1 17 20 16 16

然后进行堆排序，每次取出堆顶元素（最大值），与数组末尾元素交换，再对剩余元素进行调整，重复这个过程，最终得到有序数组。
相关参考文章：我的十大经典排序算法 (C++、Java 实现) 动图演示及代码解析 - 冒泡排序、选择排序、插入排序、快速排序、堆排序、希尔排序、归并排序、计数排序、桶排序、基数排序

有各个经典排序算法的动图介绍和源码，可以参考。

（二）优先队列

堆可以用于实现优先队列。在优先队列中，元素按照优先级进行排序。最大堆可以用于实现最大优先队列，每次取出的元素是优先级最高（值最大）的元素；最小堆可以用于实现最小优先队列，每次取出的元素是优先级最高（值最小）的元素。插入和删除元素时，堆的操作可以保证优先队列的性质始终满足。

五、总结

堆是一种非常重要的数据结构，具有独特的性质和高效的操作。它在堆排序、优先队列等算法和应用中有着广泛的应用。通过对堆的深入理解和掌握，我们可以更好地设计和实现高效的算法，解决各种实际问题。在未来的计算机科学领域，堆的应用可能会随着技术的发展而更加广泛，例如在大数据处理、实时系统等方面发挥更大的作用。同时，对于堆的研究和优化也将不断深入，以提高其性能和适用性。希望大家在学习堆的过程中，能充分体会到它的魅力和价值。

如果在阅读过程中有任何疑问或建议，欢迎随时交流。

💝💝💝感谢你看到最后，点个赞再走吧！💝💝💝

以下是一个投票，欢迎你参与：

查看全文

http://www.kler.cn/a/322864.html