数据结构之堆：原理与排序应用

20XX/XX/XX数据结构之堆：原理与排序应用汇报人:XXXCONTENTS目录01

堆的基本概念与性质02

堆的存储结构与节点关系03

堆的核心操作算法04

堆的构建与时间复杂度05

堆排序算法06

Top-K问题的堆应用01堆的基本概念与性质堆的本质定义堆是一种特殊的完全二叉树，其所有元素按完全二叉树的顺序存储方式存于一维数组中，且满足每个节点的值大于等于（大根堆）或小于等于（小根堆）其左右子节点的值。堆的结构特性堆是一棵完全二叉树，除最后一层外，其他层节点均满，最后一层节点从左向右连续排列。堆的数值特性大根堆中每个父节点的值大于等于子节点，根节点为最大值；小根堆中每个父节点的值小于等于子节点，根节点为最小值。堆的定义与核心特性大根堆与小根堆的结构对比大根堆的定义与结构特征大根堆是指每个父节点的值大于或等于其左、右子节点的值，根节点为整个堆的最大值。例如数组[90,85,75,70,65,50,45]可表示为大根堆，根节点90为最大值。小根堆的定义与结构特征小根堆是指每个父节点的值小于或等于其左、右子节点的值，根节点为整个堆的最小值。例如数组[16,14,10,8,7,9,3]可表示为小根堆，根节点16为最小值。结构对比与核心差异大根堆强调父节点大于子节点，适用于需要频繁获取最大值的场景；小根堆则相反，适用于频繁获取最小值的场景。两者均为完全二叉树，区别仅在于父子节点间的大小关系约束。堆与完全二叉树的关系堆的结构本质堆在逻辑上是一种特殊的完全二叉树，它满足完全二叉树的结构特性：除最后一层外，其他层节点均被填满，且最后一层节点从左向右依次排列。堆的堆序性要求在完全二叉树的基础上，堆还需满足堆序性：大根堆中每个节点的值大于等于其子节点的值；小根堆中每个节点的值小于等于其子节点的值。完全二叉树的存储优势由于堆是完全二叉树，可通过数组高效存储，利用节点下标计算父子关系：父节点下标为(i-1)/2，左子节点为2i+1，右子节点为2i+2，无需额外存储指针。堆与其他数据结构的区别堆与二叉搜索树的区别堆是完全二叉树，仅保证父节点与子节点的大小关系（堆序性），整体无序；二叉搜索树要求左子树所有节点值小于根节点，右子树所有节点值大于根节点，中序遍历有序。堆的插入和删除时间复杂度为O(logn)，二叉搜索树在平衡状态下同样为O(logn)，但堆更适合高效获取最值。堆与栈的区别堆（数据结构）是基于完全二叉树的有序结构，用于高效管理最值元素；栈是线性结构，遵循后进先出（LIFO）原则。堆的操作主要是插入、删除堆顶元素，栈的操作是入栈和出栈。两者在逻辑结构、核心特性和应用场景上截然不同。堆与优先队列的关系优先队列是一种抽象数据类型，要求每次出队的是优先级最高的元素；堆是实现优先队列的常用数据结构，通过堆的插入（上浮调整）和删除（下沉调整）操作，可高效实现优先队列的功能，时间复杂度均为O(logn)。02堆的存储结构与节点关系数组存储堆的原理

01数组存储的逻辑映射堆作为完全二叉树，通过层序遍历顺序存储于一维数组中。数组下标与树节点存在严格映射关系：根节点对应下标0，左子节点为2i+1，右子节点为2i+2，父节点为(i-1)/2（向下取整）。

02索引计算规则对于数组中任意节点i（从0开始）：左子节点索引=2i+1，右子节点索引=2i+2，父节点索引=(i-1)//2。该规则确保无需指针即可快速定位父子节点，空间效率达100%。

03存储优势完全二叉树的特性避免数组空间浪费，支持随机访问（时间复杂度O(1)），且缓存友好。相比链式存储，数组存储减少指针开销，简化堆调整算法实现。父节点与子节点的索引计算

父节点索引计算公式对于数组中索引为i的节点，其父节点的索引为：parent(i)=(i-1)/2（向下取整）。该公式适用于堆的任何非根节点。

左子节点索引计算公式对于数组中索引为i的节点，其左子节点的索引为：leftChild(i)=2*i+1。若计算结果超出数组长度，则表示该节点无左子节点。

