Java和Python中如何使用大顶堆

在数据结构之容器的那篇文章中，我们对于优先队列即堆这种数据结构的底层实现进行了剖析，在实际的

应用中我们不必自己去实现一个堆，主流的编程语言都提供了相关的集合模块，比如Java中的PriorityQueue

类，Python中的heapq模块。但是这两种语言中实现的堆都是小顶堆（根节点的元素小于左右节点元素的值），

当需要使用大顶堆时该如何解决呢？比如典型的最大的K个元素需要用小顶堆解决，但是最小的K个元素不就

是需要使用一个大顶堆来解决了吗！

具体的解决方案如下：

一、通用的方法: 取反

通用的解决方法就是跟语言没有关系的解法，想要构造一个大顶堆，只要保证根节点大于左右节点即可，

所以我们可以将数据取成相反数再添加到小顶堆中去，取出时再对数据进行取反即可实现大顶堆的效果

二、针对Java的方法

优先队列中存放的是基本数据类型的包装类（Integer、Long）或者自定义的包装类。对于基本数据类型

的包装器类，优先队列中元素默认排列顺序是升序排列的，也就是说是小顶堆，但是既然是默认的就可以进

行更改。此外，对于自定义的类来说，需要自己定义比较器，比如：

//自定义比较器，降序排列
public static Comparator<Integer> cmp = new Comparator<Integer>(){
    public int compare(Integer e1,Integer e2){
        return e2 - e1;
    }
} 

//声明对象时
Queue<Integer> pqueue = new PriorityQueue<Integer>();   //不使用比较器，默认升序排列，即小顶堆
Queue<Integer> pqueue = new PriorityQueue<Integer>(cmp); //使用比较器，降序排列，即为大顶堆

//比较器升降序的声明
Comparator<Object> cmp = new Comparator<Object>(){
    public int compare(Object o1,Object o2){
        return o1 - o2    //升序
        return o2 - o1    //降序
    }
}

所以在实际解决问题的过程中如果需要使用大顶堆可以这样声明

PriorityQueue<Integer> pqueue = new PriorityQueue<>((o1,o2) -> o2 - o1);
//实例：对哈希表中的值进行排序
PriorityQueue<Integer> heap = new PriorityQueue<>((o1,o2) ->hashmap.get(o1) - hashmap.get(o2))

最后再补充一个堆的遍历，对于PriorityQueue类来说，当调用iterator()方法时，返回的iterator迭代器实际上

不保证以任何特定的顺序遍历队列的元素；若想按特定顺序遍历，需要先将队列转换成数组，在排序遍历

Queue<Integer> pqueue = new PriorityQueue<>(cmp);   //定义一个优先队列
Object[] retarr = pqueue.toArray();
Arrays.sort(retarr);
//注意，此时retarr数组中的元素的类型是Object类型的，如果想要组成整数数组，需用(int)强制类型转化