首页 > 其他分享 >数据结构——优先队列

数据结构——优先队列

时间:2023-02-01 18:38:18浏览次数:53  
标签:index 优先 return 队列 元素 int 数据结构 data public

一、优先队列

优先队列顾名思义,就是优先权最大的排在队列的头部,而优先权的判断是根据对象的compare方法比较获取的,保证根节点的优先级一定比子节点的优先级大。所以放入到优先队列的元素要么实现了Comparable接口,要么在创造这个优先队列时,指定一个比较器。

 

普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。通常采用堆数据结构来实现。

二、代码实现

  • 优先队列通常采用堆数据结构来实现,而堆数据结构通常采用数组为底层数据结构实现。

2.1 动态数组的底层实现

/**
 * @Author: huangyibo
 * @Date: 2021/12/25 17:29
 * @Description: 动态数组实现
 */

public class Array<E> {

    private E[] data;

    private int size;

    public Array(){
        this(10);
    }

    public Array(int capacity){
        this.data = (E[]) new Object[capacity];
        this.size = 0;
    }

    public Array(E[] arr){
        this.data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        this.size = arr.length;
    }

    /**
     * 获取数组中元素个数
     * @return
     */
    public int getSize(){
        return size;
    }

    /**
     * 获取数组容量
     * @return
     */
    public int getCapacity(){
        return data.length;
    }

    /**
     * 返回数组是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 数组尾部新增元素
     * @param e
     */
    public void addLast(E e){
        add(size, e);
    }

    /**
     * 数组头部新增元素
     * @param e
     */
    public void addFirst(E e){
        add(0, e);
    }

    /**
     * 在指定位置插入元素
     * @param index
     * @param e
     */
    public void add(int index, E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("AddLast failed. require index >=0 and index <= size");
        }
        if(size == data.length){
            //扩容
            resize(2 * data.length);
        }

        for(int i = size - 1; i >= index; i --){
            data[i + 1] = data[i];
        }
        data[index] = e;
        size ++;
    }

    /**
     * 数组扩容
     * @param newCapacity
     */
    private void resize(int newCapacity){
        E[] newData = (E[])new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    /**
     * 获取指定索引位置的值
     * @param index
     * @return
     */
    public E get(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("Get failed. index is illegal.");
        }
        return data[index];
    }

    /**
     * 替换指定索引位置的值
     * @param index
     * @param e
     */
    public void set(int index, E e){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("Set failed. index is illegal.");
        }
        data[index] = e;
    }

    /**
     * 数组是否包含元素e
     * @param e
     * @return
     */
    public boolean contains(E e){
        for (int i = 0; i < size; i++) {
            if(data[i].equals(e)){
                return true;
            }
        }
        return false;
    }

    /**
     * 查找数组中元素e所在的索引,不存在元素e,返回-1
     * @param e
     * @return
     */
    public int find(E e){
        for (int i = 0; i < size; i++) {
            if(data[i].equals(e)){
                return i;
            }
        }
        return -1;
    }

    /**
     * 删除数组中index位置的元素, 并返回删除的元素
     * @param index
     * @return
     */
    public E remove(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("Remove failed. index is illegal.");
        }
        E ret = data[index];
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        size --;
        data[size] = null;
        if(size == data.length / 4 && data.length / 2 != 0){
            //当数组长度缩小为原数组的4分之一的时候才进行数组的缩容,
            //缩小为原数组的2分之一,预留空间,防止有数据添加导致扩容浪费性能
            resize(data.length / 2);
        }
        return ret;
    }

    /**
     * 删除数组中第一个元素
     * @return
     */
    public E removeFirst(){
        return remove(0);
    }

    /**
     * 删除数组中最后一个元素
     * @return
     */
    public E removeLast(){
        return remove(size - 1);
    }

    /**
     * 从数组中删除元素e
     * @param e
     */
    public void removeElement(E e){
        int index = find(e);
        if(index != -1){
            remove(index);
        }
    }

    /**
     * 数组索引元素交换
     * @param i
     * @param j
     */
    public void swap(int i, int j){
        if(i < 0 || i >= size || j < 0 || j >= size){
            throw new IllegalArgumentException("Index is illegal.");
        }
        E temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("Array: size = %d, capacity = %d\n",size,data.length));
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if(i != size - 1){
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

2.2 最大堆——使用动态数组作为底层实现

/**
 * @Author: huangyibo
 * @Date: 2022/2/17 22:54
 * @Description: 最大堆 完全二叉树,父亲节点大于等于孩子节点,采用数组表示
 */

public class MaxHeap<E extends Comparable<E>> {

    //这里使用数组作为底层实现
    private Array<E> data;

    public MaxHeap(){
        data = new Array<>();
    }

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    /**
     * 将任意数组整理成堆的形状
     * @param arr
     */
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        //从最后一个叶子节点的父节点开始进行siftDown操作,不断循环
        for(int i = parent(arr.length - 1); i >= 0; i --){
            siftDown(i);
        }
    }

    /**
     * 返回堆中的元素个数
     * @return
     */
    public int getSize(){
        return data.getSize();
    }

    /**
     *堆是否为空
     * @return
     */
    public boolean isEmpty(){
        return data.isEmpty();
    }

    /**
     * 返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引
     * @param index
     * @return
     */
    private int parent(int index){
        if(index == 0){
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        }
        return (index - 1) / 2;
    }

    /**
     * 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
     * @return
     */
    private int leftChild(int index){
        return index * 2 + 1;
    }

    /**
     * 回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
     * @param index
     * @return
     */
    private int rightChild(int index){
        return index * 2 + 2;
    }

    /**
     * 向堆中添加元素
     * @param e
     */
    public void add(E e){
        data.addLast(e);
        //当前元素在数组中的索引为 data.getSize() - 1
        //比较当前元素和其父亲节点的元素,大于父亲节点元素则交换位置
        siftUp(data.getSize() - 1);
    }

    /**
     * k索引元素比父节点元素大,则交换位置,不断循环
     * @param k
     */
    private void siftUp(int k){
        //k > 0 并且k索引元素比父节点元素大,则交换位置,不断循环
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
            data.swap(parent(k), k);
            k = parent(k);
        }
    }

    /**
     * 查看堆中最大元素
     * @return
     */
    public E findMax(){
        if(data.getSize() == 0){
            throw new IllegalArgumentException("Can not findMax when heap is empty.");
        }
        return data.get(0);
    }

    /**
     * 取出堆中最大元素
     * @return
     */
    public E extractMax(){
        //获取堆中最大元素
        E ret = findMax();

        //堆中最开始的元素和最后元素交换位置
        data.swap(0,data.getSize() - 1);

        //删除堆中最后一个元素
        data.removeLast();
        //0索引元素比左右孩子节点元素小,则交换位置,不断循环
        siftDown(0);
        return ret;
    }

    /**
     * k索引元素比左右孩子节点元素小,则交换位置,不断循环
     * @param k
     */
    private void siftDown(int k){

        while (leftChild(k) < data.getSize()){
            //获取k索引的左孩子的索引
            int j = leftChild(k);

            //j + 1 < data.getSize()
            if(j + 1 < data.getSize() &&
                    //如果右孩子比左孩子大
                    data.get(j + 1).compareTo(data.get(j)) > 0){
                //最大孩子的索引赋值给j
                j = rightChild(k);
            }

            //此时data[j]是leftChild和rightChild中的最大值
            if(data.get(k).compareTo(data.get(j)) >= 0){
                //如果父亲节点大于等于左右孩子节点,跳出循环
                break;
            }

            //如果父亲节点小于左右孩子节点(中的最大值),交换索引的值
            data.swap(k, j);

            //交换完成之后,将j赋值给K,重新进入循环
            k = j;
        }
    }

    /**
     * 取出堆中最大元素,并且替换成元素e
     * @param e
     * @return
     */
    public E replace(E e){
        //获取堆中的最大值
        E ret = findMax();
        //用新添加的元素替换最大的元素
        data.set(0, e);
        //0索引元素比左右孩子节点元素小,则交换位置,不断循环
        siftDown(0);
        return ret;
    }
}

