堆和优先级队列（PriorityQueue）

素颜马尾好姑娘i 2021-12-19 14:45 373阅读 0赞

## 1. 堆的概念 ##

堆逻辑概念上是一棵完全二叉树，而物理存储上使用数组，还要一定的顺序要求。

TreeMap内部使用的是排序二叉树原理，排序二叉树是完全有序的，每个节点都有确定的前驱和后继，而且不能有重复元素。与排序二叉树不同，在堆中，可以有重复元素，元素间不是完全有序的，但对于父子节点直接，有一定的顺序要求。根据顺序分为两种堆：最大堆、最小堆

堆是一种特殊的树，一个堆需要满足如下两个条件：

*  一个堆是一个完全二叉树；
 *  堆中每个节点的值都必须大于等于或者小于等于其子树中的每个节点。

第一条，完全二叉树要求，除了最后一层，其它层的节点个数都是满的，并且最后一层的节点都靠左排列。

第二条，也等价于，每个节点的值大于等于或者小于等于其左右子节点的值。节点值大于等于其子树中每个节点值的堆称为 “大顶堆”，节点值小于等于其子树中每个节点值的堆称为 “小顶堆”。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70][]

上图中，第 1 个和第 2 个是大顶堆，第 3 个是小顶堆，第 4 个不是堆。而且，可以看到，对于同一组数据，我们可以构建多种不同形态的堆。

## 2. 堆的实现 ##

完全二叉树比较适合用数组来存储，这样非常节省空间，因为不需要额外的空间来存储左右子节点的指针，单纯通过下标我们就可以找到一个节点的左右子节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 1][]

*  数组0位置不存放数时，下标为 i 的节点的左子节点下标为 2i，右子节点下标为 2i+1，而父节点下标就为 i/2。
 *  数组0位置存放数时，下标为 i 的节点的左子节点下标为 2i+1，右子节点下标为 2i+2，而父节点下标就为 （i-1）/2。

**2.1. 往堆中插入一个元素**

往堆中插入一个元素后，我们需要继续保持堆满足它的两个特性。

如果我们将新插入的元素放到堆的最后，此时，这依旧还是一棵完全二叉树，但就是节点的大小关系不满足堆的要求。因此，我们需要对节点进行调整，使之满足堆的第二个特性，这个过程称为**堆化**（heapify）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 2][]

堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比然后交换。

我们从新插入的节点开始，依次与其父结点进行比较，如果不满足子节点值小于等于父节点值，我们就互换两个节点，直到满足条件为止。这个过程是自下向上的，称为**从下往上的堆化**方法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 3][]

public class Heap {
            private int[] a; // 数组，从下标 0 开始存储数据
            private int n;  // 堆可以存储的最大数据个数
            private int count; // 堆中已经存储的数据个数
    
            public Heap(int capicity) {
                a = new int[capicity];
                n = capicity;
                count = 0;
            }
    
            public void insert(int data) {
                if (count >= n) return; // 堆满了
                ++count;
                a[count] = data;
                int i = count;
                while ((i-1) / 2 > 0 && a[i] > a[(i-1) / 2]) { // 自下往上堆化
                    swap(a, i, (i-1) / 2);   // swap() 函数作用：交换下标为 i 和 i/2 的两个元素
                    i = (i-1) / 2;
                }
            }
        }

**2.2. 删除堆顶元素**

假设我们构建的是大顶堆，那么堆顶元素就是最大值。当我们删除堆顶元素后，就需要把第二大元素放到堆顶，而第二大元素肯定是其左右子节点中的一个。然后，我们再迭代地删除第二大节点，以此类推，直到叶子节点被删除。

但是，这个方法有点问题，删除堆顶元素后堆就不满足完全二叉树的条件了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 4][]

实际上，我们稍微改变一下思路，就可以解决这个问题。删除堆顶元素后，我们将最后一个结点放到堆顶，然后再依次进行对比，将这个结点交换到正确的位置即可。这个过程是自上而下的，称为**从上往下的堆化**方法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 5][]

public void removeMax() {
      if (count == 0) return -1; // 堆中没有数据
      a[0] = a[count];   // 数组的0位置不存数据。从1开始存数据
      --count;
      heapify(a, count, 0);
    }
    
    private void heapify(int[] a, int n, int i) { // 自上往下堆化
      while (true) {
        int maxPos = i;
        if (i*2+1 <= n && a[i] < a[i*2+1]) maxPos = i*2+1;
        if (i*2+2 <= n && a[maxPos] < a[i*2+2]) maxPos = i*2+2;
        if (maxPos == i) break;
        swap(a, i, maxPos);
        i = maxPos;
      }
    }