右子节点索引计算公式对于数组中索引为i的节点，其右子节点的索引为：rightChild(i)=2*i+2。若计算结果超出数组长度，则表示该节点无右子节点。

索引计算示例以数组索引为3的节点为例：父节点索引=(3-1)/2=1，左子节点索引=2*3+1=7，右子节点索引=2*3+2=8。通过公式可快速定位任意节点的亲属节点位置。堆结构体的核心组成堆的结构体通常包含三个关键成员：存储数据的动态数组指针（HPDataType*a）、当前元素个数（intsize）、数组容量（intcapacity）。C语言结构体定义示例typedefintHPDataType;typedefstructHeap{HPDataType*a;intsize;intcapacity;}Heap;成员变量的作用动态数组指针（a）用于存储堆的元素；size记录当前有效元素数量；capacity表示数组的最大存储容量，支持动态扩容。堆的结构体定义03堆的核心操作算法向上调整算法（小堆）算法适用场景

当堆的尾部插入新元素后，需通过向上调整恢复小堆性质。要求除插入元素外，原堆结构已满足小堆条件。核心调整逻辑

从新插入元素（初始为堆尾）开始，与父节点比较：若子节点值小于父节点，则交换两者位置；重复此过程直至父节点值小于等于子节点或到达根节点。关键步骤与公式

1.子节点下标child，父节点下标parent=(child-1)/2（向下取整）；2.比较a[child]与a[parent]，若a[child]<a[parent]则交换；3.更新child=parent，重复上述步骤直至child=0或满足堆性质。C语言实现示例

voidAdjustUp(HPDataType*a,intchild){intparent=(child-1)/2;while(child>0){if(a[child]<a[parent]){Swap(&a[child],&a[parent]);child=parent;parent=(child-1)/2;}elsebreak;}}算法适用场景用于堆的插入操作，当新元素添加到堆尾后，通过向上调整使其满足大堆性质（父节点值≥子节点值）。核心操作步骤1.新元素插入堆尾；2.计算当前节点父节点索引（parent=(child-1)/2）；3.若当前节点值>父节点值，交换两者位置；4.重复步骤2-3，直至当前节点≤父节点或到达堆顶。C语言实现代码voidAdjustUp(HPDataType*a,intchild){intparent=(child-1)/2;while(child>0){if(a[child]>a[parent]){Swap(&a[child],&a[parent]);child=parent;parent=(child-1)/2;}elsebreak;}}时间复杂度分析最坏情况下需调整至堆顶，时间复杂度为O(logn)，其中n为堆中元素个数。向上调整算法（大堆）向下调整算法（小堆）

算法核心原理当堆顶元素不满足小堆性质时，通过将其与左右子节点中较小值交换，逐步下沉至合适位置，使堆重新满足父节点值≤子节点值的特性。

前置条件待调整节点的左子树和右子树必须已满足小堆性质，仅当前节点可能违反堆序性。

操作步骤1.计算当前节点（parent）的左子节点（2*parent+1）和右子节点（2*parent+2）索引；2.比较左右子节点值，选择较小子节点（child）；3.若parent值>child值，交换两者并以child为新parent继续调整；4.直至节点无孩子或满足小堆性质时停止。

C语言实现示例voidAdjustDown(HPDataType*a,intn,intparent){intchild=2*parent+1;while(child<n){if(child+1<n&&a[child]>a[child+1])child++;if(a[parent]>a[child]){Swap(&a[parent],&a[child]);parent=child;child=2*parent+1;}elsebreak;}}向下调整算法（大堆）01算法核心思想针对大堆结构，当堆顶元素被替换后，通过将当前节点与左右子节点中较大值进行比较交换，使节点逐步下沉至合适位置，恢复堆的性质。02操作步骤1.从目标节点（通常为堆顶）开始，计算左子节点（2i+1）和右子节点（2i+2）索引；2.比较左右子节点大小，选择较大子节点；3.若当前节点值小于较大子节点值，则交换两者位置；4.以交换后的子节点为新起点，重复上述步骤直至节点无子节点或满足堆性质。03前提条件执行向下调整算法的大堆，其左右子树必须已满足大堆的性质，即每个父节点的值大于等于其子节点的值。04C语言实现示例voidAdjustDown(HPDataType*a,intn,intparent){intchild=parent*2+1;while(child<n){if(child+1<n&&a[child]<a[child+1])child++;if(a[parent]<a[child]){Swap(&a[parent],&a[child]);parent=child;child=parent*2+1;}elsebreak;}}堆的插入操作实现

