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

简介: 数据结构优先级队列(堆)

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

文章目录

1.优先级队列

1.1概念

队列是一种先进先出(FIFO)的数据结构,但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列 ,在该场景中,队列显然不适用, 这时我们需要的操作是,一是返回最高优先级对象,二是添加新对象.这种数据结构称作优先级队列(Priority Queue)。

1.2优先级队列的模拟实现

在JDK1.8中的Priority Queue底层使用了堆这种数据结构 ,而堆实际就是在完全二叉树的基础上进行一些调整。

c39729f1d988919b83c68f790399eb82.png

2.堆

2.1概念

如果有一个集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足:Ki <= K2i+1 且 Ki<= K2i+2(Ki >= K2i+1 且 Ki >= K2i+2) i = 0,1,2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆

堆的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

2.2堆的存储方式

堆是一颗完全二叉树,可以利用层序遍历的规则采用顺序的方式来高效存储

703ae4c78cc8d8c881638ad3c2966b85.png

对于非二叉树,则不适合使用顺序排序方式进行存储,会导致空间利用率比较低

将元素存储到数组中后,利用完全二叉树的性质对树进行还原,假设i为数组下标,有以下性质


  • 当i=0时,则表示根节点,否则i节点的双亲节点为(i-1)/2
  • 如果2*i+1小于节点个数,则节点i的左孩子为2*i+1,否则没有左孩子
  • 如果2*i+2小于节点个数,则节点i的右孩子为2*i+2,否则没有右孩子

2.3堆的创建

2.3.1堆向下调整

对于集合{ 27,15,19,18,28,34,65,49,25,37 } 中的数据,首先利用层序遍历规则对树进行还原

d9b98077643dde172e078abd9d45723e.png


此时树已经满足堆的性质了,只要进行向下调整即可

这里我们以大根堆为例:

1.parent记为需要调整的根节点,child记为parent根节点的左孩子

2.parent存在左孩子,即:child<size,进行下列操作,直到parent的左孩子不存在


  • parent右孩子是否存在,存在找的左右孩子中较大的孩子,并将child修改为较大孩子的下标
  • 将parent与较大的孩子child比较
  • parent大于child,调整结束
  • 否则,交换parent与child,交换结束后,parent中小的元素向下移动,可能导致树不能满足堆的结构,因此继续向下调整,即parent=child;child=parent*2+1;进行操作2.

8827b1afc7f67f1b7c4d81d14c1b9691.png

private void shiftDown (int parent) {
        if (parent < 0) {
            return;
        }
        // 1. 先去找到左孩子节点
        int child = parent * 2 + 1;
        while (child < size) {
            // 2. 判断有没有右孩子
            if (child + 1 < size) {
                // 有右孩子节点,如右孩子节点的值比左孩子节点的值大,那么child就设置成右孩子节点的下标
                if (elementData[child + 1] > elementData[child]) {
                    child++; // 这时child下标对应的值是左右孩子节点中最大的那个
                }
            }
            // 3. 用孩子节点中最大的值与父节点去比较
            if (elementData[parent] >= elementData[child]) {
                break;
            }
            // 4. 交换父子节点的值
            swap(elementData, parent, child);
            // 5. 向下调整,重置父子下标
            parent = child;
            child = (parent * 2) + 1;
        }
    }
private void swap(int[] elementData, int parent, int child) {
        int tmp=elementData[parent];
        elementData[parent]=elementData[child];
        elementData[child]=tmp;
    }

2.3.2堆的创建

核心为对集合进行向下调整

public Head(int []array) {
        //复制数组,防止array的修改影响elementData
        this.elementData = Arrays.copyOf(array, array.length);
        this.size = elementData.length;
        //向下调整为堆结构
        int parent=(size-1-1)/2;
        for (int i = parent; i >=0 ; i--) {
            shiftDown(i);
        }
    }

2.4堆的插入与删除

2.4.1堆的插入

  1. 将元素放入到底层空间中(需判断是否需要扩容)
  2. 将最后插入的节点向上调整(与向下调整原理相似),直到符合堆结构
     public void offer(int val){
        //判断数组是否满了
        if (isFull()){
            //2倍扩容
            elementData=Arrays.copyOf(elementData,DEFAULT_CAPACITY*2);
        }
        //新元素插入到最后一个位置
        elementData[size]=val;
        size++;
        shiftUp(size-1);
     }
     //向上调整
    private void shiftUp(int child) {
        //判断是否越界
        if (child>=size){
            return;
        }
        int parent=(child-1)/2;
        //向上调整
        while (child>0&&parent>=0){
            //和父节点的值比较大小
            if(elementData[child]<=elementData[parent]){
                break;
            }
            //此时孩子节点的值比父节点的值大,交换
            swap(elementData,parent,child);
            //重置父子下标
            child=parent;
            parent=(child-1)/2;
        }
    }
    private boolean isFull() {
        return size==elementData.length;
    }

2.4.2 堆的删除

堆的删除实质是删除堆顶元素

  1. 将堆顶元素与最后一个元素交换
  2. 将堆中有效数据个数减少一个
  3. 对堆顶元素进行向下调整