2.3 队列的抽象接口

public interface Queue<E> {

    /**
     * 队列的容量
     * @return
     */
    int getSize();

    /**
     * 队列是否为空
     * @return
     */
    boolean isEmpty();

    /**
     * 向队列中添加元素
     * @param e
     */
    void enqueue(E e);

    /**
     * 向队列取出元素
     * @return
     */
    E dequeue();

    /**
     * 查看队列第一个元素
     * @return
     */
    E getFront();
}

2.4 优先队列——基于最大堆实现

/**
 * @Author: huangyibo
 * @Date: 2022/2/19 17:52
 * @Description: 优先队列:基于最大堆实现
 */

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private MaxHeap<E> maxHeap;

    public PriorityQueue(){
        maxHeap = new MaxHeap<>();
    }

    @Override
    public int getSize() {
        return maxHeap.getSize();
    }

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

    @Override
    public E getFront() {
        return maxHeap.findMax();
    }

    @Override
    public void enqueue(E e) {
        maxHeap.add(e);
    }

    @Override
    public E dequeue() {
        return maxHeap.extractMax();
    }
}

三、java中的priorityqueue

在Java中也实现了自己的优先队列java.util.PriorityQueue,与我们自己写的不同之处在于,Java中内置的为最小堆,然后就是一些函数名不一样,底层还是维护了一个Object类型的数组,大家可以戳戳看有什么不同,另外如果想要把最小堆变成最大堆可以给PriorityQueue传入自己的比较器。

3.1 在N个元素中选出最小的K个元素

  • 输入整数数组 arr ,找出其中最小的 k 个数
  • 采用上面自定义的最大堆实现
/**
 * @Author: huangyibo
 * @Date: 2022/2/19 18:05
 * @Description: 在N个元素中选出最小的K个元素
 */

public class Solution {