01插入操作基本步骤堆的插入操作分为三步：首先检查堆的容量，若不足则进行扩容；然后将新元素添加到堆的末尾（数组的最后一个位置）；最后通过向上调整算法使堆重新满足堆序性。

02容量检查与扩容策略在插入新元素前，需判断当前堆的元素个数是否等于容量。若相等，通常采用翻倍扩容策略（如初始容量为4，扩容后为8），使用realloc函数重新分配内存空间，确保有足够空间存储新元素。

03向上调整算法（小堆示例）从新插入元素（child）开始，计算其父节点（parent=(child-1)/2）。若child小于parent，交换两者位置，并更新child为parent，重复上述过程直至child大于等于parent或到达根节点（child=0）。

04插入操作时间复杂度插入操作的时间复杂度主要由向上调整算法决定，最坏情况下需调整堆的高度次，即O(logn)，其中n为堆中元素个数。删除操作核心目标堆的删除操作特指删除堆顶元素（大堆为最大值，小堆为最小值），需在删除后保持堆的结构特性与堆序性。删除操作步骤1.交换堆顶元素与堆尾元素；2.移除堆尾元素（原堆顶）；3.对新堆顶执行向下调整算法，恢复堆序性。向下调整算法前提条件执行向下调整需满足：当前节点的左右子树均为有效堆（大堆/小堆），通过比较父节点与子节点值，交换后继续下沉直至满足堆性质。删除操作时间复杂度删除操作的时间复杂度为O(logn)，其中n为堆中元素个数，主要由向下调整算法决定（调整次数不超过堆的高度log₂n）。堆的删除操作实现堆的初始化与销毁

堆的初始化操作堆的初始化是创建一个空堆的过程，需将堆结构体中的数组指针设为NULL，元素个数(size)和容量(capacity)均初始化为0，为后续堆操作做好准备。

初始化函数实现要点在C语言中，通常通过函数对堆结构体进行初始化，例如：voidHeapInit(Heap*php)，需确保传入的堆指针有效，避免空指针操作。

堆的销毁操作堆的销毁用于释放堆所占用的内存资源，包括释放动态分配的数组空间，将数组指针置为NULL，并将size和capacity重置为0，防止内存泄漏。

销毁函数实现要点销毁函数需先判断堆数组是否为空，若不为空则使用free函数释放内存，例如：voidHeapDestroy(Heap*php)，确保堆结构体指针有效是操作的前提。堆的判空与数据个数获取

堆的判空操作堆的判空操作用于检查堆中是否包含元素。通过判断堆的size属性是否为0来实现，若size为0则堆为空，否则不为空。

堆的判空实现代码在C语言中，可通过函数boolHPEmpty(Heap*php)实现，返回php->size==0的结果。

堆的数据个数获取堆的数据个数即堆中当前元素的数量，通过直接访问堆的size属性即可获取，该属性记录了堆中有效元素的个数。

