leetcode-堆

java中堆，不管是大根堆还是小根堆，都是优先队列PriorityQueue

1.创建大根堆和小根堆

（1）创建小根堆（堆顶元素最小）：

PriorityQueue queue=new PriorityQueue();
 
//向堆里面添加元素
queue.add(0);
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
queue.add(6);
 
//输出堆中全部元素
while(queue.isEmpty()==false)
{
  System.out.println(queue.remove());
}
//输出：0，1，2，3，4，5，6，即小根堆每次弹出当前堆里面最小的元素

（2）创建大根堆

PriorityQueue queue=new PriorityQueue(
                                        { 
                                           public int compare(Integer a,Integer b)
                                           {
                  //这里如果是return a-b就是生成一个小根堆，return b-a就是生成一个大根堆
                                              return b-a;
                                           }                                      
                                        }
                                     );
 
//向堆里面添加元素
queue.add(0);
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
queue.add(6);
 
//输出堆中全部元素
while(queue.isEmpty()==false)
{
  System.out.println(queue.remove());
}
//输出6,5,4,3,2,1,0即大根堆每次弹出当前堆里面最大的元素

事实上还有一种更简洁的创建大根堆的方式：

PriorityQueue<Integer> queue=new PriorityQueue<Integer>(
                                                        (a,b)->b-a
                                                       )

2.堆的常用方法：

（1)通过索引获取堆里面的元素

 queue[0]=3, queue[1]=5,queue[2]=10........

(2)向堆内添加元素：add

弹出堆顶元素：remove

返回堆顶元素（不删除）：peek

3.例题：用最大堆，最小堆来解决TopK问题：

（1）小根堆：力扣703，找出数组中第k大的数

暴力法的话是通过不了所有测试用例的

 
class KthLargest 
{
    int k;
    ArrayList<Integer> a=new ArrayList();
    public KthLargest(int k, int[] nums)
    {
       this.k=k;
       for(int i:nums)
       {
           a.add(i);
       }
    }
    
    public int add(int val) 
    {
        a.add(val);
        int[] result=new int[a.size()];
        int j=0;
        for(int temp:a)
        {
            result[j]=temp;
            j++;
        }
        Arrays.sort(result);
        return result[a.size()-k];
    }
}

 小根堆法：

class KthLargest 
{
    int k; 
   // 创建一个小根堆（即堆顶元素最小）
    PriorityQueue<Integer> queue=new PriorityQueue<Integer>();
   //构造函数：传入k值和数组（后面调用add函数会往这个数组里面添加元素）
    public KthLargest(int k, int[] nums) 
    {
        this.k=k;
        
        //这道题要维护一个size为k的堆 
        //在堆的长度小于k之前，随便添加
        //当堆的长度等于k的时候，此时堆顶元素是这k个数中最小的
        //由于我们是想要找出数组中第k大的，所以要添加新的元素进堆中时，如果新的数比堆顶元素大，就可以进堆里面（先把堆顶元素弹出，然后再把这个新的元素添加进堆中），如果新的数不比堆顶元素大，就不添加进堆里
        for(int i=0;i<nums.length;i++)
        {
            if(queue.size()<k)
            {
                queue.add(nums[i]);
            }
            else
            {
                if(nums[i]>queue.peek())
                {
                    queue.remove();
                    queue.add(nums[i]);
 
                }
            }
        }
    }
  
    public int add(int val)
    {
       if(queue.size()<k)  queue.add(val);
       else
       {
             if(val>queue.peek())
             {
               queue.remove();
               queue.add(val);
            }
       }
       return queue.peek();
    }
}

（2）大根堆的题：

力扣1046 最后一块石头的重量

class Solution 
{
    public int lastStoneWeight(int[] stones)
    {
        //构造一个大根堆
        PriorityQueue<Integer> queue=new PriorityQueue<Integer>((a,b)->b-a);
        //将数组里的元素放进大根堆
        for(int stone:stones)
        {
            queue.add(stone);
        }
        while(queue.size()>1)//只要堆里面的元素有两个以上
        {
           int a=queue.remove();//取出堆顶元素，即最大的元素
           int b=queue.remove();//继续取出堆顶元素，第二大的元素
           int c=Math.abs(a-b);
           queue.add(c);
        }
        //跳出循环，则堆里面只有一个元素了
        return  queue.remove(); 
    }
}

（3）不止找一个数，而是找出若干个数（那就queue.remove()若干次，弹出若干次堆顶元素就行）

力扣 最小的k个数

暴力法：

class Solution 
{
    public int[] getLeastNumbers(int[] arr, int k) 
    {
        Arrays.sort(arr);
        int[] result=new int[k];
        for(int i=0;i<k;i++)
        {
            result[i]=arr[i];
        }
        return result;
    }
}

小根堆的方法：

class Solution 
{
    public int[] getLeastNumbers(int[] arr, int k) 
    {
       PriorityQueue<Integer> queue=new PriorityQueue();
       for(int i:arr)
       {
           queue.add(i);
       }
       int[] result=new int[k];
       for(int j=0;j<k;j++)
       {
           result[j]=queue.remove();
       }
       return result;
    }
}

（4）前k个高频元素

力扣347

class Solution
{
   public int[] topKFrequent(int[] nums, int k)
    {
        HashMap<Integer,Integer> map=new HashMap();
        for(int num:nums)
        {
            map.put(num,map.getOrDefault(num,0)+1);
        }
       //构建一个特殊的小根堆，小根堆里面存的是hashmap的key，比较的依据是这这个key对应的value值，也就是说堆顶元素是这个堆中所有key中，对应的value最小的那个key
        PriorityQueue<Integer> queue=new PriorityQueue(
                                                        new Comparator<Integer>() 
                                                        {
                                                          @Override
                                                          public int compare(Integer a, Integer b)
                                                          {
                                                            return map.get(a)-map.get(b);
                                                          }
                                                         }
                                                       );//构建一个小根堆
        int size=0;
  //往小根堆里面添加key，在堆的容量没有达到k之前，随便加
  //一旦容量达到k，想要将key再加入堆，就必须这个key对应的value值要大于堆顶元素对应的value值
        for(int num:map.keySet())
        {
            if(size<k)   queue.add(num);
            else//当小根堆的容量超过k
            {
                if(map.get(num)>map.get(queue.peek()))
                {
                    queue.remove();
                    queue.add(num);
                }
            }
            size++;
        }
        int[] result=new int[queue.size()];
        int temp=queue.size();
        for(int i=0;i<temp;i++)
        {
            result[i]=queue.remove();
        }
        return result;
    }
}