优先级队列 堆排序 TopK 问题（非常重要） （数据结构）

1 二叉树的顺序存储

2 下标关系

已知父亲节点下标，求孩子节点下表

1 左孩子下标=2*parent+1;

2 右孩子下标=2*parent+2;

已知孩子节点下表，求父亲节点下标 （不分左右孩子下标）

3 堆

概念：1 逻辑上是一颗完全二叉树

2 对物理上是保存在数组中，相当于把二叉树层序遍历的结果放到数组中

3 每棵树的根节点都小于孩子节点，叫小根堆。每颗树的根结点都大于孩子节点，叫大根堆（优先级队列默认的是小堆）；

但是左右孩子的关系是不确定的

1 如何将一个二叉树调整成大堆呢

从最后一棵子树进行调整，进行向下调整，每调整一棵子树时，都要保证向下调整，直到孩子结点的值大于数组的长度（从每颗树的根节点向下调整）；

没调整一个根节点时，让parent减减即可；

2 入堆操作

1） 首先必须判断数组长度是否满了

2）放到数组的最后一个位置

3） 进行向上调整（因为之前已经是一个大堆，调整也没那么麻烦）

3 出当前最大的元素

让当前的元素和数组的最后一个元素交换位置，然后再从数组的0下标开始向下调整

上代码

class hello {
    static class Heap
    {
        int arr1[];
        int usedsize;

        public Heap() {
            this.arr1 = new int[10];
        }

        public void createbig()
        {
            for(int i=(arr1.length-1-1)/2;i>=0;i--)
            {
                downadjust(i,usedsize);//这里的代码是调整每一个节点，要传数组的长度，因为要判断是否有右节点和向下调整的限度
            }
        }
        public void downadjust(int front,int len)
        {
             int parent=front;
             int child=2*parent+1;
             while(child<len) {
                 if (child + 1 < len && arr1[child] < arr1[child + 1])//判断是否有右孩子并保证当前child指向的是左右孩子中最大的元素
                 {
                     child++;
                 }
                 if (arr1[child] > arr1[parent]) {
                     int temp=arr1[child];
                     arr1[child]=arr1[parent];
                     arr1[parent]=temp;
                     parent = child;
                     child = 2 * parent + 1;
                 } else {
                     break;
                 }
             }
        }
        public void upjust(int child)
        {
            int parent=(child-1)/2;
            while(child>0)
            {
                if(arr1[child]>arr1[parent])
                {
                   int temp=arr1[child];
                   arr1[child]=arr1[parent];
                   arr1[parent]=temp;
                    child=parent;
                    parent=(child-1)/2;
                }
                else
                {
                    break;
                }
            }
        }
        public boolean isfull()
        {
            return usedsize== arr1.length;
        }
        public void push(int data)
        {   if(isfull())
        {
            this.arr1=Arrays.copyOf(arr1,2*arr1.length);
        }
            arr1[usedsize]=data;
            usedsize++;
            upjust(usedsize-1);
        }
        public void pop()//出当前的堆顶元素
        {
            int temp=arr1[0];
            arr1[0]=arr1[usedsize-1];
            arr1[usedsize-1]=temp;
            usedsize--;
            downadjust(0,usedsize);
        }
        public Boolean isnull()
        {
            return usedsize==0;
        }
        public int top()
        {  if(isnull())
        {
            throw new RuntimeException("堆里面没有元素");
        }
            return arr1[0];
        }
        public void show()
        {
            for(int i=0;i<usedsize;i++)
            {
                System.out.println(arr1[i]);
            }
        }
    }

2 堆排序

