• 【数据结构】优先级队列（堆）重点知识汇总（附有代码）

    目录

    思维导图：

    1.优先级队列：

    2.PriorityQueue特性：

    3.优先级队列的使用：

    思维导图：

    1.优先级队列：

    1. 队列的特点是先进先出，优先级队列中则是优先级高的元素先出队列。
    2. 堆是将所有元素按完全二叉树的顺序存储方式存储到一个数组中，如果根节点的值大于孩子节点则称大根堆；若根节点的值小于孩子节点则称为小根堆；堆总是一颗完全二叉树。
    3. 完全二叉树可以采用层序遍历的规则按照顺序存储到数组中，而非完全二叉树则不适合，容易造成空间的浪费空间利用率低下。
    4. 堆的创建，在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整，建堆的时间复杂度为O(n)。 
      //建立大根堆，每一棵子树的调整属于向下调整
public void createHeap(){
    for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
        shiftDown(parent,usedSize);
    }
}
//向下调整
public void shiftDown(int parent,int len){
    int child = parent*2 + 1;
    //parent和child只是下标
    while(parent < len){
        if(child+1 < len && elem[child] < elem[child+1]){
            child++;
        }
        if(elem[child] > elem[parent]){
            int tmp = elem[child];
            elem[child] = elem[parent];
            elem[parent] = tmp;
            parent = child;
            child = 2*parent + 1;
        }
        else{
            break;
        }
    }
}

       

       

       

    5. 堆的插入涉及到了向上调整，插入和删除元素的时间复杂度都为O(log2N)。 
      //入堆，需要向上调整
public void offer(int x){
    if(isFull()){
        elem = Arrays.copyOf(elem,elem.length*2);
    }
    this.elem[usedSize] = x;
    usedSize++;
    shiftUp(usedSize-1);
}

private boolean isFull() {
    return usedSize == elem.length;
}

//向上调整
public void shiftUp(int child){
    int parent = (child-1)/2;
    while(child > 0){
        if(elem[child] > elem[parent]){
            int tmp = elem[child];
            elem[child] = elem[parent];
            elem[parent] = tmp;
            child = parent;
            parent = (child-1)/2;
        }else{
            break;
        }
    }
}
    6. 优先级队列的删除操作，删除的是堆顶的元素，将要删除的堆顶元素和最后元素交换，然后让usedSize--，再让0下标向下调整即可；插入和删除元素的时间复杂度为O(log2N)。 
      //出堆，需要向下调整
public int poll(){
    if(isEmpty()){
        return -1;
    }
    int oldvalue = elem[0];
    int tmp = elem[0];
    elem[0] = elem[usedSize-1];
    elem[usedSize-1] = tmp;
    usedSize--;
    shiftDown(0,usedSize);
    return oldvalue;
}
private boolean isEmpty(){
    return usedSize == 0;
}
    7. 优先级队列模拟实现时，就是将完全二叉树使用数组的形式存储起来
    1. class TestHeap{
    2.     public int[] elem;
    3.     public int usedSize;
    4.  
    5.     public TestHeap() {
    6.         this.elem = new int[10];
    7.         this.usedSize = usedSize;
    8.     }
    9.  
    10.     public void initArray(int[] array){
    11.         elem = Arrays.copyOf(array,array.length*2);
    12.         usedSize = elem.length;
    13.     }
    14.     //建立大根堆
    15.     public void createHeap(){
    16.         for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
    17.             shiftDown(parent,usedSize);
    18.         }
    19.     }
    20.     //向下调整
    21.     public void shiftDown(int parent,int len){
    22.         int child = parent*2 + 1;
    23.  
    24.         while(parent < len){
    25.             if(child+1 < len && elem[child] < elem[child+1]){
    26.                 child++;
    27.             }
    28.             if(elem[child] > elem[parent]){
    29.                 int tmp = elem[child];
    30.                 elem[child] = elem[parent];
    31.                 elem[parent] = tmp;
    32.                 parent = child;
    33.                 child = 2*parent + 1;
    34.             }
    35.             else{
    36.                 break;
    37.             }
    38.         }
    39.     }
    40.  
    41.     //入堆，需要向上调整
    42.     public void offer(int x){
    43.         if(isFull()){
    44.             elem = Arrays.copyOf(elem,elem.length*2);
    45.         }
    46.         this.elem[usedSize] = x;
    47.         usedSize++;
    48.         shiftUp(usedSize-1);
    49.  
    50.  
    51.     }
    52.  
    53.     private boolean isFull() {
    54.         return usedSize == elem.length;
    55.     }
    56.  
    57.     //向上调整
    58.     public void shiftUp(int child){
    59.         int parent = (child-1)/2;
    60.         while(child > 0){
    61.             if(elem[child] > elem[parent]){
    62.                 int tmp = elem[child];
    63.                 elem[child] = elem[parent];
    64.                 elem[parent] = tmp;
    65.                 child = parent;
    66.                 parent = (child-1)/2;
    67.             }else{
    68.                 break;
    69.             }
    70.         }
    71.     }
    72.  
    73.     //出堆，需要向下调整
    74.     public int poll(){
    75.         if(isEmpty()){
    76.             return -1;
    77.         }
    78.         int oldvalue = elem[0];
    79.         int tmp = elem[0];
    80.         elem[0] = elem[usedSize-1];
    81.         elem[usedSize-1] = tmp;
    82.         usedSize--;
    83.         shiftDown(0,usedSize);
    84.         return oldvalue;
    85.     }
    86.     private boolean isEmpty(){
    87.         return usedSize == 0;
    88.     }
    89. }
    90.  
    91. public class Main {
    92.     public static void main(String[] args) {
    93.         int[] elem = { 27,15,19,18,28,34,65,49,25,37 };
    94.         TestHeap testHeap = new TestHeap();
    95.         testHeap.initArray(elem);
    96.         testHeap.createHeap();
    97.         System.out.println("调试！");
    98.     }
    99. }

    2.PriorityQueue特性：

    1. PriorityQueue底层是使用堆来实现的，默认情况为小堆。如果需要大根堆需要提供比较器。
    2. 优先级队列底层数组默认大小是11；没有容量限制，可以插入多个元素。如果容量小于64数组会按照2倍扩容。容量大于等于64数组会按照1.5倍扩容。
    3. PriorityQueue放的元素必须可以比较，不可以插入不能比较的元素和null，比较器需要自己传入如果不传入默认这个数据是可以比较的，默认实现Comparable接口的。 
      //方法1
