优先队列和堆

发表于 | 分类于 | | 热度: ℃
字数统计: 1.9k | 阅读时长 ≈ 8

什么是优先队列

普通队列是先进先出的数据结构，而对于优先队列则是以优先级为准则的，优先级越大的先出队。就比如医院挂急诊的优先级大于普通排队就诊的，比如在游戏中自动打怪设置，当地图中出现级别高的野怪先打级别高的等等。

如果我们实现优先队列使用普通的线性结构，那么当我们入队的时候时间复杂度就是O(1)，但出队的时候我们的时间复杂度就是O(n)，因为出队的时候是优先级最高的出队，所以我们需要遍历整个队列寻找优先级最高的元素。

如果我们实现优先队列使用的顺序线性结构，那么我们出队的时间复杂度就是O(1)，因为原本队列就是依靠优先级排列的，这时候我们出队只需要取出第一个元素就行了。但是，当我们进行入队操作的时候我们就需要维持队列的顺序性，这时候入队就是O(n)的时间复杂度了。

相较于前面两种实现方法，使用堆来实现优先队列的入队操作和出队操作都是O(logn)的时间复杂度，这是非常快的。

优先队列的实现方法的时间复杂度比较

什么是堆

堆其实就是按照层由上到下，由左到右的树结构，其中可以分为最大堆和最小堆(根元素为最大的元素就是最大堆)

堆的数据结构

当我们使用数组实现堆的时候，这时候父子节点的索引值存在着一种数学关系。

堆的数据结构

当索引从0开始的时候，父亲节点的索引就是子节点的索引-1再除以2(取整的性质，所以左右孩子都一样)，相应的，左孩子就是父亲节点索引乘2+1，右孩子则是左孩子+1。

通过这个关系我们就可以很轻松的使用数组存储二叉堆。

最大堆的代码实现

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
/**
 * @author Lin
 * @date 2019-05-19 17:03
 **/
public class MaxHeap<E extends Comparable<E>> {

  private Array<E> array;

  public MaxHeap(int capacity){
    array = new Array<>(capacity);
  }

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

  public int size(){
    return array.getSize();
  }

  public boolean isEmpty(){
    return array.isEmpty();
  }

  /**
   * 返回index索引的父亲节点的索引
   * @param index 索引
   * @return 父亲节点的索引
   */
  private int parent(int index){
    if (index == 0){
      throw new IllegalArgumentException("index-0 doesn't have parent");
    }
    return (index - 1) / 2;
  }

  /**
   * 获取节点左孩子的索引
   * @param index 节点索引
   * @return 左孩子索引
   */
  private int leftChild(int index){
    return index * 2 + 1;
  }

  /**
   * 获取右孩子索引
   * @param index 费节点的索引
   * @return 右孩子的索引
   */
  private int rightChild(int index){
    return index * 2 + 2;
  }

  public void add(E e){
    array.addLast(e);
    siftUp(array.getSize() - 1);
  }

  /**
   * 堆中元素上浮
   * @param index 指定上浮元素
   */
  private void siftUp(int index) {
    //当父元素比指定元素小的时候交换，如果交换则继续去比较
    while(index > 0 && array.get(parent(index)).compareTo(array.get(index)) < 0){
      array.swap(index, parent(index));
      index = parent(index);
    }
  }

  public E getMax(){
    if (array.getSize() == 0){
      throw new IllegalArgumentException("The heap is empty");
    }
    return array.getFirst();
  }

  public E extractMax(){
    E temp = getMax();

    //将堆顶元素和堆的最后一个元素交换位置
    array.swap(0, array.getSize() - 1);
    //删除最后一个元素(原来的堆顶元素)
    array.removeLast();

    siftDown(0);

    return temp;
  }

