欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构与算法(4)——优先队列和堆

程序员文章站 2022-06-30 12:53:16
前言:题图无关,接下来开始简单学习学习优先队列和堆的相关数据结构的知识; 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)——栈和队列(https://www.jianshu.com/p/5087c7 ......

数据结构与算法(4)——优先队列和堆

前言:题图无关,接下来开始简单学习学习优先队列和堆的相关数据结构的知识;

前序文章:

  • 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875)
  • 数据结构与算法(2)——栈和队列(https://www.jianshu.com/p/5087c751cb42)
  • 数据结构与算法(3)——树(二叉、二叉搜索树)(https://www.jianshu.com/p/4ef1f50d45b5)

什么是优先队列?

听这个名字就能知道,优先队列也是一种队列,只不过不同的是,优先队列的出队顺序是按照优先级来的;在有些情况下,可能需要找到元素集合中的最小或者最大元素,可以利用优先队列ADT来完成操作,优先队列ADT是一种数据结构,它支持插入和删除最小值操作(返回并删除最小元素)或删除最大值操作(返回并删除最大元素);

这些操作等价于队列的enQueuedeQueue操作,区别在于,对于优先队列,元素进入队列的顺序可能与其被操作的顺序不同,作业调度是优先队列的一个应用实例,它根据优先级的高低而不是先到先服务的方式来进行调度;

数据结构与算法(4)——优先队列和堆

如果最小键值元素拥有最高的优先级,那么这种优先队列叫作升序优先队列(即总是先删除最小的元素),类似的,如果最大键值元素拥有最高的优先级,那么这种优先队列叫作降序优先队列(即总是先删除最大的元素);由于这两种类型时对称的,所以只需要关注其中一种,如升序优先队列;

优先队列ADT

下面操作组成了优先队列的一个ADT;

1.优先队列的主要操作
优先队列是元素的容器,每个元素有一个相关的键值;

  • insert(key, data):插入键值为key的数据到优先队列中,元素以其key进行排序;
  • deleteMin/deleteMax:删除并返回最小/最大键值的元素;
  • getMinimum/getMaximum:返回最小/最大剑指的元素,但不删除它;

2.优先队列的辅助操作

  • 第k最小/第k最大:返回优先队列中键值为第k个最小/最大的元素;
  • 大小(size):返回优先队列中的元素个数;
  • 堆排序(Heap Sort):基于键值的优先级将优先队列中的元素进行排序;

优先队列的应用

  • 数据压缩:赫夫曼编码算法;
  • 最短路径算法:Dijkstra算法;
  • 最小生成树算法:Prim算法;
  • 事件驱动仿真:顾客排队算法;
  • 选择问题:查找第k个最小元素;
  • 等等等等....

优先队列的实现比较

实现 插入 删除 寻找最小值
无序数组 1 n n
无序链表 1 n n
有序数组 n 1 1
有序链表 n 1 1
二叉搜索树 logn(平均) logn(平均) logn(平均)
平衡二叉搜索树 logn logn logn
二叉堆 logn logn 1

堆和二叉堆

什么是堆

堆是一颗具有特定性质的二叉树,堆的基本要求就是堆中所有结点的值必须大于或等于(或小于或等于)其孩子结点的值,这也称为堆的性质;堆还有另一个性质,就是当 h > 0 时,所有叶子结点都处于第 h 或 h - 1 层(其中 h 为树的高度,完全二叉树),也就是说,堆应该是一颗完全二叉树;

数据结构与算法(4)——优先队列和堆

在下面的例子中,左边的树为堆(每个元素都大于其孩子结点的值),而右边的树不是堆(因为5大于其孩子结点2)

数据结构与算法(4)——优先队列和堆

二叉堆

在二叉堆中,每个结点最多有两个孩子结点,在实际应用中,二叉堆已经足够满足需求,因此接下来主要讨论二叉最小堆和二叉最大堆;

堆的表示:在描述堆的操作前,首先来看堆是怎样表示的,一种可能的方法就是使用数组,因为堆在形式上是一颗完全二叉树,用数组来存储它不会浪费任何空间,例如下图:

数据结构与算法(4)——优先队列和堆

用数组来表示堆不仅不会浪费空间还具有一定的优势:

  • 每个结点的左孩子为下标i的2倍:left child(i) = i * 2;每个结点的右孩子为下标i的2倍加1:right child(i) = i * 2 + 1
  • 每个结点的父亲结点为下标的二分之一:parent(i) = i / 2,注意这里是整数除,2和3除以2都为1,大家可以验证一下;
  • 注意:这里是把下标为0的地方空出来了的,主要是为了方便理解,如果0不空出来只需要在计算的时候把i值往右偏移一个位置就行了(也就是加1,大家可以试试,下面的演示也采取这样的方式);

二叉堆的相关操作

堆的基本结构

public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;
    public MaxHeap(int capacity){ data = new Array<>(capacity); }
    public MaxHeap(){ data = new Array<>(); }
    // 返回堆中的元素个数
    public int size(){ return data.getSize(); }
    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty(){ return data.isEmpty(); }
    // 返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }
    // 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){ return index * 2 + 1; }
    // 返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){ return index * 2 + 2; }
}

向堆中添加元素和Sift Up

当插入一个元素到堆中时,它可能不满足堆的性质,在这种情况下,需要调整堆中元素的位置使之重新变成堆,这个过程称为堆化(heapifying);在最大堆中,要堆化一个元素,需要找到它的父亲结点,如果不满足堆的基本性质则交换两个元素的位置,重复该过程直到每个结点都满足堆的性质为止,下面我们来模拟一下这个过程:

下面我们在该堆中插入一个新的元素26:

数据结构与算法(4)——优先队列和堆

我们通过索引(上面的公式)可以很容易地找到新插入元素的父亲结点,然后比较它们的大小,如果新元素更大则交换两个元素的位置,这个操作就相当于把该元素上浮了一下:

数据结构与算法(4)——优先队列和堆

重复该操作直到26到了一个满足堆条件的位置,此时就完成了插入的操作:

数据结构与算法(4)——优先队列和堆

对应的代码如下:

// 向堆中添加元素
public void add(E e){
    data.addLast(e);
    siftUp(data.getSize() - 1);
}

private void siftUp(int k){

    while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
        data.swap(k, parent(k));
        k = parent(k);
    }
}

