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

37次阅读

共计 1996 个字符,预计需要花费 5 分钟才能阅读完成。

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

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

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

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

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

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

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

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

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

排序的对象和排序时比拟的对象不同的一种状况是对 Map 排序。在 Map 中,依照值 ValueKey 进行排序。这时,排序的对象是 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);  // 退出队列的同时,会排序
}

正文完
 0