Java学习苦旅(十九)——详解Java的堆和优先级队列

2024-01-08 12:01:39

本篇博客将详细讲解堆和优先级队列。

概念

  1. 堆逻辑上是一棵完全二叉树。

  2. 堆物理上是保存在数组中。

  3. 满足任意结点的值都大于其子树中结点的值,叫做大堆,或者大根堆,或者最大堆。反之,则是小堆,或者小根堆,或者最小堆。

image-20220306165626174

image-20220306170006428

堆的基本作用就是快速找出集合中的最值。

向下调整

**前提:**左右子树必须已经是一个堆,才能调整。

例如:

image-20220306181206804

示例代码:

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    /**
     * 向下调整函数的实现
     * @param parent 每棵树的根节点
     * @param len 每棵树调整的结束位置
     */
    public void shiftDown(int parent, int len) {
        int child = 2*parent + 1;
        while (child < len) {
            if (child+1 < len && elem[child] < elem[child+1]) {
                child++;
            }
            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2*parent + 1;
            } else {
                break;
            }
        }
    }

    public void createHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
        for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
            shiftDown(parent,usedSize);
        }
    }
}

此时,向下调整的代码时间复杂度为O(N)

优先级队列

概念

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

内部原理

优先级队列的实现方式有很多,但最常见的是使用堆来构建。

入队列

过程(以大根堆为例):

  1. 首先按尾插方式放入数组

  2. 比较其和其双亲的值的大小,如果双亲的值大,则满足堆的性质,插入结束

  3. 否则,交换其和双亲位置的值,重新进行 2、3 步骤

  4. 直到根结点

示例代码

public void shiftUp(int child) {
    int parent = (child-1)/2;
    while (child > 0) {
        if (elem[child] > elem[parent]) {
            int tmp = elem[child];
            elem[child] = elem[parent];
            elem[parent] = tmp;
            child = parent;
            parent = (child-1)/2;
        } else {
            break;
        }
    }
}

public void offer(int val) {
    if (isFull()) {
        elem = Arrays.copyOf(elem,2*elem.length);
    }
    elem[usedSize++] = val;
    shiftUp(usedSize-1);
}

public boolean isFull() {
    return usedSize == elem.length;
}

出队列

为了防止破坏堆的结构,删除时并不是直接将堆顶元素删除,而是用数组的最后一个元素替换堆顶元素,然后通过向下调整方式重新调整成堆。

示例代码

public int poll() {
    if (isEmpty()) {
        throw new RuntimeException("优先级队列为空");
    }
    int tmp = elem[0];
    elem[0] = elem[usedSize-1];
    elem[usedSize-1] = tmp;
    usedSize--;
    shiftDown(0,usedSize);
    return tmp;
}

public boolean isEmpty() {
    return usedSize == 0;
}

返回队首元素

返回堆顶元素即可

示例代码

public int peek() {
    if (isEmpty()) {
        throw new RuntimeException("优先级队列为空");
    }
    return elem[0];
}

java中的优先级队列

PriorityQueue代表java中的优先级队列。

常用操作

错误处理抛出异常返回特殊值
入队列add(e)offer(e)
出队列remove()poll()
队首元素element()peek()

PriorityQueue默认是小根堆。

topK问题

topK问题是指给定一组数据,找出前K个最大或最小的元素。

我们可以使用优先级队列去解决这个问题。

  • 如果求前K个最大元素,建一个小根堆。
  • 如果求前K个最小元素,建一个大根堆。
  • 如果求第K大的元素,建一个小根堆,堆顶元素就是第K大的元素。
  • 如果求第K小的元素,建一个大根堆,堆顶元素就是第K小的元素。

假如求前K个最小元素,具体代码如下:

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public static int[] topK(int[] array, int k) {
    //创建一个大小为K的大根堆
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    });
    //遍历数组中的元素,前K个元素放到队列中
    for (int i = 0; i < array.length; i++) {
        if (maxHeap.size() < k) {
            maxHeap.offer(array[i]);
        } else {
            //从第K+1个元素开始,每个元素和堆顶元素比较
            int top = maxHeap.peek();
            if (top > array[i]) {
                maxHeap.poll();
                maxHeap.offer(array[i]);
            }
        }
    }
    int[] tmp = new int[k];
    for (int i = 0; i < k; i++) {
        tmp[i] = maxHeap.poll();
    }
    return tmp;
}

我们可以验证一下,输入:

int[] array = {18,21,8,10,34,12};
int[] tmp = topK(array,3);
System.out.println(Arrays.toString(tmp));

输出:

image-20220309185801522

结尾

本篇博客到此结束。
上一篇博客:Java学习苦旅(十八)——详解Java中的二叉树
下一篇博客:Java学习苦旅(二十)——七大排序(JAVA代码)

文章来源:https://blog.csdn.net/m0_53408775/article/details/135392583
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。