堆和优先级队列

?????????? ?? ? 完全二叉树/满二叉树也可以建议使用顺序表（数组）来存储，但是其他二叉树不建议使用顺序表（数组）。因为用数组存储的话，前者没有空间的浪费，就是按照层序遍历来一个个写出来，在完全二叉树中不存在只有右子树没有左子树的情况，因此前者不用存储空节点，而后者则要存储空节点，会浪费大量的空间。

????????d，?堆的基本作用是，快速找集合中的最值?

以大根堆为例：

?? ?? ??在最大堆中，只能保证当前根节点 >= 子树的所有节点，在任意子树中仍满足这个特点，但是节点的大小关系和所处的层次无关，节点层次越高不一定比同一层节点的子节点的值大。

顺序存储时，节点索引和节点的关系如下：

根节点从0开始编号：

?? ?? ? 如何看一个节点k是否存在左右子树？

?? ??? ??? ??? ?看左右子树节点索引是否小于数组长度，左/右子树的索引为2*k+1/2 - 即 2 * k + 1 / 2 < 数组长度?

?? ?? ? 如何看一个节点索引k的父节点是否存在？

?? ??? ??? ?? ? 在二叉树中只有一个节点没有父节点 - 根节点0，因此只需要看父节点的编号是否 > 0即可，即(k - 1) / 2 > 0。

堆(heap)的基础实现：

? ?? ? 基于整型的最大堆代码实现

1.向最大堆中添加一个元素

?? ?? ? 第一步：直接在数组的末尾新增元素 - > 结构上保证添加元素之后，这颗二叉树仍然是完全二叉树

?? ?? ? 第二步：添加完新元素之后，要调整元素的位置，使得这颗完全二叉树仍然满足最大堆的性质。

?? ??? ??? ??? ??? ????即上浮操作 - siftUp(int k)：向上调整索引为k的节点，使其仍然满足堆的性质。

?? ??? ??? ??? ??? ?? ?上浮操作的终止条件：当前节点值 < = 父节点值 (已处在最终位置)

?? ?? ? 代码实现：

?? ?? ? 添加方法 - add(int val)

//元素添加操作
public void add(int val) {
????//1.将元素添加到数组末尾
????data.add(val);
????//2.元素的上浮操作
????siftUp(data.size() - 1);
}

?? ?? ? 上浮操作 - siftUp(int k)

/**
* 上浮操作
* 上浮终止条件：已经走到根节点 || 当前节点值 <= 父节点值
* @param k
*/
private void siftUp(int k) {
????//此时还没走到根节点 ｜｜ 当前元素 > 父节点元素
????while (k > 0 && data.get(k) > data.get(parent(k))) {
????????//将当前节点位置与父节点位置交换
????????swap(k, parent(k));
????????k = parent(k);
????}
}

?? ?? ? 交换操作 - swap( )

/**
* 元素位置交换
*
* @param i
* @param j
*/
private void swap(int i, int j) {
????int temp = data.get(i);
????data.set(i, data.get(j));
????data.set(j, temp);
}

2.取出当前堆中的最大元素值 - 即取出堆顶元素 - extractMax( )

? ? ? ? 第一步：直接从堆顶取出最大值 data.get(0)

?? ?? ? 第二步：删除栈顶元素

?? ??? ??? ??? ?? ? ? ?对于数组来说，元素的添加和删除在数组末尾是最简单的；反之在数组头部的删除和插入是最麻烦的。

?? ??? ??? ??? ?? ? ? ?因此，我们在取出栈顶元素后，直接将数组末尾的元素顶到堆顶，然后进行元素的下沉操作。

?? ??? ??? ??? ?? ? ? ?下沉操作 - siftDown(int k)：调整索引k的节点不断下沉，直到到达最终位置。

?? ??? ??? ??? ??? ?? ? 下沉终止条件：

?? ??? ??? ??? ??? ??? ??? ????a，到达了叶子节点 2k + 1 > size??? ?

?? ??? ??? ??? ??? ??? ??? ??? b，当前节点值 > 左右子树的最大值

?? ?? ? 结论：我们不难看出，如果一直进行这个操作，我们会得到一个非增排列的数组

?? ?? ? 代码实现：

?? ?? ? 取出最大值方法 -?extractMax( )

/**
* 删除堆中最大值，即取出堆顶元素
*
* @return
*/
public int extractMax() {
????//判空
????if (isEmpty()) {
????????throw new NoSuchElementException("heap is empty!cannot extract!");
????}
????//1.获取最大值
????int max = data.get(0);
????//2.将数组末尾元素顶到堆顶
????int value = data.get(data.size() - 1);
????data.set(0, value);
????//3.删除末尾元素删除
????data.remove(data.size() - 1);
????//4.堆顶元素下沉操作
????siftDown(0);
????return max;
}