  public void heartsort()
        {
            int index=usedsize-1;
            while(index!=0)//让顶上的元素与末尾元素交换，在对啊让arr1[0]进行向上调整
            {
                int temp=arr1[0];
                arr1[0]=arr1[index];
                arr1[index]=temp;
                downadjust(0,index);
                index--;
            }
        }

3 TOPK问题

例如 有十万个数据，你给我找前十个最大的数据？

** 将前10个建立一个大小为10的小堆，遍历剩下的元素如果元素比堆顶元素大，就入堆，同时删除堆顶元素，再将剩下的元素调整成一个小堆；**

上代码

static void TopK(int[]arr1)
      {
          PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(3, new Comparator<Integer>() {
              @Override
              public int compare(Integer o1, Integer o2) {
                  return o1-o2;//小堆是o1-o2,大堆是o2-o1
              }
          });
          for(int i=0;i<arr1.length;i++)
          {
              if(priorityQueue.size()<3)
              {
                  priorityQueue.add(arr1[i]);
              }
              else
              {
                  int num=priorityQueue.peek();//先找到当前堆顶的元素，如果这个元素比数组元素小，就去除对顶元素，放数组元素入队列
                  if(arr1[i]>num)
                  {
                      priorityQueue.poll();
                      priorityQueue.add(arr1[i]);
                  }
              }
          }
          System.out.println(priorityQueue);
      }
    public static void main(String[] args) {
        int arr1[]={34,23,89,78,123,67,87,55};//写一个topk问题，找到数组中8个数中前三个最大的
        TopK(arr1);

    }

下面来做几个面试题

1

代码

 class Hello{
    public static void main(String[] args) {
      int arr1[]={1,7,11};
      int arr2[]={2,4,6};
      PriorityQueue<List<Integer>> priorityQueue=new PriorityQueue<>(3, new Comparator<List<Integer>>() {
        @Override
        public int compare(List<Integer> o1, List<Integer> o2) {
          return o2.get(0)+o2.get(1)-o1.get(0)-o1.get(1);
        }
      });
      for(int i=0;i<arr1.length;i++){
        for(int j=0;j<arr2.length;j++) {
          if(priorityQueue.size()<3)
          {
            ArrayList list=new ArrayList<>();
            list.add(arr1[i]);
            list.add(arr2[j]);
            priorityQueue.add(list);
          }
          else
          {
            int top=priorityQueue.peek().get(0)+priorityQueue.peek().get(1);
            if(top>arr1[i]+arr2[j])
            {
              priorityQueue.poll();
              ArrayList list=new ArrayList<>();
              list.add(arr1[i]);
              list.add(arr2[j]);
              list.addAll(list);
            }
          }
        }
      }
      List<List<Integer>> list1=new ArrayList<>();
      for(int k=0;k<3&&!priorityQueue.isEmpty();k++)
      {
        list1.add(priorityQueue.poll());
      }
      System.out.println(list1);

    }

放到优先级队列的规则：次数优先，次数相同，比较哪个字母在前面

本题是对单词出现的次数建立小堆，况且优先级队列方的不单单是单词出现的次数，而是放的是单词加次数，放的是map.entry<String,Integer> 类型

class hello {
    public static void main(String[] args) {
        String[] arr1={"i","love","leetcode","i","love","coding"};
        Map<String,Integer> map=new HashMap<>();
        for(String string:arr1)
        {
            if(!map.containsKey(string))
            {
                map.put(string,1);
            }
            else
            {
                int count=map.get(string);
                count++;
                map.put(string,count);

            }
        }
        System.out.println(map);
        PriorityQueue<Map.Entry<String,Integer>> priorityQueue=new PriorityQueue<>(2, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                return o1.getValue()- o2.getValue();
            }
        });
        for(Map.Entry<String,Integer> entry: map.entrySet())
        {
            if(priorityQueue.size()<2)
            {
                priorityQueue.add(entry);
            }
            else
            {
                Map.Entry<String,Integer> map1=priorityQueue.peek();
                if(map1.getValue().compareTo(entry.getValue())==0) {//频率相同看首字母
                    if (map1.getKey().compareTo(entry.getKey()) > 0) {
                        priorityQueue.poll();
                        priorityQueue.add(entry);
                    }
                }
                else//频率不相同
                {
                    if(map1.getValue()<entry.getValue())
                    {
                        priorityQueue.poll();
                        priorityQueue.add(entry);
                    }
                }
            }

        }
        System.out.println(priorityQueue);
    }
}