“堆与优先队列”

堆和优先队列

什么是优先队列

  • 普通队列：先进先出；后进后出
  • 优先队列：出对顺序和入队顺序无关；和优先级有关

优先队列的实现

  • 通常情况下，我们可以使用两种方法实现优先队列。
    • 1、我们直接采用普通线性结构，诸如数组或者链表。这样的话，入队操作变得非常简单，只是O(1)的复杂度，但是出队操作就是O(n)的复杂度，优先级最高我们可以理解为取出最大/最小元素。
    • 2、我们采用顺序线性结构，这里的顺序线性结构是指我们所有的元素维持着一种顺序。这样我们如果需要取出最大/最小元素，只需要O(1)的时间复杂度，但是我们如果要入队一个元素的话，则需要找一个合适的位置插入，即入队操作的复杂度为O(n)。
    • 3、我们在这里使用堆来实现优先队列，这时候不管是入队操作还是出队都是都是O(logn)的时间复杂度，并且是在最坏情况下都是O(logn)，这表明堆是一种非常高效的数据结构。

堆的基本结构

其实一个堆也是一个二叉树，接下来我们主要是实现一个二叉堆。

二叉堆是一颗完全二叉树，二叉堆中一个非常重要的性质就是：堆中某个节点的值总是不大于其父节点的值。

即二叉堆的根节点的元素是最大的，这就非常方便了。以这种方式定义的堆叫做“最大堆”。

同理，我们也可以定义出来最小堆，即根元素的节点是最小值。

heap

如上图所示，我们这样定义一个二叉堆。即我们可以用一个数组来存储二叉堆。那么接下来问题的关键就是，我们如何来找到这些索引呢，通过上面的图，我们不难发现，某节点的左孩子的索引就是该节点索引的两倍，该节点的右孩子就是该节点索引的两倍+1.

用数组来定义一个二叉堆的好处还不止上面这些，我们要想得到某个节点的父亲节点，同样也很方便，直接为该节点的索引值/2.

以上方式我们是把初始索引定义成1来计算，但是为了计算机语言的方便，我们还是将初始位置定义为0，即我们只需要做一点点的偏移即可。

heap2

如上图所示，上述我们可以通过数学归纳法来证明，在这里就不详细展开了。就这样我们就实现了一个基于数组实现的二叉堆！

在这里，首先我引入自己以前定义的一个动态数组实现，由于比较简单，在这里就不详细说明了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
public class Array<E> {

    private E[] data;
    private int size;

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

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

    public int getSize() {
        return size;
    }

    public int getCapacity() {
        return data.length;
    }

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

    public void addLast(E e) {
        add(size, e);

    }

    public void add(int index, E e) {

        if (index < 0 || index > size)
            throw new IllegalArgumentException("add fail");
        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++;

    }