?? ?? ? 下沉操作 - siftDown(int k)

/**
* 下沉操作
* 终止条件： 2k + 1 > size || 当前节点值 > 左右子树的值
*
* @param k
*/
private void siftDown(int k) {
????//还存在子树
????while (leftChild(k) < data.size()) {
????????int j = leftChild(k);
????????//判断一下是否有右子树，如果有判断左右子树大小
????????if (j + 1 < data.size() && data.get(j + 1) > data.get(j)) {
????????????//此时右树存在且大于左树
????????????j = j + 1;
????????}
????????//此时j就是该节点左右子树最大值
????????//将该节点值与最大值比较
????????if (data.get(k) >= data.get(j)) {
????????????//此时下沉结束，退出循环
????????????break;
????????}
????????if (data.get(k) < data.get(j)) {
????????????//节点值小于左右子树最大值
????????????//进行下沉
????????????swap(k, j);
????????????k = j;
????????}
????}
}

?? ?? ? 交换操作 - swap( )

提示：

????????在测试自己代码的正确性时，以siftDown为例，不要在小集合上测试，那样会片面。可以生成一个10w个随机数，然后将这10w个元素构成最大堆，然后不断extractMax（）得到一个非递增的数组，前一个元素 >= 后一个元素然后再找错误

3.堆化操作?- heapify将任意数组调整为堆的结构

?? ??? ?不断的调用add方法虽然也可以达到目的，其时间复杂度为NogN，但这并不是堆化操作。

?? ?? ? 堆化的思路为：从小问题逐步向上走，不断去调整子树，将子树不断变为大树的过程，就将整颗树调整为堆结构，其时间复杂度为O(N)。

?? ?? ? 任意一个数组都可以看作是一颗完全二叉树，从当前这个完全二叉树的最后一个非叶子节点开始，进行元素的下沉操作即可调整为堆。

?? ?? ? 最后一个非叶子节点就是最后一个叶子节点的父节点 - lastNotLeafNode = parent(data.size( ) - 1);

?? ?? ? 代码实现：

/**
* 数组的堆化操作
*
* @param arr
*/
public MaxHeap(int[] arr) {
????data = new ArrayList<>(arr.length);
????// 1.将数组元素复制到data数组中
????for (int i : arr) {
????????data.add(i);
????}
????// 2.从最后一个非叶子节点进行下沉操作
????for (int i = data.size() - 1; i >= 0; i--) {
????????siftDown(i);
????}
}

最大堆代码的实现

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;


