数据结构之堆和优先队列

ゞ浴缸里的玫瑰 2022-02-23 10:38 354阅读 0赞

### 数据结构之堆和优先队列 ###

*  优先队列
 *   *  为什么使用优先队列？
     *  优先队列不同底层实现复杂度分析
 *  堆的基本结构
 *   *  实现一个底层数组的最大堆
     *  向堆中添加元素和Sift Up
     *  取出堆中的最大元素和Sift Down
 *  基于堆的优先队列
 *   *  优先队列的经典问题 LeetCode347
     *  d 叉堆 d-ary heap（用的不多）
     *  索引堆（了解）
     *  二项堆（了解）
     *  斐波那契堆（了解）
     *  广义队列

# 优先队列 #

*  普通队列：先进先出；后进后出
 *  优先队列：出队顺序和入队顺序无关；和优先级相关

## 为什么使用优先队列？ ##

*  动态选择优先级最高的任务执行

## 优先队列不同底层实现复杂度分析 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]

# 堆的基本结构 #

二叉堆是一棵完全二叉树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 1]  
二叉堆的性质

*  堆中某个节点的值总是不大于其父节点的值
 *  最大堆（上述定义，根节点最大），相应的可以定义最小堆（根节点最小）
 *  用数组存储二叉堆时，parent(i) = i/2  
    left child(i) = 2*i  
    right child(i) = 2*i + 1  
    注意这里索引为0的位置是空出来的  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 2]

如果使用索引0  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 3]

## 实现一个底层数组的最大堆 ##

public class MaxHeap<E extends Comparable<E>> { 
    
        // Array为自定义的数组
        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 ##

// 向堆中添加元素
    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));
        }
    }

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

// 取出堆中最大元素
    public E extractMax(){ 
        E ret = findMax();
        data.swap(0, data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return ret;
    }
    
    // 看堆中的最大元素
    public E findMax(){ 
        if (data.getSize() == 0)
            throw new IllegalArgumentException("Can not findMax when heap is empty.");
        return data.get(0);
    }
    
    private void siftDown(int k){ 
        while (leftChild(k) < data.getSize()){ 
            int j = leftChild(k);
            // 判断是否有右节点且右节点的值是否大于左节点的值
            if (j + 1 < data.getSize() &&
                    data.get(j + 1).compareTo(data.get(j)) > 0)
                j = rightChild(k);
            // data[j] 是 leftChild 和 rightChild 中的最大值
            if (data.get(k).compareTo(data.get(j)) >= 0)
                break;
            data.swap(k, j);
            k = j;
        }
    }

*  add和extractMax时间复杂度都是0(logn)

# 基于堆的优先队列 #

public interface Queue<E> { 
    
        int getSize();
        boolean isEmpty();
        void enqueue(E e);
        E dequeue();
        E getFront();
    }

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.size() == 0;
        }
    
        @Override
        public void enqueue(E e) { 
            maxHeap.add(e);
        }
    
        @Override
        public E dequeue() { 
            return maxHeap.extractMax();
        }
    
        @Override
        public E getFront() { 
            return maxHeap.findMax();
        }
    }

## 优先队列的经典问题 LeetCode347 ##

*  在1000000个元素中选出前100名？  
    在N个元素中选出M个元素
    
    使用优先队列，维护当前看到的前M个元素  
    需要使用最小堆
 *  LeetCode第347号问题  
    [https://leetcode-cn.com/problems/top-k-frequent-elements/][https_leetcode-cn.com_problems_top-k-frequent-elements]

import java.util.LinkedList;
    import java.util.List;
    import java.util.PriorityQueue;
    import java.util.TreeMap;
    
    class Solution { 
    
        private class Freq implements Comparable<Freq>{ 
            int e, freq;
    
            public Freq(int e, int freq) { 
                this.e = e;
                this.freq = freq;
            }
    
            @Override
            public int compareTo(Freq another) { 
                if (this.freq < another.freq)
                    return -1;
                else if (this.freq > another.freq)
                    return 1;
                else
                    return 0;
            }
        }
    
        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);
            }
    
            // 我们可以将map中的键值数据对做成可比较的 Freq 类型的优先队列
            // 承载的元素类型一定要是可比较的
            // 注意这里的PriorityQueue用的是我们自己定义的不是util下的
            PriorityQueue<Freq> pq = new PriorityQueue<>();
            for (int key : map.keySet()){ 
                if (pq.size() < k)
                    pq.add(new Freq(key, map.get(key)));
                else if (map.get(key) > pq.peek().freq){ 
                    pq.remove();
                    pq.add(new Freq(key, map.get(key)));
                }
            }
    
            LinkedList<Integer> res = new LinkedList<>();
            while (!pq.isEmpty())
                res.add(pq.remove().e);
            return res;
        }
    }

不使用Freq辅助类的方式（只使用Map）

import java.util.*;
    
    class Solution { 
    
        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<>(new Comparator<Integer>() { 
                @Override
                public int compare(Integer a, Integer b) { 
                    return map.get(a) - map.get(b);
                }
            });
            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;
        }
    }

## d 叉堆 d-ary heap（用的不多） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 4]

## 索引堆（了解） ##

## 二项堆（了解） ##

## 斐波那契堆（了解） ##

## 广义队列 ##

*  普通队列
 *  优先队列
 *  栈，也可以理解成是一个队列

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]: /images/20220223/570503c46ad1440192cf528d4b2e93a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 1]: /images/20220223/c1be50f2bd8a44bc916be837a7b94b7a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 2]: /images/20220223/2a3477e76a6c43209cc8900fd6caa417.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 3]: /images/20220223/91f179b56bb2474eb21fe2bae16fff01.png
[https_leetcode-cn.com_problems_top-k-frequent-elements]: https://leetcode-cn.com/problems/top-k-frequent-elements/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 4]: /images/20220223/794d6ebaeff845faa4004188a5c22b23.png