如何使用Priority-Queue对键值对按value值进行排序

实现逻辑 #

• 优先队列底层为堆结构，默认多为小顶堆/大顶堆实现，我们只需自定义比较规则，将键值对的value作为比较字段构造小顶堆，即可实现按value从小到大排序
• 依次从队首弹出元素，即可得到符合要求的顺序：[{4,1}->{1,2}->{3,4}->{2,5}]

代码示例 #

Python 实现 #

Python内置heapq模块默认实现小顶堆，将键值对转为(value, key)格式入堆即可自动按value比较：

import heapq

# 原始键值对数据
pairs = [(1, 2), (2, 5), (3, 4), (4, 1)]
heap = []

# 元素入堆
for k, v in pairs:
    heapq.heappush(heap, (v, k))

# 依次出堆得到排序结果
sorted_pairs = []
while heap:
    v, k = heapq.heappop(heap)
    sorted_pairs.append((k, v))

print(sorted_pairs)
# 输出：[(4, 1), (1, 2), (3, 4), (2, 5)]

Java 实现 #

Javautil包自带的PriorityQueue默认是小顶堆，自定义比较器指定按value排序即可：

import java.util.*;

public class PairSort {
    public static void main(String[] args) {
        List<Map.Entry<Integer, Integer>> pairs = Arrays.asList(
                new AbstractMap.SimpleEntry<>(1, 2),
                new AbstractMap.SimpleEntry<>(2, 5),
                new AbstractMap.SimpleEntry<>(3, 4),
                new AbstractMap.SimpleEntry<>(4, 1)
        );

        // 定义优先队列，按value升序排列
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
        pq.addAll(pairs);

        List<Map.Entry<Integer, Integer>> sortedPairs = new ArrayList<>();
        while (!pq.isEmpty()) {
            sortedPairs.add(pq.poll());
        }

        System.out.println(sortedPairs);
        // 输出：[4=1, 1=2, 3=4, 2=5]
    }
}

内容的提问来源于stack exchange，提问作者Ankit