堆和优先级队列

目录

堆和优先级队列

堆

堆的特点：

以大根堆为例：

堆(heap)的基础实现：

最大堆代码的实现

优先级队列

概念​​​​​​​

原理

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

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

---

堆和优先级队列

堆 堆有很多种存储形式，这里说的是二叉堆 - 基于二叉树的堆 二叉堆 - 就是一颗完全二叉树（满二叉树缺了个“右下角”）

堆的特点：         a，二叉堆首先是一颗完全二叉树（结构上）         b，二叉堆节点间关系满足以下要求：                 堆中根节点值 >= 子树中的节点值（最大堆/大根堆）

​​​​​​​

                堆中根节点值 <= 子树中的节点值（最小堆/小根堆）          c， 堆物理上是保存在数组中                 完全二叉树/满二叉树也可以建议使用顺序表（数组）来存储，但是其他二叉树不建议使用顺序表（数组）。因为用数组存储的话，前者没有空间的浪费，就是按照层序遍历来一个个写出来，在完全二叉树中不存在只有右子树没有左子树的情况，因此前者不用存储空节点，而后者则要存储空节点，会浪费大量的空间。         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)

private void siftUp(int k) {
    //此时还没走到根节点 ｜｜ 当前元素 > 父节点元素
    while (k > 0 && data.get(k) > data.get(parent(k))) {
        //将当前节点位置与父节点位置交换
        swap(k, parent(k));
        k = parent(k);
    }
}

        交换操作 - swap( )

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( )

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)

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);         代码实现：

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;



public class MaxHeap {
    //使用JDK的动态数组来存储最大堆
    List data;


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


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


    
    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);
    }


    
    private void siftUp(int k) {
        //此时还没走到根节点 ｜｜ 当前元素 > 父节点元素
        while (k > 0 && data.get(k) > data.get(parent(k))) {
            //将当前节点位置与父节点位置交换
            swap(k, parent(k));
            k = parent(k);
        }
    }


    
    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;
    }


    
    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;
            }
        }
    }


    
    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{
    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 {


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


//降序比较
class StudentComDesc implements Comparator {


    @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 queue = new PriorityQueue<>(new Comparator() {
    @Override
    public int compare(Student o1, Student o2) {
        return o2.getAge() - o1.getAge();
    }
});

还可以更简化的写为

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

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

import Stack_Queue.queue.Queue;



public class PriorityQueue implements Queue {
    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();
    }
}