class IntCmp implements Comparator{

    @Override
    public int compare(Integer o1, Integer o2) {
        //小根堆 return o1 - o2;
        //大根堆
        return o2 - o1;
    }
}
public static void main(String[] args) {
    PriorityQueue priorityQueue = new PriorityQueue<>(new IntCmp());       
}

//方法2
PriorityQueue priorityQueue 
                    = new PriorityQueue<>(new Comparator() {
    @Override
    public int compare(Integer o1, Integer o2) {
        //大根堆
        return o2 - o1;
    }
});

    3.优先级队列的使用：

    1. topK问题，时间复杂度为O(N log2N) 
      top-K问题：
1.求前k个最大的，建大小为k的小堆。拿剩下的元素和堆顶元素比较，剩下元素大于堆顶，则删除堆顶元素，入大的元素。
2.求前k个最小的，建大小为k的大堆。拿剩下的元素和堆顶元素比较，剩下元素小于堆顶，则删除堆顶元素，入小的元素。
3.求第k个最大的，建大小为k的小堆，堆顶元素就是第k个最大的。拿剩下的元素和堆顶元素比较，剩下元素大于堆顶，则删除堆顶元素，入大的元素。
4.求第k个最小的，建大小为k的大堆，堆顶元素就是第k个最小的。拿剩下的元素和堆顶元素比较，剩下元素小于堆顶，则删除堆顶元素，入小的元素。

    2. 堆排序，若将一组数据从小到大排序，要求在原数组上进行调整，不得创建新的数组。解题思路：建立大根堆；将堆顶元素也就是最大值和最后一个下标元素交换；交换后向下调整再让end--即可。此处留心shiftDown(array, 0, end); 后再 end--;

    top-k问题的代码实现：

    1. public int[] smallestK(int[] array,int k){
    2.     int[] ret = new int[k];
    3.     if(k == 0) return ret;
    4.  
    5.     PriorityQueue priorityQueue = new PriorityQueue<>(k, new Comparator() {
    6.         @Override
    7.         public int compare(Integer o1, Integer o2) {
    8.             return o2 - o1;
    9.         }
    10.     });
    11.     for (int i = 0; i < array.length; i++) {
    12.         if(priorityQueue.size() < k){
    13.             priorityQueue.offer(array[i]);
    14.         }else{
    15.             int top = priorityQueue.peek();
    16.             if(array[i] < top){
    17.                 priorityQueue.poll();
    18.                 priorityQueue.offer(array[i]);
    19.             }
    20.         }
    21.     }
    22.     for (int i = 0; i < k; i++) {
    23.         ret[i] = priorityQueue.poll();
    24.     }
    25.     return ret;
    26. }

    堆排序的代码实现：

    1. //堆排序
    2. public void shiftDown(int parent,int len){
    3.     int child = 2*parent + 1;
    4.  
    5.     while(child 
    6.         if(child+1 < len && elem[child] < elem[child+1]){
    7.             child++;
    8.         }
    9.         if(elem[child] > elem[parent]){
    10.             int tmp = elem[child];
    11.             elem[child] = elem[parent];
    12.             elem[parent] = tmp;
    13.             parent = child;
    14.             child = 2*parent + 1;
    15.         }else{
    16.             break;
    17.         }
    18.     }
    19. }
    20. //建立一个大根堆
    21. public void createHeap(){
    22.     for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
    23.         shiftDown(parent,usedSize);
    24.     }
    25. }
    26. //实现堆排序
    27. public void heapSort() {
    28.  
    29.     int end = usedSize - 1;
    30.     while (end > 0) {
    31.         swap(array, 0, end);
    32.         shiftDown(array, 0, end);
    33.         end--;
    34.     }
    35. }

    如果对您有帮助的话，

    不要忘记点赞+关注哦，蟹蟹

    如果对您有帮助的话，

    不要忘记点赞+关注哦，蟹蟹

    如果对您有帮助的话，

    不要忘记点赞+关注哦，蟹蟹

  • 相关阅读:
    使用match-lstm和答案指针进行机器理解
    git密码提交切换SSH提交
    信创之国产浪潮电脑+统信UOS操作系统体验4：visual studio code中怎么显示中文
    Delaunay三角网之逐点插入法（优化版本三）
    Linux c编程之TCP通信
    统计单词数
    【贝叶斯分类2】朴素贝叶斯分类器
    数据建模设计
    二叉树的中序遍历
    掌握这些插件，分分钟提高你的办公效率90%！
  • 原文地址：https://blog.csdn.net/qq_68993495/article/details/127109886