安全的响应式网站建设,网站建建设心的,wordpress the terms,成都网站建设网站制作在深入了解堆这一重要的数据结构之前#xff0c;不妨先回顾一下我之前的作品 ——“二叉树详解”。 上篇文章#x1f449;剖析二叉树#xff08;Binary Tree#xff09; 二叉树作为一种基础的数据结构#xff0c;为我们理解堆以及其他更复杂的数据结构奠定了坚实的基础。它… 在深入了解堆这一重要的数据结构之前不妨先回顾一下我之前的作品 ——“二叉树详解”。 上篇文章剖析二叉树Binary Tree 二叉树作为一种基础的数据结构为我们理解堆以及其他更复杂的数据结构奠定了坚实的基础。它的结构特点、遍历方式以及在不同场景下的应用都与堆有着千丝万缕的联系。通过对二叉树的深入学习能更好地帮助我们掌握堆的相关知识。 目录
一、引言
二、堆的基础概念
一完全二叉树与满二叉树
二堆的定义与性质
三、堆的操作
一堆的插入
二堆的删除
三最大堆
四最小堆
四、堆的应用
一堆排序
二优先队列
五、总结 一、引言 堆是计算机科学中一种非常重要的数据结构它在众多算法和应用中发挥着关键作用。本文将深入探讨堆的相关概念、操作及其应用。
二、堆的基础概念 一完全二叉树与满二叉树 1.完全二叉树
若二叉树的深度为 则除第 层外其他层的结点全部达到最大值且第 层的所有结点都集中在左子树。 2.满二叉树
满二叉树是一种特殊的完全二叉树所有层的结点都是最大值。 二堆的定义与性质 1.堆的定义 堆英语heap是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。 个元素的序列 当且仅当满足下关系时称之为堆 堆分为大顶堆和小顶堆。在大顶堆中父节点的值总是大于或等于子节点的值在小顶堆中父节点的值总是小于或等于子节点的值。 2.堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值。 堆总是一棵完全二叉树。 将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。 注意在二叉树中若当前节点的下标为则其父节点的下标为其左子节点的下标为其右子节点的下标为。 三、堆的操作 一堆的插入 1.插入过程 每次插入都是将先将新数据放在数组最后。由于从这个新数据的父结点到根结点必然为一个有序的序列现在的任务是将这个新数据插入到这个有序序列中类似于直接插入排序中将一个数据并入到有序区间中。例如将数字插入到堆中堆的数组是 第一步是将新的元素插入到数组的尾部数组变成相应的树变成了 107 25 1 16
此时堆属性不满足因为在的上面这是一个最大堆需要交换和。得到 107 165 1 2 现在还未完成因为 也比 小。继续交换插入元素和它的父节点直到父节点比它大或者到达树的顶部。这就是所谓的 shift-up每一次插入操作后都需要进行它将一个太大或者太小的数字 “浮起” 到树的顶部。最后得到的堆 167 105 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.调整时先在左右子结点中找最小的对于最大堆如果父结点比这个最小的子结点还小说明不需要调整了反之将父结点和它交换后再考虑后面的结点。相当于根结点数据的 “下沉” 过程。例如删除树中的 167 105 1 2 顶部有一个空的节点取出数组中的最后一个元素 将它放到树的顶部。然后进行 shift-down 操作。为了保持最大堆的堆属性需要树的顶部是最大的数据。现在有两个数字 和 可用于交换选择两者中的较大者放在树的顶部 交换和 树变成了 71 25 继续堆化直到该节点没有任何子节点或者它比两个子节点都要大为止。对于这个堆只需要再有一次交换就恢复了堆属性 75 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.构造最大堆 基本思想首先将每个叶子节点视为一个堆再将每个叶子节点与其父节点一起构造成一个包含更多节点的堆。所以在构造堆的时候首先需要找到最后一个节点的父节点从这个节点开始构造最大堆直到该节点前面所有分支节点都处理完毕这样最大堆就构造完毕了。假设树的节点个数为以为下标开始编号直到结束。对于节点 其父节点为左孩子节点为右孩子节点为。最后一个节点的下标为其父节点的下标为。例如原始数据为采用顺序存储方式对应的完全二叉树构建最大堆的过程如下 首先最后一个节点为其父节点为从这个节点开始构造最大堆。构造完毕之后转移到下一个父节点直到所有父节点都构造完毕。具体过程如下图所示括号内为每次调整后的结果 41 3 (3 1)2 16 9 10 (14 16 9 10)14 8 7 (2 8 7)(a) (b)41 10 (10 1)14 16 9 3 (14 16 9 3)2 8 7 (2 8 7)(c) (d)1614 108 7 9 32 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.示例 例如对数组进行堆排序。首先根据该数组元素构建一个完全二叉树具体过程如下从左到右从上到下按顺序一步一步的详细过程 初始完全二叉树 167320178
构建最大堆过程 16 16 207 8 20 8 16 820 17 3 7 201787163 317 816 20173 87 16 2017 3 1616 8 16 8 3 87 3 7 20 716 3 87 8 7 8 7 33 20 163 7 37 8 3 9 81 17 20 16 16 然后进行堆排序每次取出堆顶元素最大值与数组末尾元素交换再对剩余元素进行调整重复这个过程最终得到有序数组。 相关参考文章我的十大经典排序算法 (C、Java 实现) 动图演示及代码解析 - 冒泡排序、选择排序、插入排序、快速排序、堆排序、希尔排序、归并排序、计数排序、桶排序、基数排序 有各个经典排序算法的动图介绍和源码可以参考。 二优先队列 堆可以用于实现优先队列。在优先队列中元素按照优先级进行排序。最大堆可以用于实现最大优先队列每次取出的元素是优先级最高值最大的元素最小堆可以用于实现最小优先队列每次取出的元素是优先级最高值最小的元素。插入和删除元素时堆的操作可以保证优先队列的性质始终满足。 五、总结 堆是一种非常重要的数据结构具有独特的性质和高效的操作。它在堆排序、优先队列等算法和应用中有着广泛的应用。通过对堆的深入理解和掌握我们可以更好地设计和实现高效的算法解决各种实际问题。在未来的计算机科学领域堆的应用可能会随着技术的发展而更加广泛例如在大数据处理、实时系统等方面发挥更大的作用。同时对于堆的研究和优化也将不断深入以提高其性能和适用性。希望大家在学习堆的过程中能充分体会到它的魅力和价值。 如果在阅读过程中有任何疑问或建议欢迎随时交流。 感谢你看到最后点个赞再走吧
以下是一个投票欢迎你参与