一棵包含 n 个节点的完全二叉树，树的高度不会超过 log2n。而堆化的过程是顺着结点所在的路径进行比较交换的，所以堆化的时间复杂度和树的高度成正比，也就是 O(logn)，也即往堆中插入和删除元素的时间复杂度都为 O(logn)。

## 3. 堆排序的实现 ##

借助于堆这种数据结构实现的排序算法，叫作堆排序，堆排序的时间复杂度非常稳定，为 O(nlogn），而且是一种原地排序算法。堆排序大致可以分为两个步骤，**建堆**和**排序**。

**3.1. 建堆**

我们首先将数组原地建成一个堆，所谓原地，就是不借助另外一个数组直接在原数组上进行操作，这有两种思路。

第一种思路就是借助于我们前面往堆中插入一个元素的思想。首先，我们假设下标为 0 的元素就是堆顶，然后依次将数组后面的数据插入到这个堆中即可。这种思路从前往后处理数据，而且每次插入数据时，都是从下往上堆化。

第二种实现思路和第一种截然相反，我们从后往前处理数据，每个数据从上往下堆化。因为叶子节点无法再往下继续堆化，我们从第一个非叶子节点开始，依次往前对数据进行堆化即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 7][]

private static void buildHeap(int[] a, int n) {
      for (int i = (n-1)/2; i >= 0; --i) {
        heapify(a, n, i);
      }
    }
    
    // 这个方法相当于某节点与左右子节点比较，将最大的换得到父节点上。
    private static void heapify(int[] a, int n, int i) {
      while (true) {
        int maxPos = i;
        if (i*2+1 <= n && a[i] < a[i*2+1]) maxPos = i*2+1;
        if (i*2+2 <= n && a[maxPos] < a[i*2+2]) maxPos = i*2+2;
        if (maxPos == i) break;
        swap(a, i, maxPos);
        i = maxPos;
      }
    }

这里，我们对下标为 （n-1）/2 到 0 的数据进行堆化，下标为 （n-1）/2+1 到 n 的节点是叶子结点，不需要进行堆化。

**3.2. 排序**

建堆结束之后，堆顶元素就是最大元素，我们将其和最后一个元素进行交换，那最大元素就放到了下标为 n

的位置。然后，我们再对前面 n−1 个元素进行堆化，然后将堆顶元素放到下标为 n−1 的位置，重复这个过程，直到堆中剩余一个元素，排序也就完成了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 8][]

// n 表示数据的个数，数组 a 中的数据从下标 1 到 n 的位置。
    public static void sort(int[] a, int n) {
      buildHeap(a, n);
      int k = n;
      while (k > 1) {
        swap(a, 1, k);
        --k;
        heapify(a, k, 1);
      }
    }

整个堆排序过程中，我们都只需要常量级别的临时空间，所以堆排序是原地排序算法。堆排序中建堆过程的时间复杂度为 O(n)，排序过程的时间复杂度为 O(nlogn)，因此整体的时间复杂度为 O(nlogn)。

堆排序不是稳定的排序算法，因为在排序的时候，我们将堆顶元素和最后一个元素进行了交换，这就有可能改变了值相同元素的原始相对位置。

### 4. 为什么说堆排序没有快速排序快？ ###

*  堆排序数据访问的方式没有快速排序好

可以看到，堆排序数据的访问不是像快速排序那样按顺序访问的，这对 CPU 缓存是不友好的。下面的这个例子，要对堆顶结点进行堆化，我们要依次访问下标为 1,2,4,8 的元素。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 9][]

*  同样的数据，堆排序的数据交换次数多于快速排序

快速排序的交换次数不会比逆序数多，但是堆排序的建堆过程会打乱原有数据的先后顺序，导致数据的有序度降低。比如，针对一组已经有序的数据，建堆之后，数据反而变得更无序了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 10][]

## 优先级队列（PriorityQueue） ##

PriorityQueue是优先级队列，实现了队列接口（Queue），内部是用堆实现的，内部元素不是完全有序的，不过，逐个出对会得到有序的输出。

PriorityQueue是用堆实现的，堆物理上就是数组，与ArrayList类似，都是使用动态数据，根据元素的个数进行动态扩展，initialCapacity表示初始化的数组大小，默认为11。与TreeMap/TreeSet类似，为了保持一定顺序，PriorityQueue要求要么元素实现Comparable接口，要么传递一个比较器Comparator。

PriorityQueue有多个构造方法：

public PriorityQueue();
    public PriorityQueue(int initialCapacity, Comparator<? super E> comparator);
    public PriorityQueue(Collection<? extends E> c);

常用方法：