  /**
   * 堆中元素的下沉
   * @param index 需要下沉的索引
   */
  private void siftDown(int index) {

    //判断index合法性
    if (index < 0 || index > array.getSize()){
      throw new IllegalArgumentException("Index is illegal");
    }

    //遍历堆，条件是左孩子存在
    while (leftChild(index) < array.getSize()){
      int j = leftChild(index);

      //如果右孩子存在则比较左右孩子，将大的索引赋值给j
      if (j + 1 < array.getSize() && array.get(j).compareTo(array.get(j + 1)) < 0){
        j ++;
      }

      if (array.get(index).compareTo(array.get(j)) >= 0){
        //如果需要下沉的节点已经比左右孩子最大的大了直接break
        break;
      }else {
        array.swap(index, j);
        index = j;
      }
    }
  }
}

最大堆的入队和出队的操作

在上述代码中，其他操作都是最基本的，但是对于插入和移除元素就会稍微复杂了。

当我们插入元素的时候，我们需要在数组最后插入元素，但是插入元素的大小不一定性决定着我们需要重新排列这个二叉堆使它还满足最大堆的特性。所以我们只需要和插入元素的父亲节点比较，如果我们插入的节点大于父亲节点了则交换，然后再和交换后的父亲节点比较，一直到根节点或者子节点小于父亲节点了。

当我们移除元素的时候，其实就是移除堆中的顶层元素，这时候如果直接移除的话，那么堆就会变成两个堆，这样整合成一个堆的话太复杂，这时候我们可以将堆底元素和堆顶元素交换，然后再删除堆底元素(原来堆顶元素),然后我们通过现在堆顶元素和它的左右孩子最大的作比较，如果小于最大的那么就交换，然后再次和左右孩子做比较直到自己没有左右孩子为止。

使用堆来实现优先队列

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
/**
 * @author Lin
 * @date 2019-05-19 20:48
 **/
 //优先队列中的元素必须是可比较的
 //其他的方法直接复用堆中的方法就行了
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

  private MaxHeap<E> maxHeap;

  public PriorityQueue(){
    maxHeap = new MaxHeap<>();
  }

  @Override
  public void enqueue(E e) {
    maxHeap.add(e);
  }

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

  @Override
  public int getSize() {
    return maxHeap.size();
  }

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

  @Override
  public boolean isEmpty() {
    return maxHeap.isEmpty();
  }
}

关于LeetCode中优先队列的问题

题目

分析: 我们需要获取频率出现最高的元素，我们需要将频率和元素(key)存入一个map中，然后遍历这个数组，当map不存在相应key的数组中的元素，则将value设置为1，如果存在value++。

然后我们遍历这个map中的key，将key存入优先队列中(容量为k)，当k的容量存满了并且还需要添加元素到优先队列的时候就判断优先队列优先度最高的元素和插入元素的优先度，如果插入元素的优先度高于现在队列中最高的，那么就将元素插入到队列中，知道整个map遍历完。

代码实现:

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
class Solution {

  //定义一个Frequency类
  //存放key和频率
  private class Frequency{
    public int k, freq;

    public Frequency(int k, int freq){
      this.k = k;
      this.freq = freq;
    }

  }

  //实现比较器
  private class FrequencyCompartor implements Comparator<Frequency>{

    @Override
    public int compare(Frequency o1, Frequency o2) {
      return o1.freq - o2.freq;
    }
  }

  public List<Integer> topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>(20);
    //遍历数组并且将频率信息存入map中
    for (Integer integer : nums){
      if (!map.containsKey(integer)){
        map.put(integer, 1);
      }else {
        map.put(integer, map.get(integer) + 1);
      }
    }

    PriorityQueue<Frequency> priorityQueue = new PriorityQueue<>(new FrequencyCompartor());

    //遍历map的key，并且将频率最高的放入优先队列中
    for (int key: map.keySet()) {
      if (priorityQueue.size() < k){
        priorityQueue.add(new Frequency(key, map.get(key)));
      }else if (map.get(key) > priorityQueue.peek().freq){
        priorityQueue.poll();
        priorityQueue.add(new Frequency(key, map.get(key)));
      }
    }

    LinkedList<Integer> linkedList = new LinkedList<>();

    while (!priorityQueue.isEmpty()){
      linkedList.add(priorityQueue.poll().k);
    }

    return linkedList;

  }
}
-------------本文结束感谢阅读-------------
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多