/**
* 基于整型的最大堆实现
* 根节点从0开始编号，若此时节点编号为k
* 左子树节点：2k + 1
* 右子树节点：2k + 2
* 父节点：（k - 1）/ 2
*/
public class MaxHeap {
????//使用JDK的动态数组来存储最大堆
????List<Integer> data;


????public MaxHeap() {
????????//无参构造，默认长度为10
????????this(10);
????}


????public MaxHeap(int size) {
????????//有参构造，初始化堆大小
????????this.data = new ArrayList<>(size);
????}


????/**
?????* 数组的堆化操作
?????*
?????* @param arr
?????*/
????public MaxHeap(int[] arr) {
????????data = new ArrayList<>(arr.length);
????????// 1.将数组元素复制到data数组中
????????for (int i : arr) {
????????????data.add(i);
????????}
????????// 2.从最后一个非叶子节点进行下沉操作
????????for (int i = data.size() - 1; i >= 0; i--) {
????????????siftDown(i);
????????}
????}


????//查看最大元素
????public int peekMax() {
????????if (isEmpty()) {
????????????throw new NoSuchElementException("heap is empty!cannot peek");
????????}
????????return data.get(0);
????}


????//元素添加操作
????public void add(int val) {
????????//1.将元素添加到数组末尾
????????data.add(val);
????????//2.元素的上浮操作
????????siftUp(data.size() - 1);
????}


????/**
?????* 上浮操作
?????* 上浮终止条件：已经走到根节点 || 当前节点值 <= 父节点值
?????*
?????* @param k
?????*/
????private void siftUp(int k) {
????????//此时还没走到根节点 ｜｜ 当前元素 > 父节点元素
????????while (k > 0 && data.get(k) > data.get(parent(k))) {
????????????//将当前节点位置与父节点位置交换
????????????swap(k, parent(k));
????????????k = parent(k);
????????}
????}


????/**
?????* 删除堆中最大值，即取出堆顶元素
?????*
?????* @return
?????*/
????public int extractMax() {
????????//判空
????????if (isEmpty()) {
????????????throw new NoSuchElementException("heap is empty!cannot extract!");
????????}
????????//1.获取最大值
????????int max = data.get(0);
????????//2.将数组末尾元素顶到堆顶
????????int value = data.get(data.size() - 1);
????????data.set(0, value);
????????//3.删除末尾元素删除
????????data.remove(data.size() - 1);
????????//4.堆顶元素下沉操作
????????siftDown(0);
????????return max;
????}


????/**
?????* 下沉操作
?????* 终止条件： 2k + 1 > size || 当前节点值 > 左右子树的值
?????*
?????* @param k
?????*/
????private void siftDown(int k) {
????????//还存在子树
????????while (leftChild(k) < data.size()) {
????????????int j = leftChild(k);
????????????//判断一下是否有右子树，如果有判断左右子树大小
????????????if (j + 1 < data.size() && data.get(j + 1) > data.get(j)) {
????????????????//此时右树存在且大于左树
????????????????j = j + 1;
????????????}
????????????//此时j就是该节点左右子树最大值
????????????//将该节点值与最大值比较
????????????if (data.get(k) >= data.get(j)) {
????????????????//此时下沉结束，退出循环
????????????????break;
????????????}
????????????if (data.get(k) < data.get(j)) {
????????????????//节点值小于左右子树最大值
????????????????//进行下沉
????????????????swap(k, j);
????????????????k = j;
????????????}
????????}
????}


????/**
?????* 元素位置交换
?????*
?????* @param i
?????* @param j
?????*/
????private void swap(int i, int j) {
????????int temp = data.get(i);
????????data.set(i, data.get(j));
????????data.set(j, temp);
????}


????//判空
????public boolean isEmpty() {
????????return data.size() == 0;
????}


????//根据索引得到父节点的索引
????public int parent(int k) {
????????return (k - 1) >> 1;
????}


????//根据索引得到左子树索引
????public int leftChild(int k) {
????????return (k << 1) + 1;
????}


????//根据索引得到右子树索引
????public int rightChild(int k) {
????????return (k << 1) + 2;
????}


????@Override
????public String toString() {
????????return data.toString();
????}
}

优先级队列

普通队列：FIFO 元素先进先出

优先级队列：按照元素间的优先级大小 - 动态顺序出队

注意：JDK中的优先级队列默认是最小堆的实现，队首元素就是队列中最小值。

概念???????

????????很多应用中，我们通常需要按照优先级情况对待处理对象进行处理，比如首先处理优先级最高的对象，然后处理次高的对象。最简单的一个例子就是，在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话。在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)

原理

????????优先级队列的实现方式有很多，但最常见的是使用堆

自定义类元素间大小的比较

????????在比较自定义类型是否相等时需要覆盖Object类提供的equals方法。

????????比较两个自定义的对象谁大谁小，调用java.lang.Comparable类，一旦一个类实现了Comparable接口，就表示该类具备了可比较大小的能力。

????????输出结果: 当前对象 - ?传入对象

?? ???????????? ? ? ? ? ?> 0 当前对象 > 传入对象

?? ??? ??? ??????????? ? = 0??当前对象 = 传入对象

?? ??? ??? ?? ? ?????????< 0 当前对象 < 传入对象

????????一旦一个自定义的类覆写了Comparable类，那么就可以进行排序，排序默认是升序的。如果想要按照降序排列，因为sort方法是按照元素的大小顺序，小的在前，大的在后，不可能更改JDK的代码，所以可以更改一下compareTo方法，让大的反而小，小的反而大，即让程序以为大的是小的，小的是大的。

?? ??? ?即将：当前对象 - 传入对象 ?= 》传入对象 - 当前对象（自我理解：sort方法内部默认无论如何，comparTo方法return出的结果如果大于0，则固定认为是当前对象大于传入对象，因此我们可以利用这一点让小的反而成为大的，大的反而成为小的）

?? ??? ?代码示例：

public class PriorityQueueTest {
????public static void main(String[] args) {
????????Student stu1 = new Student("李雷", 25);
????????Student stu2 = new Student("韩梅梅", 20);
????????Student stu3 = new Student("小明", 40);
????????Student[] stu = {stu1,stu2,stu3};
????????Arrays.sort(stu);
????????System.out.println(Arrays.toString(stu));
????}
}