<table> 
 <tbody> 
  <tr> 
   <td>&nbsp;boolean offer(E e);</td> 
   <td>添加一个元素并返回true</td> 
   <td>如果队列满，则返回false</td> 
  </tr> 
  <tr> 
   <td>&nbsp;E poll();</td> 
   <td>移出并返回队列的头元素</td> 
   <td>如果队列为空，则返回null</td> 
  </tr> 
  <tr> 
   <td>&nbsp;E peek();</td> 
   <td>返回队列的头元素</td> 
   <td>如果队列为空，则返回null</td> 
  </tr> 
  <tr> 
   <td>&nbsp;boolean add(E e);</td> 
   <td>添加一个元素并返回true</td> 
   <td>如果队列满，则抛出IllegalStateException异常</td> 
  </tr> 
  <tr> 
   <td>&nbsp;E remove();</td> 
   <td>移出并返回头元素</td> 
   <td>如果队列空，则抛出NoSuchElementException异常</td> 
  </tr> 
  <tr> 
   <td>&nbsp;E element()</td> 
   <td>返回队列的头元素</td> 
   <td>如果队列为空，则抛出NoSuchElementException异常</td> 
  </tr> 
 </tbody> 
</table>

优先级队列，既然是优先级，那么内部肯定有一定的规则进行排序，并每一次出队列的保证是优先级最高的。优先级队列的用法实际上很简单，需要实现是一个比较器，内部根据这个比较器来判定谁的优先级比较高：

public class MyComparator implements Comparator<Student> {
    
        @Override
        public int compare(Student o1, Student o2) {
            return -(o1.getId() - o2.getId());
        }
    }

用起来也很简单：

public static void main(String[] args) {
            Queue<Integer> queue = new PriorityQueue();
            queue.add(1);
            queue.add(2);
            queue.add(5);
            queue.add(3);
            while (!queue.isEmpty()){
                System.out.println(queue.poll());
            }
    
            Queue<Student> queue1 = new  PriorityQueue(new MyComparator());
            Student st1 = new Student("ming1", 10);
            Student st2 = new Student("ming2", 11);
            Student st3 = new Student("ming3", 9);
            Student st4 = new Student("ming4", 20);
            Student st5 = new Student("ming5", 1);
            queue1.add(st1);
            queue1.add(st2);
            queue1.add(st3);
            queue1.add(st4);
            queue1.add(st5);
    
            while (!queue1.isEmpty()){
                System.out.println(queue1.poll().getId());
            }
        }

**打印结果：**

> 1  
> 2  
> 3  
> 5
> 
> 20  
> 11  
> 10  
> 9  
> 1

### 堆和PriorityQueue的应用 ###

**问题**

这里先抛出两个比较常见的问题，然后再用堆的思想来进行解决

*  1. 求前K个最大的元素，元素个数不确定，数据量可能很大，甚至源源不断到来，但需要知道目前为止最大的前K个元素
 *  2. 求中值元素，中值不是平均值，而是排序后中间那个元素的值，同样数据量可能很大，甚至源源不断到来

### **求前K个最大的元素** ###

一个简单的思路是排序，排序后取最大的K个就可以了，排序可以使用Arrays.sort()方法，效率为O(N\*log(N))。Arrays.sort()使用的是经过调优的快速排序法 。  
       另一种思路是选择，循环选择K次，每次从剩下的元素中选择最大值，效率为O(N\*K)，如果K值大于log(N)，就不如排序了。

不过这两个思路都是假定所有元素都是已知的，而不是动态的。如果元素个数不确定，且源源不断到来呢？

一个基本的思路是维护一个长度为K的数组，最前面的K个元素就是目前最大的K个元素，以后每来一个新元素的时候，都先找到数组中最小值，将新元素与最小值相比，如果小于最小值，什么都不用做；如果大于最小值，则将最小值替换为新元素。  
这类似于生活中常见的末尾淘汰。

这样，数组中维护的永远都是最大的K个元素，不管数据源有多少，需要的内存开销是固定的，就是长度为K的数组。不过，每来一个元素，都需要找最小值，都需要进行K次比较，能不能减少比较次数呢？

解决方法是使用最小堆维护这个K个元素，最小堆中，根即第一个元素永远都是最小的，新来的元素与根比较就可以了，如果小于根，则堆不需要变化，否则用新元素替换根，然后向下调整堆即可，调整的效率为O(logK)，总体效率就是O(N\*logK)。而且使用了最小堆后，第K个最大的元素也很容易获取，它就是堆的根。

public class TopK<E> {
        private PriorityQueue<E> p;
        private int k;
        public TopK(int k) {
            this.k = k;
            this.p = new PriorityQueue<>(k);
        }
        public void addAll(Collection<? extends E> c) {
            for(E e: c) {
                add(e);
            }
        }
        public void add(E e) {
            if(p.size() < k) {
                p.add(e);
                return ;
            }
            Comparable<? super E> head = (Comparable<? super E>)p.peek();
            if(head.compareTo(e)>0) {
                // 小于TopK中的最小值，不用变
                return ;
            }
            // 新元素替换掉原来最小值成为TopK之一
            p.poll();
            p.add(e);
        }
        public <T> T[] toArray(T[] a) {
            return p.toArray(a);
        }
        public E getKth() {
            return p.peek();
        }
    }