取出堆中的最大元素和Sift Down

如果理解了上述的过程,那么取出堆中的最大元素(堆顶元素)将变得容易,不过这里运用到一个小技巧,就是用最后一个元素替换掉栈顶元素,然后把最后一个元素删除掉,这样一来元素的总个数也满足条件,然后只需要把栈顶元素依次往下调整就好了,这个操作就叫做Sift Down(下沉):

数据结构与算法(4)——优先队列和堆

用最后元素替换掉栈顶元素,然后删除最后一个元素:

数据结构与算法(4)——优先队列和堆

然后比较其孩子结点的大小:

数据结构与算法(4)——优先队列和堆

如果不满足堆的条件,那么就跟孩子结点中较大的一个交换位置:

数据结构与算法(4)——优先队列和堆

重复该步骤,直到16到达合适的位置:

数据结构与算法(4)——优先队列和堆

完成取出最大元素的操作:

数据结构与算法(4)——优先队列和堆

对应的代码如下:

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

// 取出堆中最大元素
public E extractMax(){

    E ret = findMax();

    data.swap(0, data.getSize() - 1);
    data.removeLast();
    siftDown(0);

    return ret;
}

private void siftDown(int k){

    while(leftChild(k) < data.getSize()){
        int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置
        if( j + 1 < data.getSize() &&
                data.get(j + 1).compareTo(data.get(j)) > 0 )
            j ++;
        // data[j] 是 leftChild 和 rightChild 中的最大值

        if(data.get(k).compareTo(data.get(j)) >= 0 )
            break;

        data.swap(k, j);
        k = j;
    }
}

Replace 和 Heapify

Replace这个操作其实就是取出堆中最大的元素之后再新插入一个元素,常规的做法是取出最大元素之后,再利用上面的插入新元素的操作对堆进行Sift Up操作,但是这里有一个小技巧就是直接使用新元素替换掉堆顶元素,之后再进行Sift Down操作,这样就把两次O(logn)的操作变成了一次O(logn):

// 取出堆中的最大元素,并且替换成元素e
public E replace(E e){

    E ret = findMax();
    data.set(0, e);
    siftDown(0);
    return ret;
}

