数据结构-优先级队列(堆)

文章目录

目录

文章目录

前言

一 . 堆

二 . 堆的创建(以大根堆为例)

堆的向下调整(重难点)

 堆的创建

 堆的删除

向上调整

堆的插入

三 . 优先级队列

总结

---

前言

大家好,今天给大家讲解一下堆这个数据结构和它的实现 - 优先级队列

---

一 . 堆

堆（Heap）是一种基于完全二叉树的数据结构，具有以下特点：

1. 完全二叉树：堆是一种完全二叉树，即除了最后一层外，其他层的节点都是满的，并且最后一层的节点都靠左排列。

2. 堆序性：堆中的每个节点都满足堆序性质，即对于最大堆（Max Heap），父节点的值大于或等于其子节点的值；对于最小堆（Min Heap），父节点的值小于或等于其子节点的值。

堆通常用数组来实现，其中数组的索引表示节点在堆中的位置。对于一个节点在索引i的堆，其左子节点在索引2i，右子节点在索引2i+1，父节点在索引i/2。

堆常常被用来实现优先级队列，因为它能够快速找到最大或最小的元素，并且在插入和删除操作时保持堆序性质。

常见的堆有两种类型：

1. 最大堆（大根堆）：父节点的值大于或等于其子节点的值。最大堆的根节点是堆中的最大元素。

2. 最小堆（小根堆）：父节点的值小于或等于其子节点的值。最小堆的根节点是堆中的最小元素。

堆的常见操作包括：

1. 插入（Insertion）：将一个元素插入到堆中，需要保持堆序性质。

2. 删除根节点（Delete Root）：删除堆中的根节点，需要调整堆以保持堆序性质。

3. 查找最大/最小元素（Find Max/Min）：在最大堆中查找最大元素，在最小堆中查找最小元素，时间复杂度为O(1)。

4. 堆排序（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比较如果：

1. parent小大于较大的孩子child，调整结束
2. 否则：交换parent与较大的孩子child，交换完成之后，parent中小的元素向下移动，可能导致子树不满足堆的性质，因此需要继续向下调整，即parent = child；child = parent*2+1; 然后继续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];}}

---

总结

这篇文章给大家重点讲解了堆的模拟实现还有其应用之一 优先级队列,大家好好理解,我们下一篇博客见。