关键词排名优化网站建设公司,重庆网站的建设,上海央企排名前十名,个人可以备案企业网站吗文章目录 目录
文章目录
前言
一 . 堆
二 . 堆的创建(以大根堆为例)
堆的向下调整(重难点) 堆的创建 堆的删除
向上调整
堆的插入
三 . 优先级队列
总结 前言 大家好,今天给大家讲解一下堆这个数据结构和它的实现 - 优先级队列 一 . 堆
堆#xff08;Heap#xff0…文章目录 目录
文章目录
前言
一 . 堆
二 . 堆的创建(以大根堆为例)
堆的向下调整(重难点) 堆的创建 堆的删除
向上调整
堆的插入
三 . 优先级队列
总结 前言 大家好,今天给大家讲解一下堆这个数据结构和它的实现 - 优先级队列 一 . 堆
堆Heap是一种基于完全二叉树的数据结构具有以下特点 完全二叉树堆是一种完全二叉树即除了最后一层外其他层的节点都是满的并且最后一层的节点都靠左排列。 堆序性堆中的每个节点都满足堆序性质即对于最大堆Max Heap父节点的值大于或等于其子节点的值对于最小堆Min Heap父节点的值小于或等于其子节点的值。
堆通常用数组来实现其中数组的索引表示节点在堆中的位置。对于一个节点在索引i的堆其左子节点在索引2i右子节点在索引2i1父节点在索引i/2。
堆常常被用来实现优先级队列因为它能够快速找到最大或最小的元素并且在插入和删除操作时保持堆序性质。
常见的堆有两种类型 最大堆大根堆父节点的值大于或等于其子节点的值。最大堆的根节点是堆中的最大元素。 最小堆小根堆父节点的值小于或等于其子节点的值。最小堆的根节点是堆中的最小元素。
堆的常见操作包括 插入Insertion将一个元素插入到堆中需要保持堆序性质。 删除根节点Delete Root删除堆中的根节点需要调整堆以保持堆序性质。 查找最大/最小元素Find Max/Min在最大堆中查找最大元素在最小堆中查找最小元素时间复杂度为O(1)。 堆排序Heap Sort利用堆的性质进行排序时间复杂度为O(nlogn)。 二 . 堆的创建(以大根堆为例)
初始化工作 public class BigHeap {int[] elem; // 用来记录堆中的元素int size;public BigHeap(int capacity) {elem new int[capacity];}//再初始化的时候默认给一个数组public void initHeap(int[] arr) {for (int i 0; i arr.length; i) {elem[i] arr[i];size;}}public boolean isFull() {return elem.length size;}public void swap(int i,int j){int temp elem[i];elem[i] elem[j];elem[j] temp;} } 堆的向下调整(重难点)
对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据如果将其创建成大根堆呢
父节点的值大于或等于其子节点的值。最大堆的根节点是堆中的最大元素。 根据层序遍历构建出的二叉树显然并不符合我们的要求,这个是时候我们就需要进行向下调整
在最大堆中向下调整的过程是将当前节点与其子节点中较大的节点进行比较如果当前节点小于其中较大的子节点就将它们交换位置。然后继续向下比较和交换直到当前节点不再小于其子节点或者已经到达叶子节点。
思考一下,这个时候我们应该从哪个节点进行调整?
我们通常是从最后一个非叶子节点开始向下调整直到根节点或者到达叶子节点为止。从最后一个非叶子节点开始向下调整的原因是只有非叶子节点才有子节点而叶子节点没有子节点所以没有必要对叶子节点进行向下调整操作。
最后一个非叶子节点的索引可以通过公式计算得到n/2-1其中n是堆中元素的数量。
步骤
1. 让parent标记需要调整的节点child标记parent的左孩子(注意parent如果有孩子一定先是有左孩子,因为是完全二叉树)
2. 如果parent的左孩子存在即:child len 进行以下操作直到parent的左孩子不存在
parent右孩子是否存在存在找到左右孩子中最大的孩子让child进行标记将parent与较大的孩子child比较如果
parent小大于较大的孩子child调整结束否则交换parent与较大的孩子child交换完成之后parent中小的元素向下移动可能导致子树不满足堆的性质因此需要继续向下调整即parent childchild parent*21; 然后继续2(上面的)。
图解
{ 27,15,19,18,28,34,65,49,25,37 }
len: 数组的长度
parent: 表示指向需要调整的节点指针
child: 表示指向孩子节点的指针
最后一个非叶子节点: 根据公式parent (child-1)/2 在这里child表示最后一个节点的索引
parent (len - 1 - 1)/2 4 我们应该从4索引开始进行向下调整 进行到这里左子树宣告调整完毕,开始进行右子树的调整 调整完毕!
代码实现 private void shiftDown(int parent, int len) {int child 2 * parent 1;// 对交换引起的堆结构的改变进行调整(如果改变就调整)while (child len) {// 找出左右孩子中最大的孩子,用child进行记录if (child 1 len elem[child] elem[child 1]) {child;}// 判断大小关系if (elem[child] elem[parent]) {swap(child,parent);// parent中大的元素往下移动可能会造成子树不满足堆的性质因此需要继续向下调整parent child;child 2 * parent 1;} else {// 左孩子为空,表示以最开始的parent为根的二叉树已经是大根堆结构break;}}} 堆的创建 public void createHeap() {// 找倒数第一个非叶子节点从该节点位置开始往前一直到根节点遇到一个节点应用向下调整for (int parent (size - 1 - 1) / 2; parent 0; parent--) {shiftDown(parent, size);}} 堆的删除
注意堆的删除一定删除的是堆顶元素。具体如下
1. 将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整 public int poll(){int temp elem[0];swap(0, size);size--;// 调整完之后需要进行先下调整,因为原来的最后一个元素变成了堆顶元素,不用想的肯定不满足大根堆的结构shiftDown(0, size);return temp;}
向上调整
在最大堆中向上调整的过程是将当前节点与其父节点进行比较如果当前节点大于其父节点就将它们交换位置。然后继续向上比较和交换直到当前节点不再大于其父节点或者已经到达根节点。 private void shiftUp(int child) {while (child ! 0) {int parent (child - 1) / 2;if (elem[parent] elem[child]) {swap(child,parent);child parent;} else {break;}}}
堆的插入
堆的插入总共需要两个步骤
1. 先将元素放入到底层空间中(注意空间不够时需要扩容)
2. 将最后新插入的节点向上调整直到满足堆的性质
小根堆中插入10 public void offer(int val) {if (isFull()) {this.elem Arrays.copyOf(this.elem, 2 * this.elem.length);}elem[size] val;shiftUp(size);size;} 总代码
public class BigHeap {int[] elem;int size;public BigHeap(int capacity) {elem new int[capacity];}public void initHeap(int[] arr) {for (int i 0; i arr.length; i) {elem[i] arr[i];size;}}public void createHeap() {for (int parent (size - 1 - 1) / 2; parent 0; parent--) {shiftDown(parent, size);}}public int poll(){int temp elem[0];swap(0, size);size--;// 调整完之后需要进行先下调整,因为原来的最后一个元素变成了堆顶元素,不用想的肯定不满足大根堆的结构shiftDown(0, size);return temp;}private void shiftDown(int parent, int len) {int child 2 * parent 1;// 对交换引起的堆结构的改变进行调整(如果改变就调整)while (child len) {// 找出左右孩子中最大的孩子,用child进行记录if (child 1 len elem[child] elem[child 1]) {child;}// 判断大小关系if (elem[child] elem[parent]) {swap(child,parent);// parent中大的元素往下移动可能会造成子树不满足堆的性质因此需要继续向下调整parent child;child 2 * parent 1;} else {// 左孩子为空,表示以最开始的parent为根的二叉树已经是大根堆结构break;}}}public void offer(int val) {if (isFull()) {this.elem Arrays.copyOf(this.elem, 2 * this.elem.length);}elem[size] val;shiftUp(size);size;}private void shiftUp(int child) {while (child ! 0) {int parent (child - 1) / 2;if (elem[parent] elem[child]) {swap(child,parent);child parent;} else {break;}}}public boolean isFull() {return elem.length size;}public void swap(int i,int j){int temp elem[i];elem[i] elem[j];elem[j] temp;}
} 三 . 优先级队列
前面介绍过队列队列是一种先进先出(FIFO)的数据结构但有些情况下操作的数据可能带有优先级一般出队 列时可能需要优先级高的元素先出队列该中场景下使用队列显然不合适比如在手机上玩游戏的时候如果有来电那么系统应该优先处理打进来的电话初中那会班主任排座位时可能会让成绩好的同学先挑座位。 在这种情况下数据结构应该提供两个最基本的操作一个是返回最高优先级对象一个是添加新的对象。这种数 据结构就是优先级队列(Priority Queue)。
优先级队列可以用于很多场景例如任务调度、进程调度、事件处理等。在任务调度中可以根据任务的优先级来决定先执行哪些任务在进程调度中可以根据进程的优先级来决定先执行哪些进程在事件处理中可以根据事件的优先级来决定先处理哪些事件。
在实际应用中优先级队列可以通过使用堆来实现因为堆具有良好的时间复杂度和空间复杂度。通过使用堆来实现优先级队列可以在log₂ n的时间复杂度内插入和删除元素以及在O(1)的时间复杂度内获取优先级最高的元素。 注意点:
1. 使用时必须导入PriorityQueue所在的包
2. PriorityQueue中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出 ClassCastException异常
3. 不能插入null对象否则会抛出NullPointerException
4. 没有容量限制可以插入任意多个元素其内部可以自动扩容
5. 插入和删除元素的时间复杂度为O(log₂ n)
6. PriorityQueue底层使用了堆数据结构
7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素
堆模拟实现优先级队列 class MyPriorityQueue {// 演示作用不再考虑扩容部分的代码private int[] array new int[100];private int size 0;public void offer(int e) {array[size] e;shiftUp(size - 1);}public int poll() {int oldValue array[0];array[0] array[size--];shiftDown((size-1-1)/2,size);return oldValue;}public int peek() {return array[0];}} 总结
这篇文章给大家重点讲解了堆的模拟实现还有其应用之一 优先级队列,大家好好理解,我们下一篇博客见。
