(数据结构与算法）堆相关

总览

今天讲另外一种特殊的树，“堆”（Heap）。堆这种数据结构的应用场景非常多，java中的PriorityQueue，最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为 O(nlogn) 的排序算法。它有两个特点：

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

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。对于每个节点的值
都小于等于子树中每个节点值的堆，我们叫作“小顶堆”。

如何实现一个堆？

我之前讲过，完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间。如图所示：

往堆中插入一个元素

也叫堆化（heapify），堆化实际上有两种，从下往上和从上往下。这里我先讲从下往上的堆化方法。（注意：我们从一位置开始储存元素）

public class Heap {
  private int[] a; // 数组，从下标 1 开始存储数据
  private int n;  // 堆可以存储的最大数据个数
  private int count; // 堆中已经存储的数据个数

  public Heap(int capacity) {
    a = new int[capacity + 1];
    n = capacity;
    count = 0;
  }

  public void insert(int data) {
    if (count >= n) return; // 堆满了
    ++count;
    a[count] = data;
    int i = count;
    while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化
      swap(a, i, i/2); // swap() 函数作用：交换下标为 i 和 i/2 的两个元素
      i = i/2;
    }
  }
 }

2. 删除堆顶元素

我们把最后一个节点放到堆顶，然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的，互换两
个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。这就是从上往下的堆化方法。

public void removeMax() {
  if (count == 0) return -1; // 堆中没有数据
  a[1] = a[count];
  --count;
  heapify(a, count, 1);
}

private void heapify(int[] a, int n, int i) { // 自上往下堆化
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}

往堆中插入一个元素和删除堆顶元素的时间复杂度都是 O(logn)。

如何基于堆实现排序？

1. 建堆

从第一个非叶子节点开始堆化。此文中为n/2，若从数组0位置开始则为(n-1)/2
建堆的时间复杂度就是 O(n)

private static void buildHeap(int[] a, int n) {
  for (int i = n/2; i >= 1; --i) {
    heapify(a, n, i);
  }
}

private static void heapify(int[] a, int n, int i) {
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}

排序

建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆
顶，也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位
置。
这个过程有点类似上面讲的“删除堆顶元素”的操作，当堆顶元素移除之后，我们把下标为 n
的元素放到堆顶，然后再通过堆化的方法，将剩下的 n − 1 个元素重新构建成堆。堆化完成之
后，我们再取堆顶的元素，放到下标是 n − 1 的位置，一直重复这个过程，直到最后堆中只剩下
标为 1 的一个元素，排序工作就完成了。
排序过程的时间复杂度是 O(nlogn)

// 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)。

堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操
作，所以就有可能改变值相同数据的原始相对顺序。

堆排序和快速排序的比较

第一点，堆排序数据访问的方式没有快速排序友好。
对于快速排序来说，数据是顺序访问的。而对于堆排序来说，数据是跳着访问的。 比如，堆排
序中，最重要的一个操作就是数据的堆化。比如下面这个例子，对堆顶节点进行堆化，会依次访
问数组下标是 1 ， 2 ， 4 ， 8 的元素，而不是像快速排序那样，局部顺序访问，所以，这样对
CPU 缓存是不友好的。

第二点，对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。
我们在讲排序的时候，提过两个概念，有序度和逆序度。对于基于比较的排序算法来说，整个排
序过程就是由两个基本的操作组成的，比较和交换（或移动）。快速排序数据交换的次数不会比
逆序度多。
但是堆排序的第一步是建堆，建堆的过程会打乱数据原有的相对先后顺序，导致原数据的有序度
降低。比如，对于一组已经有序的数据来说，经过建堆之后，数据反而变得更无序了。

堆的应用

堆的应用一：优先级队列

优先级队列的应用场景非常多，我们后面要讲的很多数据结构和算法都要依赖它。比如，赫夫曼编码、图的最短路径、最小生成树算法等等。不仅如此，很多语言中，都提供了优先级队列的实现，比如，Java 的 PriorityQueue，C++ 的 priority_queue 等。

1. 合并有序小文件
   假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。
   我们希望将这些 100 个小文件合并成一个有序的大文件。这里就会用到优先级队列。
   也可以说是堆。我们将从小文件中取出来的字符串放入到小顶堆中，那堆顶的元素，也就是优先级队列队首的元素，就是最小的字符串。我们将这个字符串放入到大文件中，并将其从堆中删除。然后再从小文件中取出下一个字符串，放入到堆中。循环这个过程，就可以将 100 个小文件中的数据依次放入到大文件中。我们知道，删除堆顶数据和往堆中插入数据的时间复杂度都是 O(logn)，n 表示堆中的数据个数，这里就是 100。是不是比原来数组存储的方式高效了很多呢？
2. 高性能定时器
   将任务储存在最小堆里面，定时器拿到最近的任务（也就是最小堆堆顶元素）计算时间间隔，等到了时间间隔再来执行任务，之后堆顶元素刷新，再计算第二个任务的时间间隔…

堆的应用二：利用堆求 Top K

1. 针对静态数据
   如何在一个包含 n 个数据的数组中，查找前 K 大数据呢？我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出取数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。
   遍历数组需要 O(n) 的时间复杂度，一次堆化操作需要 O(logK) 的时间复杂度，所以最坏情况下，n 个元素都入堆一次，所以时间复杂度就是 O(nlogK)。
   最小的K个数
   剑指offer#40
   输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,
   思路：维持一个最大堆

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        if(k>input.length || k <= 0){
            return result;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        
        for (int i = 0; i < input.length; i++) {
            if(maxHeap.size()<k)
                maxHeap.add(input[i]);
            else{
                if (input[i]<maxHeap.peek()){
                    maxHeap.poll();
                    maxHeap.add(input[i]);
                }
            }

        }
        for (int i = 0; i < k; i++) {
            
            result.add(maxHeap.poll());
        }
        return result;
    }

堆的应用三-求中位数

剑指offer#41
数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
思路：维持两个堆，最大和最小堆

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
     PriorityQueue<Integer> maxHeap = new PriorityQueue<>(11, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

     public  void Insert(Integer num) {

        //假如堆为空，先向最大堆中添加元素
        if(maxHeap.size() == 0){
            maxHeap.add(num);
            return;
        }

        if(num<maxHeap.peek()){
            maxHeap.add(num);
        }else {
            minHeap.add(num);
        }
        //对堆的大小进行调整
        if(maxHeap.size()> minHeap.size()+1){
            minHeap.add(maxHeap.poll());
        }
        if(minHeap.size()>maxHeap.size()){
            maxHeap.add(minHeap.poll());
        }

    }



     public Double GetMedian() {


        if((minHeap.size()==maxHeap.size())){
            return (maxHeap.peek()+minHeap.peek())/2.0;
        }else{
            return (double)maxHeap.peek();
        }
        
    }

牢记：堆的插入和删除操作时间复杂度为O(logn)，返回元素的复杂度为O(n)