### 求中值 ###

中值就是排序后中间那个元素的值，如果元素个数为奇数，中值是没有歧义的，如果是偶数，可以为偏小的，也可以为偏大的。

一个简单的思路就是排序，排序后取中间的那个值就可以了。排序可以使用Arrays.sort()方法，效率为O(N\*log(N))。  
当然，这是要在数据源已知的情况下才能做到的。如果数据源源不断到来呢？

可以使用两个堆，一个最大堆，一个最小堆

*  1. 假设当前的中位数为m，最大堆维护的是<=m的元素，最小堆维护的是>=m的元素，但两个堆都不包含m。
 *  2. 当新的元素到达时，比如为e，将e与m进行比较，若e<=m，则将其加入最大堆中，否则加入最小堆中
 *  3. 如果此时最小堆和最大堆的元素个数相差>=2，则将m加入元素个数少的堆中，然后从元素个数多的堆将根节点移除并赋值给m。

给个示例解释一下，输入的元素依次是：34，90，67，45，1

*  1. 输入第一个元素时，m赋值为34
 *  2. 输入第二个元素时，90>34，把90加入最小堆，m不变
 *  3. 输入第三个元素时，67>34，把67加入最小堆，此时最小堆根节点为67。但是现在最小堆中元素个数为2，最大堆中元素个数为0，所以需要做调整，把m(34)加入个数少的堆中（最大堆），然后从元素个数多的堆（最小堆）将根节点移除并赋值给m，所以现在m为67，最大堆中有34，最小堆中有90
 *  4. 输入第四个元素时，45<67，把45加入最大堆，m不变
 *  5. 输入第五个元素时，1<67，把1加入最大堆中，此时m为67，最大堆中有1，34，45，最小堆中有90，所以需要调整。调整后，m为45，最大堆为1，34，最小堆为67，90。

public class Median<E> {
        // 最小堆
        private PriorityQueue<E> minP;
        // 最大堆
        private PriorityQueue<E> maxP;
        // 中值
        private E m;
        public Median() {
            this.minP = new PriorityQueue<>();
            this.maxP = new PriorityQueue<>(11, Collections.reverseOrder());
        }
        // 比较
        private int compare(E e, E m) {
            Comparable<? super E> cmpr = (Comparable<? super E>)e;
            return cmpr.compareTo(e);
        }
        public void add(E e) {
            if(m == null) {
                // 第一个元素
                m = e;
                return ;
            }        
            if(compare(e, m) < 0) {
                // 如果e小于m，则加入最大堆
                maxP.add(e);
            } else {
                // 如果e大于m，则加入最小堆
                minP.add(e);
            }
            if(minP.size() - maxP.size() >= 2) {
                // 最小堆中元素比最大堆中元素多2个
                // 将m加入最大堆中，然后将最小堆中的根移除赋值给m
                maxP.add(this.m);
                this.m = minP.poll();
            } else if(maxP.size() - minP.size() >= 2) {
                minP.add(this.m);
                this.m = maxP.poll();
            }
        }
        public void addAll(Collection<? extends E> c) {
            for(E e : c) {
                add(e);
            }
        }
        public E getM() {
            return m;
        }
    }

转载：[https://www.cnblogs.com/seniusen/p/10023172.html][https_www.cnblogs.com_seniusen_p_10023172.html]

[https://blog.csdn.net/u013435893/article/details/79913146][https_blog.csdn.net_u013435893_article_details_79913146]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70]: /images/20211219/e7028a4405224c6ea4cbb77c48c77dfe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 1]: /images/20211219/2af775154ee54d42acfa2476a02c3448.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 2]: /images/20211219/ebbf0a135b624d0ab06547dfb8cd1411.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 3]: /images/20211219/587a047d08e54b9da35d5069bbcc02d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 4]: /images/20211219/8e209a657c994f869577023eac387175.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 5]: /images/20211219/da92574007574f43b23251642a752c7e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 6]: /images/20211219/86982b4f19ba48f383b0aa4d4a012769.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 7]: /images/20211219/efcf43769c4349918867d8c3c6951444.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 8]: /images/20211219/d0fa25c88d5f42bd91fefe3e7c0d7ab4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 9]: /images/20211219/c34ab7c76b0940fa87e219902dc8ee61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 10]: /images/20211219/090143555f324755999d36282a44064d.png
[https_www.cnblogs.com_seniusen_p_10023172.html]: https://www.cnblogs.com/seniusen/p/10023172.html
[https_blog.csdn.net_u013435893_article_details_79913146]: https://blog.csdn.net/u013435893/article/details/79913146