public int poll(){
         //判断数组是否为空
        if (isEmpty()){
            throw new RuntimeException("数组为空");
        }
        int val=elementData[0];
        swap(elementData,0,size-1);
        size--;
        shiftDown(0);
        return val;
    }
    private boolean isEmpty() {
         return size==0;
    }

2.5用堆实现优先级队列

public class Head {
    //用一个数组存放数据
    private int[] elementData;
    //数组元素个数
    private int size;
    //数组大小
    private int DEFAULT_CAPACITY=10;
    public Head() {
        this.elementData=new int [DEFAULT_CAPACITY];
        this.size=0;
    }
    //通过一个数组创建堆
    public Head(int []array) {
        //复制数组,防 止array的修改影响elementData
        this.elementData = Arrays.copyOf(array, array.length);
        this.size = elementData.length;
        //向下调整为堆结构
        int parent=(size-1-1)/2;
        for (int i = parent; i >=0 ; i--) {
            shiftDown(i);
        }
    }
// 向下调整的核心逻辑
    private void shiftDown (int parent) {
        if (parent < 0) {
            return;
        }
        // 1. 先去找到左孩子节点
        int child = parent * 2 + 1;
        while (child < size) {
            // 2. 判断有没有右孩子
            if (child + 1 < size) {
                // 有右孩子节点,如右孩子节点的值比左孩子节点的值大,那么child就设置成右孩子节点的下标
                if (elementData[child + 1] > elementData[child]) {
                    child++; // 这时child下标对应的值是左右孩子节点中最大的那个
                }
            }
            // 3. 用孩子节点中最大的值与父节点去比较
            if (elementData[parent] >= elementData[child]) {
                break;
            }
            // 4. 交换父子节点的值
            swap(elementData, parent, child);
            // 5. 向下调整,重置父子下标
            parent = child;
            child = (parent * 2) + 1;
        }
    }
    private void swap(int[] elementData, int parent, int child) {
        int tmp=elementData[parent];
        elementData[parent]=elementData[child];
        elementData[child]=tmp;
    }
    /**
     * 堆的插入
     * @param val
     */
     public void offer(int val){
        //判断数组是否满了
        if (isFull()){
            //2倍扩容
            elementData=Arrays.copyOf(elementData,DEFAULT_CAPACITY*2);
        }
        //新元素插入到最后一个位置
        elementData[size]=val;
        size++;
        shiftUp(size-1);
     }
     //向上调整
    private void shiftUp(int child) {
        //判断是否越界
        if (child>=size){
            return;
        }
        int parent=(child-1)/2;
        //向上调整
        while (child>0&&parent>=0){
            //和父节点的值比较大小
            if(elementData[child]<=elementData[parent]){
                break;
            }
            //此时孩子节点的值比父节点的值大,交换
            swap(elementData,parent,child);
            //重置父子下标
            child=parent;
            parent=(child-1)/2;
        }
    }
    private boolean isFull() {
        return size==elementData.length;
    }
    /**
     * 堆的删除
     * @return
     */
    public int poll(){
         //判断数组是否为空
        if (isEmpty()){
            throw new RuntimeException("数组为空");
        }
        int val=elementData[0];
        swap(elementData,0,size-1);
        size--;
        shiftDown(0);
        return val;
    }
    private boolean isEmpty() {
         return size==0;
    }
    public int peek(){
        return elementData[0];
    }
    public void display(){
        StringBuilder sb=new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(elementData[i]);
            if (i<size-1){
                sb.append(",");
            }
        }
        sb.append("]");
        sb.toString();
        System.out.println(sb);
    }
}

3.PriorityQueue

Java集合框架为我们提供了2种优先级队列的接口:PriorityQueuePriorityBlockingQueue,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的 。

3.1注意

  1. 使用PriorityQueue是必须导入相应的包
import java.util.PriorityQueue;
  1. PriorityQueue中放置的元素必须能够比较大小,否则抛出ClassCastException异常


  1. 插入对象不能为null,否则抛出NullPointerException异常


  1. 内部默认容量为11,空间不足时会进行扩容


  1. 默认情况下是小根堆,如需要大根堆需要用户提供比较器

3.2常用的接口

构造方式


deca10a7f80d320a67238d0f28f0812.png

deca10a7f80d320a67238d0f28f0812.png

插入/删除/获取优先级最高的元素

7856ff59b1deb1173d97dc636646356.png

olean offer(E e) | 插入元素e,插入成功返回true,如果e为空,抛出NullPointerException异常,空间不足时会进行扩容 |

| E peek() | 获取优先级最高的元素,如果优先级队列为空,返回null |

| E poll() | 移除优先级最高的元素并返回,如果优先级队列为空,返回null |

| int size() | 获取有效元素的个数 |

| void clear() | 清空 |


目录
相关文章
|
1天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
29 16
|
2天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
38 9
|
5天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
24天前
初步认识栈和队列
初步认识栈和队列
52 10
|
22天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
61 1
|
24天前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
19 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
19天前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
13 0
|
23天前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
23天前
探索数据结构:队列的的实现与应用
探索数据结构:队列的的实现与应用
|
23天前
|
存储 C语言
栈和队列题目练习
栈和队列题目练习
14 0