堆数据个数获取实现代码在C语言中，可通过函数intHeapSize(Heap*php)实现，直接返回php->size的值。04堆的构建与时间复杂度核心思想从最后一个非叶子节点开始，自下而上对每个节点执行向下调整操作，将无序数组转换为堆结构。操作步骤1.确定最后一个非叶子节点：索引为(n//2)-1（n为数组长度）；2.从该节点开始，向左依次对每个节点执行向下调整；3.调整过程中确保当前节点与其子树满足堆序性。时间复杂度建堆过程时间复杂度为O(n)，优于逐个插入元素的O(nlogn)，适用于大规模数据的堆初始化。示例说明对数组[3,4,5,6,1,7,8]，从索引2（值5）开始向下调整，依次处理索引1（值4）、索引0（值3），最终构建大根堆。自底向上建堆法自顶向下建堆法自顶向下建堆法的定义自顶向下建堆法是指从堆顶开始，对每个节点执行向下调整操作，使得堆的性质保持不变的建堆方式。自顶向下建堆法的步骤从根节点开始，对每个节点执行向下调整操作，将节点与其左右子节点中符合堆性质（大堆选较大子节点，小堆选较小子节点）的子节点比较，若不满足堆性质则交换，重复此过程直至满足堆性质或到达叶子节点。自顶向下建堆法的时间复杂度自顶向下建堆法的时间复杂度为O(nlogn)，其中n为堆中元素的个数。建堆的时间复杂度分析

自底向上建堆法从最后一个非叶子节点开始，从下到上对每个节点执行向下调整。最后一个非叶子节点下标为(n//2)-1，其中n为数组长度。

时间复杂度推导设堆的高度为h，各层节点数为2⁰,2¹,...,2ʰ⁻¹。第i层节点最多需要调整(h-i)次，总调整次数T(n)=Σ(2ⁱ·(h-i))，经推导得T(n)=O(n)。

与自顶向下建堆对比自顶向下建堆（逐个插入元素）时间复杂度为O(nlogn)，而自底向上建堆为O(n)，后者效率更高，适合直接将无序数组转化为堆。05堆排序算法堆排序的基本原理

堆排序的核心思想堆排序是基于堆数据结构的排序算法，通过构建大根堆或小根堆，反复提取堆顶元素并调整堆结构，最终实现数组的有序排列。

堆排序的基本步骤堆排序分为两大阶段：首先将无序数组构建为大根堆（升序排序）或小根堆（降序排序）；然后通过交换堆顶与末尾元素、删除堆顶并调整堆结构，逐步将元素按序排列。

堆排序的时间复杂度堆排序的时间复杂度为O(nlogn)，其中建堆过程时间复杂度为O(n)，每次调整堆的时间复杂度为O(logn)，整体排序过程需执行n次调整操作。构建大根堆从最后一个非叶子节点开始，从下往上对每个节点执行向下调整操作，将无序数组转换为大根堆。最后一个非叶子节点的索引为(n//2)-1（n为数组长度）。交换堆顶与末尾元素将大根堆的堆顶元素（最大值）与数组末尾元素交换，此时末尾元素为已排序的最大值。调整剩余元素为大根堆对交换后前n-1个元素（排除已排序的末尾元素），从堆顶开始执行向下调整操作，重新构建大根堆。重复操作直至排序完成重复执行交换堆顶与当前末尾元素、调整剩余元素为大根堆的步骤，直至所有元素排序完成。最终数组将按升序排列。基于大根堆的排序步骤基于小根堆的排序步骤构建小根堆将待排序数组转换为小根堆，使根节点为最小值。从最后一个非叶子节点开始，自下而上执行向下调整操作，确保每个父节点的值小于等于其子节点的值。提取堆顶元素将堆顶元素（最小值）与数组末尾元素交换，此时末尾元素为已排序的最小值。然后删除末尾元素（原堆顶），堆的大小减1。调整剩余元素为小根堆对新的堆顶元素执行向下调整操作，使剩余元素重新满足小根堆性质。重复提取堆顶和调整堆的过程，直至堆中元素全部处理完毕。逆序输出排序结果由于每次提取的最小值按顺序存放在数组末尾，最终数组呈现降序排列。若需升序，可构建大根堆并按相同步骤操作。堆排序的时间复杂度建堆过程的时间复杂度堆排序中建堆操作的时间复杂度为O(n)，通过从最后一个非叶子节点开始自底向上进行向下调整实现，整体效率优于逐个插入元素的O(nlogn)方式。排序阶段的时间复杂度排序阶段需执行n-1次堆顶元素提取与调整操作，每次调整的时间复杂度为O(logn)，因此排序阶段的时间复杂度为O(nlogn)。堆排序整体时间复杂度堆排序的整体时间复杂度为O(nlogn)，其中n为待排序元素的个数，该复杂度不受数据初始状态影响，最坏、平均与最好情况一致。堆排序的稳定性分析

稳定性的定义排序算法稳定性指相同关键字元素在排序前后的相对位置是否保持不变。若相同元素相对位置不变则稳定，否则不稳定。

堆排序的不稳定性表现堆排序过程中，通过交换堆顶与末尾元素、下沉调整等操作，可能导致相同元素的相对位置发生改变。例如，序列[5,3,5]建堆后交换调整时，两个5的顺序可能反转。

不稳定性的根本原因堆排序依赖堆结构的调整，当多个相同元素分布在不同子树时，下沉或上浮操作可能破坏其原有顺序，且无法通过简单改进消除这种特性。

与其他排序算法的对比堆排序（不稳定）与冒泡排序、插入排序（稳定）相比，在处理含相同元素序列时，无法保证相对顺序；但堆排序时间复杂度为O(nlogn)，适用于大规模数据排序。06Top-K问题