烟台网站设计,韩国小清新网站模板,公众号开发实践 pdf,首饰设计网站推荐堆#xff1a;
定义#xff1a;
必须是一个完全二叉树#xff08;完全二叉树#xff1a;完全二叉树只允许最后一行不为满#xff0c;且最后一行必须从左往右排序#xff0c;最后一行元素之间不可以有间隔#xff09; 堆序性#xff1a;
大根堆#xff1a;每个父节点…堆
定义
必须是一个完全二叉树完全二叉树完全二叉树只允许最后一行不为满且最后一行必须从左往右排序最后一行元素之间不可以有间隔 堆序性
大根堆每个父节点元素都要大于子节点元素 小根堆每个父节点元素都要小于子节点元素 堆的存储
首先按照层序遍历的顺序来给结点编号从上到下从左到右把这些编号对应到一个数组的下标把相应的元素存入数组中二叉树的序号和结点有着相应的规律之前有讲
堆的基本操作
下滤将根点与其最大子节点进行比较如果小于其最大子节点则进行交换持续比较交换直到该元素大于其子节点为止或者移动到底部为止主要用于新元素的加入复杂度O(logN可以重新构建成堆
上滤将最后一个节点与父节点进行比较如果大于其父节点则进行交换直到无法上移为止
自顶向下建堆法将新元素放到堆的最后一位然后对其进行上滤操作直到所有元素插入后完成建堆时间复杂度为O(N logN)
自下而上建堆法将元素先调整成堆然后再对父节点进行下滤操作直到根结点操作完毕这种建堆方法的时间复杂度为O(N)
优先队列
弹出最小元素的队列可以用小根堆来实现因为小根堆的根结点本来就是最小元素所以直接弹出根结点即可完成弹出操作将最后一个元素放到根结点进行下滤操作即可插入直接上滤即可
堆排序
将大根堆结点按层序遍历不断弹出即为正序
反之为倒叙
过程
1.建堆以大根堆为例倒着检查第一个非叶结点即n/2是否大于其左右结点否则与左右节点中较大的数进行交换并不断向下进行比较直到大于等于其左右结点或者已经到叶结点了
2.排序不断检查更新最后的数然后将放好的数隐藏掉