    public void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++)
            newData[i] = data[i];
        data = newData;

    }

    public void set(int index, E e) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("index is illegal");
        data[index] = e;

    }

    public boolean contains(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e))
                return true;
        }
        return false;

    }

    public int find(E e) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e))
                return i;
        }
        return -1;

    }

    public E remove(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("index is illegal");
        E del = data[index];
        for (int i = index + 1; i < size; i++)
            data[i - 1] = data[i];

        size--;
        data[size] = null;

        if (size == data.length / 4)
            resize(data.length / 2);

        return del;

    }

    public E removeFirst() {
        return remove(0);
    }

    public E removeLast() {
        return remove(size - 1);
    }

    public void addFirst(E e) {
        add(0, e);
    }

    public void removeElement(E e) {
        int index = find(e);
        if (index != -1)
            remove(index);
        else {
            System.out.println("不存在此元素");
        }

    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (int i = 0; i < size; i++) {
            sb.append(data[i]);
            if (i != size - 1)
                sb.append(", ");

        }

        sb.append(']');
        return sb.toString();

    }

    E get(int index) {
        if (index < 0 || index >= size)
            throw new IllegalArgumentException("index is illegal");
        return data[index];
    }
   public void swap(int i,int j){
        if(i<0||i>=size ||j<0||j>=size)
            throw new IllegalArgumentException("index is illegal");
        E t=data[i];
        data[i]=data[j];
        data[i]=t;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;

    /**
     * 构造函数
     * @param capacity
     */
    public MaxHeap(int capacity){
        data=new Array<>(capacity);

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

    /**
     * 返回元素的个数
     * @return
     */
    public int size(){
        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  does not hava parent");

        return (index-1)/2;
    }

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

        return 2*index+1;

    }

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

    }

   

    /**
     * 向堆中添加元素
     * @param e
     */
    public void add(E e){
        //先向数组尾部添加元素
        data.addLast(e);

        siftUp(data.getSize()-1);

    }

    /**
     * 为了维护完全二叉树的性质，我们添加元素应该在最后一个元素的右边进行添加。
     * 但是如果这个元素大于他的父亲节点
     *  那么就破坏了堆的性质，此时我们应该把这个元素提上去，我们称之为"sift up"
     * @param k
     */
    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);
        }
    }

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

    }

    /**
     * 取出堆中最大元素
     * @return
     */
     public E extractMax(){
         E ret=findMax();
       //首先将堆中最后一个元素和最大元素交换位置
         data.swap(0,data.getSize()-1);
         //将最大元素删除
         data.removeLast();
         siftDown(0);
         return ret;

     }

    /**
     * 下沉操作 siftDown
     * @param k
     */
     private void siftDown(int k){
         while(leftChild(k)<data.getSize()){
             //k的左孩子
             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){
                     //此时k位置的元素是最大的
                     break;
                 }
                     data.swap(j,k);
                     k=j;
             }
         }
     }

    /**
     * 取出最大元素，并且替换成元素e
     */
    public E replace(E e){
        E ret=findMax();
        //直接将堆中最大元素设置为e
        data.set(0,e);
        //进行下沉操作
        siftDown(0);
        return ret;

     }

    /**
     * heapify,原地起堆
     * @param arr
     */
     public MaxHeap(E arr[]){
        data=new Array<>(arr);
        //最后一个非叶子节点
        for(int i=parent(arr.length-1);i>=0;i--){
            siftDown(i);
        }

     }


}

相信，有了上面对最大堆的分析，下面我们要实现一个以最大堆为基础的优先队列就很容易了！

  • 首先我们定义出队列的接口
1
2
3
4
5
6
7
8
9
10
11
public interface Queue<E> {

    int getSize();
    boolean isEmpty();
    //入队
    void enqueue(E e);
    //出队
    E dequeue();
    //查看队首元素
    E getFront();
}
  • 然后定义优先队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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 void enqueue(E e) {
         maxHeap.add(e);
    }

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

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

就这样，我们就很简单的实现了一个最大堆。

优先队列的经典问题

接下来，我们将引入一个优先队列的经典问题。

在1000000个元素中取出前100名，更加常见的情形就是在N个元素中选出前M个元素。

我们最容易想到的方法就是对这1000000个元素先排序，我们采用高级的排序算法，例如归并排序或者快速排序，都可以达到NlogN的复杂度。

但是，我们如果用优先队列的话，可以达到NlogM的时间复杂度，一般情况下M是远小于N的。这样就帮助我们大大改善了性能。

以Leetcode 347、前K个高频元素为例

https://leetcode-cn.com/problems/top-k-frequent-elements/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        //元素，频次
        Map<Integer,Integer> map=new HashMap<>();
        for(Integer num:nums){
            if(map.containsKey(num))
                 map.put(num,map.get(num)+1);
                 else
                 map.put(num,1);
        }
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new Comparator<Integer>() {
         //定义优先级，我们定义频率低为优先级高
        @Override
        public int compare(Integer o1, Integer o2) {
            return map.get(o1)-map.get(o2);
        }
    });
    for(int key:map.keySet()){
        if(priorityQueue.size()<k){
            priorityQueue.add(key);
            
        }else if( map.get(key)>map.get(priorityQueue.peek())){
            priorityQueue.remove();
            priorityQueue.add(key);
        }
    }
    List<Integer>list=new ArrayList<>();
    while(!priorityQueue.isEmpty()){
        list.add(priorityQueue.remove());
    }
    return list;
}
}
  • 这道题的关键就是我们如何理解优先级和频次的关系。
    • 我们利用Map映射存储元素，和他的频次。
    • 在这里，我们定义为频次低，为优先级高，这就方便了我们取出频次低的元素，并且将频次高的元素入队，这样，最后剩下的元素，都是频次高的，即我们可以取出前k个频次高的元素。
赏

谢谢你请我喝奶茶

微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家