class Student implements Comparable<Student>{
????String name;
????int age;


????public Student(String name, int age) {
????????this.name = name;
????????this.age = age;
????}


????//将当前对象和传入的对象比较
????public boolean equals(Object o) {
????????if (o == null) {
????????????return false;
????????}
????????if (this == o) {
????????????return true;
????????}
????????//传入的o是否是Student类中new出来的
????????if (!(o instanceof Student)) {
????????????//不是同一类型，没有可比性
????????????return false;
????????}
????????//向下转型还原为Studen类
????????Student stu = (Student) o;
????????return this.age == stu.age && this.name.equals(stu.name);
????}


????@Override
????public String toString() {
????????return "Student{" +
????????????????"name='" + name + '\'' +
????????????????", age=" + age +
????????????????'}';
????}


????@Override
????public int compareTo(Student o) {
????????return this.age - o.age;
????}
}

????????虽然上述方法，可以改变排序方式，但是需要根据俄条件频繁的在自定义类内部更改，容易错乱。

????????因此我们可以引入一个java.util.Comparator - 比较器：需要比较的类并不需要实现此接口，而是有一个专门的类实现此接口，这个类就是为了进行自定义类大小的比较。

代码示例：

public class PriorityQueueTest {
????public static void main(String[] args) {
????????Student stu1 = new Student("李雷", 25);
????????Student stu2 = new Student("韩梅梅", 20);
????????Student stu3 = new Student("小明", 40);
????????Student[] stu = {stu1, stu2, stu3};
????????//升序的方式
????????Arrays.sort(stu, new StudentCom());
????????System.out.println(Arrays.toString(stu));
????????//降序的方式
????????Arrays.sort(stu, new StudentComDesc());
????????System.out.println(Arrays.toString(stu));
????}
}


//升序比较
class StudentCom implements Comparator<Student> {


????@Override
????public int compare(Student o1, Student o2) {
????????return o1.getAge() - o2.getAge();
????}
}


//降序比较
class StudentComDesc implements Comparator<Student> {


????@Override
????public int compare(Student o1, Student o2) {
????????return o2.getAge() - o1.getAge();
????}
}


class Student {
????String name;
????int age;


????public Student(String name, int age) {
????????this.name = name;
????????this.age = age;
????}


????public int getAge() {
????????return age;
????}


????//将当前对象和传入的对象比较
????public boolean equals(Object o) {
????????if (o == null) {
????????????return false;
????????}
????????if (this == o) {
????????????return true;
????????}
????????//传入的o是否是Student类中new出来的
????????if (!(o instanceof Student)) {
????????????//不是同一类型，没有可比性
????????????return false;
????????}
????????//向下转型还原为Studen类
????????Student stu = (Student) o;
????????return this.age == stu.age && this.name.equals(stu.name);
????}


????@Override
????public String toString() {
????????return "Student{" +
????????????????"name='" + name + '\'' +
????????????????", age=" + age +u
????????????????'}';
????}


????//@Override
//????public int compareTo(Student o) {
//????????return this.age - o.age;
//????}
}

????????Comparator相较于Comparable来说，无需修改要比较类的代码，这叫无侵入编程，这种模式叫策略模式 - 根据不同的需求配置不同的比较器

上述比较器实现可以用匿名内部类实现

Queue<Student> queue = new PriorityQueue<>(new Comparator<Student>() {
????@Override
????public int compare(Student o1, Student o2) {
????????return o2.getAge() - o1.getAge();
????}
});

还可以更简化的写为

//Lambda表达式，函数式编程
Queue<Student> queue = new PriorityQueue<>(((o1, o2) -> o2.getAge() - o1.getAge()));

基于上述堆中实现的最大堆的优先级队列的实现

import Stack_Queue.queue.Queue;


/**
* 基于最大堆的优先级队列
* 优先级：值越大优先级越高
*/
public class PriorityQueue implements Queue<Integer> {
????private MaxHeap heap;


????public PriorityQueue() {
????????heap = new MaxHeap();
????}


????@Override
????public void offer(Integer val) {
????????heap.add(val);
????}


????@Override
????public Integer poll() {
????????return heap.extractMax();
????}


????@Override
????public Integer peek() {
????????return heap.peekMax();
????}


????@Override
????public boolean isEmpty() {
????????return heap.isEmpty();
????}
}

[数据结构与算法]堆和优先级队列 - 数据结构（JAVA）

堆和优先级队列

堆和优先级队列

堆

堆的特点：

以大根堆为例：

堆(heap)的基础实现：

最大堆代码的实现

优先级队列

概念???????

原理

自定义类元素间大小的比较

基于上述堆中实现的最大堆的优先级队列的实现