Heapify翻译过来就是堆化的意思,就是将任意数组整理成堆的形状,通常的做法是遍历数组从0开始添加创建一个新的堆,但是这里存在一个小技巧就是把当前数组就看做是一个完全二叉树,然后从最后一个非叶子结点开始进行Sift Down操作就可以了,最后一个非叶子结点也很好找,就是最后一个结点的父亲结点,大家可以验证一下:

数据结构与算法(4)——优先队列和堆

从22这个节点开始,依次开始Sift Down操作:

数据结构与算法(4)——优先队列和堆

重复该过程直到堆顶元素:

数据结构与算法(4)——优先队列和堆

数据结构与算法(4)——优先队列和堆

数据结构与算法(4)——优先队列和堆

完成堆化操作:

数据结构与算法(4)——优先队列和堆

将n个元素逐个插入到一个空堆中,算法复杂度是O(nlogn),而heapify的过程,算法复杂度为O(n),这是有一个质的飞跃的,下面是代码:

public MaxHeap(E[] arr){
    data = new Array<>(arr);
    for(int i = parent(arr.length - 1) ; i >= 0 ; i --)
        siftDown(i);
}

基于堆的优先队列

首先我们的队列仍然需要继承我们之前将队列时候声明的哪个接口Queue,然后实现这个接口中的方法就可以了,之类简单写一下:

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.size(); }
    @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传入自己的比较器,例如:

// 默认为最小堆
PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.add(5);
pq.add(2);
pq.add(1);
pq.add(10);
pq.add(3);

while (!pq.isEmpty()) {
    System.out.println(pq.poll() + ", ");
}
System.out.println();
System.out.println("————————————————————————");

// 使用Lambda表达式传入自己的比较器转换成最大堆
PriorityQueue<Integer> pq2 = new PriorityQueue<>((a, b) -> b - a);
pq2.add(5);
pq2.add(2);
pq2.add(1);
pq2.add(10);
pq2.add(3);

while (!pq2.isEmpty()) {
    System.out.println(pq2.poll() + ", ");
}

LeetCode相关题目整理

23. 合并K个排序链表

数据结构与算法(4)——优先队列和堆

参考答案:(85ms)

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;

    PriorityQueue<ListNode> q = new PriorityQueue<>(Comparator.comparing(node -> node.val));
    for (int i = 0; i < lists.length; i++) {
        if (lists[i] != null) {
            q.add(lists[i]);
        }
    }

    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    while (!q.isEmpty()) {
        tail.next = q.poll();
        tail = tail.next;
        if (tail.next != null) {
            q.add(tail.next);
        }
    }

    return dummy.next;
}

215. 数组中的第K个最大元素

数据结构与算法(4)——优先队列和堆

我的答案:(75ms)

public int findKthLargest(int[] nums, int k) {

    // 正确性判断
    if (0 == nums.length || null == nums || k <= 0 || k > nums.length) {
        return -1;
    }

    // 构造优先队列,默认为最小堆,传入自定义的比较器转换成最大堆
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
    for (Integer num : nums) {
        pq.add(num);
    }
    for (int i = 0; i < k - 1; i++) {
        pq.remove();
    }
    return pq.peek();
}

参考答案:(5ms)

public int findKthLargest(int[] nums, int k) {
    if (nums.length == 1) {
        return nums[0];
    }

    int max = nums[0];
    int min = nums[0];

    for (int i : nums) {
        max = i > max ? i : max;
        min = i < min ? i : min;
    }

    int[] arrs = new int[max - min + 1];

    for (int i : nums) {
        arrs[max - i]++;
    }

    int pos = 0;
    for (int i = 0; i < arrs.length; i++) {
        pos += arrs[i];
        if (pos >= k) {
            return max - i;
        }
    }

    return nums[0];
}

还看到一个简单粗暴的,也是服了:(4ms)

public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length - k];
}

而且我随机生成了一个100万数据的随机数组,来测试这个简单粗暴的方法的效率,发现当数据量上去之后,排序这个操作变得繁琐,我自己测试的时候,上面三个方法,第三个大概比第一个(我自己写的方法)多花仅4倍的时间;