    public int[] getLeastNumbers(int[] arr, int k){
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        //现将k个元素放进优先队列中
        for (int i = 0; i < k; i++) {
            pq.enqueue(arr[i]);
        }

        //数组余下的元素和pq最大的元素进行比较
        for (int i = k; i < arr.length; i++) {
            //如果数组元素比优先队列中最大的元素小的话
            if(!pq.isEmpty() && arr[i] < pq.getFront()){
                //优先队列中最大元素出队
                pq.dequeue();
                //将数组元素放入优先队列中
                pq.enqueue(arr[i]);
            }
        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = pq.dequeue();
        }
        return result;
    }
}

3.2 在N个元素中选出最小的K个元素

  • 输入整数数组 arr ,找出其中最小的 k 个数。
  • 采用java.util.PriorityQueue实现
import java.util.Collections;
import java.util.PriorityQueue;

/**
 * @Author: huangyibo
 * @Date: 2022/2/19 18:05
 * @Description: 输入整数数组 arr ,找出其中最小的 k 个数
 */
public class Solution2 {

    public int[] getLeastNumbers(int[] arr, int k){
        //java.util.PriorityQueue 默认为最小堆实现
        //PriorityQueue 构造函数传入Collections.reverseOrder(), 则按最大堆的逻辑进行构建
        //Collections.reverseOrder() 反向比较器
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        //现将k个元素放进优先队列中
        for (int i = 0; i < k; i++) {
            pq.add(arr[i]);
        }

        //数组余下的元素和pq最大的元素进行比较
        for (int i = k; i < arr.length; i++) {
            //如果数组元素比优先队列中最大的元素小的话
            if(!pq.isEmpty() && arr[i] < pq.peek()){
                //优先队列中最大元素出队
                pq.remove();
                //将数组元素放入优先队列中
                pq.add(arr[i]);
            }
        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = pq.remove();
        }
        return result;
    }
}

3.3 在N个元素中选出第 k 个最大的元素

  • 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
  • 采用java.util.PriorityQueue实现
import java.util.PriorityQueue;

/**
 * @Author: huangyibo
 * @Date: 2022/2/19 18:05
 * @Description: 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
 *
 * 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
 */
public class Solution3 {

    public int findKthLargest(int[] nums, int k) {
        //java.util.PriorityQueue 默认为最小堆实现
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        //现将k个元素放进优先队列中
        for (int i = 0; i < k; i++) {
            pq.add(nums[i]);
        }

        //数组余下的元素和pq最大的元素进行比较
        for (int i = k; i < nums.length; i++) {
            //如果数组元素比优先队列中最小的元素大的话
            if(!pq.isEmpty() && nums[i] > pq.peek()){
                //优先队列中最小元素出队
                pq.remove();
                //将数组元素放入优先队列中
                pq.add(nums[i]);
            }
        }
        return pq.peek();
    }
}

参考: https://blog.csdn.net/love905661433/article/details/82989608

https://www.cnblogs.com/wmyskxz/p/9301021.html

标签:index,优先,return,队列,元素,int,数据结构,data,public
From: https://blog.51cto.com/u_14014612/6031750

相关文章

  • 数据结构——线段树
    一、概述线段树是一种二叉搜索树,其存储的是一个区间的信息,每个结点以结构体的形式去存储,每个结构体包含三个元素:区间左端点、区间右端点、该区间要维护的信息(视实际情况而......
  • 数据结构——Trie
    一、Trie字典树在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位......
  • 数据结构——并查集
    一、并查集的概念在计算机科学中,并查集是一种树形的数据结构,用于处理不交集的合并(union)及查询(find)问题。 并查集可用于查询网络中两个节点的状态,这里的网络是......
  • 数据结构——AVL树
    一、平衡二叉树平衡二叉树也称平衡二叉搜索树(Self-balancingbinarysearchtree)是一种结构平衡的二分搜索树。 平衡二叉树由二分搜索树发展而来,在二分搜索树的基础上......
  • 数据结构——红黑树
    前言红黑树是计算机科学内比较常用的一种数据结构,它使得对数据的搜索,插入和删除操作都能保持在O(㏒n)的时间复杂度。然而,相比于一般的数据结构,红黑树的实现的难度有所增加......
  • 数据结构——Hash表
    前言Hash表也叫散列表,是一种线性数据结构。在一般情况下,可以用o(1)的时间复杂度进行数据的增删改查。在Java开发语言中,HashMap的底层就是一个散列表。一、什么是Hash表Ha......
  • 数据结构——动态数组
    简介数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。因此可以通过索引(Index)计算出某个元素的地址。 数组特点索引(即下标)......
  • 数据结构——队列
    简介队列是是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。 队列是一种先进先出的线性表,简称FIFO允许插入的以端称为队尾,允许删除的一端被称为队头。入......
  • 数据结构——栈
    简介限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端成为栈顶,另一端成为栈低,不含任何元素的栈成为空栈,栈又称为先进先出的线性表,简称LIFO结构。 栈的插......
  • 数据结构——链表
    链表数组要一块连续的内存空间来存储,对内存的要求比较高。如果我们申请一个100MB大小的数组,当内存中没有连续的、足够大的存储空间时,即便内存的剩余总可用空间大于100MB,......