乐趣区

关于数据结构:优先级队列-PriorityQueue

jiezi

1. 优先级队列是什么？？

首先，优先级队列是一个队列，队列所有的性质，它也有。

其次，优先级队列每次取出的是优先级最高的元素。

优先级队列的外部是用 堆来保护的。将优先级最高的排在后面。

2. 什么时候用这个队列呢？？

看完优先级队列的定义，如同看懂了，又如同没看懂。这队列，什么用它呢？

1）排序的对象和排序时比拟的对象

常见的排序办法（插入、快排等），排序的对象和比拟的对象是一样的，依据数自身的大小进行排序。

优先级队列能够对 排序对象和比拟对象雷同 的进行排序，也能够对 排序的对象和排序时比拟的对象不同 的进行排序。

排序的对象和排序时比拟的对象不同的一种状况是对 Map 排序。在 Map 中，依照值 Value 对 Key 进行排序。这时，排序的对象是 Key，比拟的对象是 Value。

2）堆

优先级队列的外部是用 堆来保护的。所以，也能够把优先级队列当做堆来用。须要用堆的时候，用优先级队列试试看。

3. 对一数组排序

int[] arr = {3, 7, 5, 1, 8};
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int t : arr) {queue.offer(t);
    System.out.println("queue =" + queue);
}

输入后果：

queue = [3]
queue = [3, 7]
queue = [3, 7, 5]
queue = [1, 3, 5, 7]
queue = [1, 3, 5, 7, 8]

由 queue = [3, 7, 5] 能够看出，在排序时，queue 尽管也是依照整数的天然序来排的，然而不是依照递增的程序（队列中的元素并不是始终是递增排列），是按堆寄存的。

上面，将优先级队列的大小设置为 3，看一下优先级队列的变动

int[] arr = {3, 7, 5, 1, 8};
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int cur : arr) {queue.offer(cur);
    if (queue.size() > 3){int t = queue.poll();
        System.out.print("poll =" + t);
    }
    System.out.println("queue =" + queue);
}

输入后果：

queue = [3]
queue = [3, 7]
queue = [3, 7, 5]
poll = 1 queue = [3, 7, 5]
poll = 3 queue = [5, 7, 8]

从后果中能够看出，每次弹出的是最小的值。

4. Map 按值排序

有两种计划实现 Map 依据值 Value 对键 Key 排序：

  • 队列中存 key
  • 队列中存 Map.entry

4.1 队列中存 key

Map<Integer, Integer> map = new HashMap<>();
// map 中存入值，这里不再写

// 创立优先级队列，同时定义比拟规定
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){public int compare(Integer a, Integer b) {return map.get(a) - map.get(b);  // 按值 Value 升序排
    }
});

// 退出队列，并排序
for (Integer key: map.keySet()) {queue.offer(key);  // 退出队列的同时，会排序
}

/*************************************************************************/
// 创立优先级队列时，还能够简化为上面的形式
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> {return map.get(a) - map.get(b);
});

4.2 队列中存 Map.entry

把 Map 中的 <key,value> 看作一个整体，通过 Map.entry<> 就能够取出。与下面一种办法的不同就是，把 Integer 变成了 Map.entry<Integer, Integer>，其余的，临时没看进去。

Map<Integer, Integer> map = new HashMap<>();
// map 中存入值，这里不再写

// 创立优先级队列，同时定义比拟规定
PriorityQueue<Map.entry<Integer, Integer>> queue = new PriorityQueue<>((a, b) -> {return a.getValue() - b,getValue();});

// Set<Map.entry<Integer, Integer>> set = map.entrySet();
// 退出队列，并排序
for (Map.entry<Integer, Integer> entry: map.entrySet()) {queue.offer(entry);  // 退出队列的同时，会排序
}
退出移动版