239. 滑动窗口最大值(类似剑指Offer面试题59)

数据结构与算法(4)——优先队列和堆

参考答案:(88ms)

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || k <= 0) return new int[0];
    int[] res = new int[nums.length - k + 1];
    ArrayDeque<Integer> deque = new ArrayDeque<Integer>();

    int index = 0;
    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && deque.peek() < i - k + 1) // Ensure deque's size doesn't exceed k
            deque.poll();

        // Remove numbers smaller than a[i] from right(a[i-1]) to left, to make the first number in the deque the largest one in the window      
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
            deque.pollLast();

        deque.offer(i);// Offer the current index to the deque's tail

        if (i >= k - 1)// Starts recording when i is big enough to make the window has k elements 
            res[index++] = nums[deque.peek()];
    }
    return res;
}

参考答案2:(9ms)

public int[] maxSlidingWindow(int[] nums, int k) {
/*
思想:依次遍历数组,有效范围在长度k内寻找当前最大值,在用result数组来依次存储当前长度K内的最大值;
     若在当前轮中出现新增的nums[end]大于curMax,直接替换即可;
     如果当前轮curMax不是新增的nums[end],在新的范围内重置curMax.
*/
    if (nums.length == 0 || k <= 0)
        return new int[0];
    int curMax = Integer.MIN_VALUE;
    for (int i = 0; i < k; i++) {
        if (nums[i] > curMax)
            curMax = nums[i];
    }
    int[] ans = new int[nums.length - k + 1];
    ans[0] = curMax;

    for (int start = 1; start + k - 1 < nums.length; start++) {
        int end = start + k - 1;
        if (nums[end] > curMax)
            curMax = nums[end];
        else if (nums[start - 1] == curMax) {//新增的不大于curMax,新范围内重置
            curMax = Integer.MIN_VALUE;
            for (int i = start; i <= end; i++) {
                if (nums[i] > curMax)
                    curMax = nums[i];
            }
        }
        ans[start] = curMax;
    }
    return ans;
}

264. 丑数 II(剑指Offer面试题49)

数据结构与算法(4)——优先队列和堆

参考答案:(7ms)

public int nthUglyNumber(int n) {
    // 正确性判断
    if (n < 1 || n > 1690) {
        return -1;
    }
    int[] ugly = new int[n];
    ugly[0] = 1;
    int index2 = 0, index3 = 0, index5 = 0;
    int factor2 = 2, factor3 = 3, factor5 = 5;
    for (int i = 1; i < n; i++) {
        int min = Math.min(Math.min(factor2, factor3), factor5);
        ugly[i] = min;
        if (factor2 == min)
            factor2 = 2 * ugly[++index2];
        if (factor3 == min)
            factor3 = 3 * ugly[++index3];
        if (factor5 == min)
            factor5 = 5 * ugly[++index5];
    }
    return ugly[n - 1];
}

如果采用逐个判断每个整数是不是丑数的解法,直观但不够高效,所以我们就需要换一种思路,我的第一反应就是这其中一定有什么规律,但是尝试着找了一下,没找到...看了看答案才幡然醒悟,前面提到的算法之所以效率低,很大程度上是因为不管一个数是不是丑数,我们都要对它进行计算,接下来我们试着找到一种只计算丑数的方法,而不在非丑数的整数上花费时间,根据丑数的定义,丑数应该是另一个丑数乘以2、3或者5的结果(1除外),因此,我们可以创建一个数组,里面的数字是排好序的丑数,每个丑数都是前面的丑数乘以2、3或者5得到的,也就是上面的算法了..

295.数据流的中位数(剑指Offer面试题41)

数据结构与算法(4)——优先队列和堆

参考答案:(219ms)

public class MedianFinder {

    PriorityQueue<Integer> maxHeap;
    PriorityQueue<Integer> minHeap;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        maxHeap.add(num);
        minHeap.add(maxHeap.poll());
        if (minHeap.size() - maxHeap.size() > 0) {
            maxHeap.add(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        } else {
            return maxHeap.peek();
        }
    }
}

思路:这道题的实现思路有很多,比如我们可以在插入的时候就将每个元素插入到正确的位置上,这样返回中位数的时候就会是一个O(1)的操作,下面列举一张表来说明不同实现的复杂度具体是多少:

