博物馆建设网站的目的及功能,网站建设 零基础,网站制作在哪找,中国工程预算网今天我们将学习新的数据结构-堆。 01定义
堆是一种特殊的二叉树#xff0c;并且满足以下两个特性#xff1a;
#xff08;1#xff09;堆是一棵完全二叉树#xff1b;
#xff08;2#xff09;堆中任意一个节点元素值都小于等于#xff08;或大于等于#xff09;左…今天我们将学习新的数据结构-堆。 01定义
堆是一种特殊的二叉树并且满足以下两个特性
1堆是一棵完全二叉树
2堆中任意一个节点元素值都小于等于或大于等于左右子树中所有节点元素值
小根堆根节点元素永远是最小值即堆中每个节点元素值都小于等于左右子树中所有节点元素值
大根堆根节点元素永远是最大值即堆中每个节点元素值都大于等于左右子树中所有节点元素值 根据堆的定义我们不难发现堆特别适合用来求集合最值以及求最值引申的问题比如排序、优先队列、动态排名等等
02结构
我们指定堆是一种特殊完全二叉树因此堆的逻辑结构是树。
我们指定树的存储结构有两种顺序存储数组和链式存储链表那么堆的存储结构是什么呢
既然堆是完全二叉树那么树的存储结构当然也适用于堆。但是堆一般都选用顺序存储数组实现。其原因有三
1位置计算简单数组实现堆可以使用完全二叉树特性用简单的数学公式即可表示父子节点的索引关系从而避免了链表实现使用额外的指针即减少内存开销和实现复杂度
2性能好数组的连续内存特性使得其有高效的访问速度而链表因为节点不一定连续访问速度相对较差
3操作简单数组实现在逻辑实现上更加简单高效通过交换数组中的元素即可快速实现堆的性质链表实现在插入和删除操作中需要遍历链表效率远不如数组实现
总结一句话数组简单、内存连续、性能更好所以一般选用数组实现堆当然不一般的情况也可以使用链表实现。
03实现最小堆
下面我们就用数组来实现一个最小堆结构最大堆只是比较大小不同这里就不做过多赘述。
1、初始化 Init
首先我们需要定义两个私有变量一个变量用来存放堆元素的数组一个变量用来存放数组尾元素索引主要用来跟踪当前堆元素个数情况。
而初始化方法就是初始化两个变量创建指定容量数组以及标记数组尾元素索引为-1表示堆中还没有元素。
//存放堆元素
private int[] _array;
//数组尾元素索引
private int _tailIndex;
//初始化堆为指定容量
public MyselfMinHeap Init(int capacity)
{//初始化指定长度数组用于存放堆元素_array new int[capacity];//初始化数组尾元素索引为-1表示空数组_tailIndex -1;//返回堆return this;
}2、获取堆容量 Capacity
堆容量指的是数组的固定空间即数组最多能容纳多少个元素直接返回数组长度即可。
//堆容量
public int Capacity
{get{return _array.Length;}
}3、获取堆元素数量 Count
堆元素数量指当前堆中一共有多少个元素我们可以通过私有字段数组尾元素索引值加1获得。
//堆元素数量
public int Count
{get{//数组尾元素索引加1即为堆元素数量return _tailIndex 1;}
}4、获取堆顶元素 Top
堆顶元素指树节点中的根节点也就是数组中的第一个元素。同时要注意判断数组是否为空为空报异常。
//获取堆顶元素即最小元素
public int Top
{get{if (IsEmpty()){//空堆不可以进行获取最小堆元素操作throw new InvalidOperationException(空堆);}return _array[0];}
}5、是否为空堆 IsEmpty
空堆即堆中还没有任何元素当数组尾元素索引为-1时表示空堆。
//检查堆是否为空
public bool IsEmpty()
{return _tailIndex -1;
}6、是否为满堆 IsFull
满堆即堆空间已满不能再添加新元素当数组尾元素索引等于数组容量减1时表示满堆。
//检查堆是否为满堆
public bool IsFull()
{//数组末尾元素索引等于数组容量减1表示满堆return _tailIndex _array.Length - 1;
}7、入堆 Push
入堆即向堆中新添加一个元素。
而入堆也涉及到一个问题就是如何保存每次添加完新元素后还保持着堆的特性。很显然我们也没办法做到直接把新元素直接插入到其正确的位置上因此我们可以梳理新添加一个元素的流程可能大致有以下几个步骤
1首先把新元素添加到堆的末尾
2然后调整堆使其满足堆的性质
3更新堆尾元素索引
而难点显然就在第二步如何调整数组使其满足堆的性质
我们先直接模拟把7654按顺序推入堆中看看如何实现。
1首先7入堆此时只有一个元素无需做任何操作而7就作为根节点
2然后6入堆此时已有两个元素因此需要保持堆的两个特性根节点永远是最小元素和堆是完全二叉树。由完全二叉树特性可得根节点左子节点索引为2011而右子节点索引为2022而此时6的索引为1所以6为左子节点又因6比7小所以根节点变为6 7变为根节点的左子节点 3然后5入堆此时已有3个元素所以5的索引为2而根节点右子节点索引为2*022所以5添加为根节点的右子节点。5比6小所以5和6交互位置 4然后4入堆此时已有4个元素所以4的索引为3而7节点左子节点索引为2*113所以4添加为7节点的左子节点。4比7小所以4和7交互位置 再次比较4和54比5小所以4和5交互位置 相信到这里大家已经看出一点规律了调整整个数组元素使其满足堆的性质的整个过程大致分为以下几个步骤
1从新元素开始向上比较其与父节点元素的值大小
2如果新元素值小于其父节点元素值则交互两者位置否则结束调整
3重复以上步骤直至处理到根节点。
代码实现如下
//入堆 向堆中添加一个元素
public void Push(int data)
{if (IsFull()){//满堆不可以进行入添加元素操作throw new InvalidOperationException(满堆);}//新元素索引var index _tailIndex 1;//在数组末尾添加新元素_array[index] data;//向上调整堆以保持堆的性质SiftUp(index);//尾元素索引向后前进1位_tailIndex;
}
//向上调整堆以保持堆的性质
private void SiftUp(int index)
{//一直调整到堆顶为止while (index 0){//计算父节点元素索引var parentIndex (index - 1) / 2;//如果当前元素大于等于其父节点元素则结束调整if (_array[index] _array[parentIndex]){break;}//否则交换两个元素(_array[parentIndex], _array[index]) (_array[index], _array[parentIndex]);//更新当前索引为父节点元素索引继续调整index parentIndex;}
}8、出堆 Pop
出堆即删除并返回堆顶元素堆中最小元素。
而出堆同样也涉及到和入堆同样的问题就是如何保存每次删除元素后还保持着堆的特性。
显然删除和添加元素情况还不一样。添加新元素后还是一棵完全二叉树只不过可能没有满足堆的性质所以需要调整。而删除就不一样了想象一下当我们把堆顶元素删除后回怎样根节点空了此时还能较完全二叉树吗显然不能。
如何处理呢直观的想法就是根节点空了就用其子节点补充上呗就这样从上到下一直填补直至最后的空落在了叶子节点那一层如果这个空位落到了叶子节点左侧而右侧还有值此时就表明堆不满足完全二叉树这一特性因此还需要把这个空位移到堆的末尾想象都头大。这显然不是一个好办法。
既然我们最后要把根节点删除后的这个空位移到堆的末尾何不直接把这个空位和堆的尾元素直接调换个位置呢然后再参考出堆中调整整个数组使其满足堆的性质。
我们梳理整个流程可能大致有以下几个步骤
1首先获取堆顶元素并暂存
2将堆尾元素赋值给堆顶元素并将堆尾元素置空
3然后调整堆使其满足堆性质
4更新数组尾元素索引并返回暂存的堆顶元素
而难点同样在第二步如何调整数组使其满足堆的性质入堆是新元素在堆尾所以是从下往上进行调整而出堆是堆顶元素需要调整是否可以从上往下进行调整呢
我们把87654按顺序推入堆中后把4推出堆中看看如何实现。
首先删除根节点4并把堆尾元素8放到根节点
为了保持堆特性找出根节点及其子节点中最小元素并与当前根节点8交互位置因为865所以5与8交互位置
然后8节点继续与其子节点进行比较因为87,所以7与8交互位置。 这一出堆过程我们可以总结为以下步骤
1从当前节点开始找到其子节点元素值
2比较当前节点元素值与其子节点元素值大小如果当前节点值最小则结束调整否则取值最小的与其交互
3重复以上步骤直至处理到叶子节点。
代码实现如下
//出堆 删除并返回堆中最小元素
public int Pop()
{if (IsEmpty()){//空堆不可以进行删除并返回堆中最小元素操作throw new InvalidOperationException(空堆);}//取出数组第一个元素即最小元素var min _array[0];//将数组末尾元素赋值给第一个元素_array[0] _array[_tailIndex];//将数组末尾元素设为默认值_array[_tailIndex] 0;//将数组末尾元素索引向前移动1位_tailIndex--;//向下调整堆以保持堆的性质SiftDown(0);//返回最小元素return min;
}
//向下调整堆以保持堆的性质
private void SiftDown(int index)
{while (index _tailIndex){//定义较小值索引变量用于存放比较当前元素及其左右子节点元素中最小元素var minIndex index;//计算右子节点索引var rightChildIndex 2 * index 2;//如果存在右子节点则比较其与当前元素保留值较小的索引if (rightChildIndex _tailIndex _array[rightChildIndex] _array[minIndex]){minIndex rightChildIndex;}//计算左子节点索引var leftChildIndex 2 * index 1;//如果存在左子节点则比较其与较小值元素保留值较小的索引if (leftChildIndex _tailIndex _array[leftChildIndex] _array[minIndex]){minIndex leftChildIndex;}//如果当前元素就是最小的则停止调整if (minIndex index){break;}//否则交换当前元素和较小元素(_array[minIndex], _array[index]) (_array[index], _array[minIndex]);//更新索引为较小值索引继续调整index minIndex;}
}9、堆化 Heapify
堆化即把一个无序数组堆化成小根堆。
可以通过调用出堆是用到的调整方法来完成。大家可以思考一下为什么不是堆尾元素开始调整为什么是从下往上调用向下调整方法调整
//堆化即把一个无序数组堆化成小根堆
public void Heapify(int[] array)
{if (array null || _array.Length array.Length){throw new InvalidOperationException(无效数组);}//将数组复制到堆中Array.Copy(array, _array, array.Length);//更新尾元素索引_tailIndex array.Length - 1;//从最后一个非叶子节点开始向下调整堆for (int i (array.Length / 2) - 1; i 0; i--){SiftDown(i);}
}注测试方法代码以及示例源码都已经上传至代码库有兴趣的可以看看。https://gitee.com/hugogoos/Planner