数据结构 插入的时间复杂度 得到中位数的时间复杂度
没有排序的数组 O(1) O(n)
排序的数组 O(n) O(1)
排序的链表 O(n) O(1)
二叉搜索树 平均O(logn),最差O(n) 平均O(logn),最差O(n)
AVL树 O(logn) O(logn)
最大堆和最小堆 O(logn) O(logn)

AVL树是一种很高效的数据结构,但是在大多数的语言中都没有现成的实现,所以考虑用最大堆和最小堆,对于一个已经排好序的数据容器,我们可以从中间分开分成两个部分,其中拿P1指向左半部分最大的元素,拿P2指向有半部分最小的元素,如果能够保证数据容器左边的数据都小于右边的数据,那么即使左、右两边内部的数据没有排序,我们仍然可以根据左边最大的数和右边最大的数得到中位数:
数据结构与算法(4)——优先队列和堆
如何快速从一个数据容器中找出最大数呢?我们可以使用最大堆来实现这个数据容器,因为堆顶的元素就是最大的元素;同样我们可以使用最小堆来快速找出一个数据容器中最小数。因此按照这个思路我们就可以使用一个最大堆实现左边的数据容器,使用一个最小堆实现右边的数据容器,但是需要注意的是这两个容器的大小差值不能超过1;

347. 前K个高频元素(类似剑指Offer面试题40)

数据结构与算法(4)——优先队列和堆

参考答案:(131ms)

public List<Integer> topKFrequent(int[] nums, int k) {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    // 保存频率
    for (int num : nums) {
        if (map.containsKey(num)) {
            map.put(num, map.get(num) + 1);
        } else {
            map.put(num, 1);
        }
    }

    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(map::get));
    for (int key : map.keySet()) {
        if (pq.size() < k) {
            pq.add(key);
        } else if (map.get(key) > map.get(pq.peek())) {
            pq.remove();
            pq.add(key);
        }
    }

    LinkedList<Integer> res = new LinkedList<>();
    while (!pq.isEmpty()) {
        res.add(pq.remove());
    }
    return res;
}

692. 前K个高频单词

数据结构与算法(4)——优先队列和堆

参考答案:(72ms)

public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> count = new HashMap();
    for (String word: words) {
        count.put(word, count.getOrDefault(word, 0) + 1);
    }
    List<String> candidates = new ArrayList(count.keySet());
    Collections.sort(candidates, (w1, w2) -> count.get(w1).equals(count.get(w2)) ?
            w1.compareTo(w2) : count.get(w2) - count.get(w1));

    return candidates.subList(0, k);
}

这道题类似于上面的第347题,但是问题出在返回的顺序上,需要自己来定义一个比较器来排序..然后也学到一个写法,就是上面的第一个for循环里,getOrDefault()方法,get√..

参考答案2:(91ms)

public List<String> topKFrequent(String[] words, int k) {
    Map<String, Integer> count = new HashMap();
    for (String word: words) {
        count.put(word, count.getOrDefault(word, 0) + 1);
    }
    PriorityQueue<String> heap = new PriorityQueue<String>(
            (w1, w2) -> count.get(w1).equals(count.get(w2)) ?
                    w2.compareTo(w1) : count.get(w1) - count.get(w2) );

    for (String word: count.keySet()) {
        heap.offer(word);
        if (heap.size() > k) heap.poll();
    }

    List<String> ans = new ArrayList();
    while (!heap.isEmpty()) ans.add(heap.poll());
    Collections.reverse(ans);
    return ans;
}

这个解法就有点儿类似于上面的347题,其实是大同小异,就是自己不会灵活使用比较器而已,学习到了学习到了√...


简单总结

今天算是很有收获的一天,因为这两种数据结构都是自己特别不熟悉的,特别是在刷了一些LeetCode相关题目之后,对这两种数据有了很不一样的认识,特别是堆的应用,这是一种特别适合用来找第k小/大的特殊的数据结构,并且在Java中居然有直接的实现,这可太棒了,而且今天的效率还算挺高的,满足;

欢迎转载,转载请注明出处!
简书ID:
github:
欢迎关注公众微信号:wmyskxz_javaweb
分享自己的Java Web学习之路以及各种Java学习资料