堆（heap）

什么是堆？ 堆是满足下面两个条件的一种二叉树

• 它是一棵完全二叉树；
• 堆中每个节点的值都必须大于等于（大根堆）或者小于等于（小根堆）其子树中每个节点的值。
  完全二叉树是指除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列
  我们看几个例图
  image.png
  其中1,2是大根堆，3,4是小根堆。从图中我们也可以看出来，同一组数据排成的堆可能有多种形式。

存储

因为堆是一棵完全二叉树，所以我们通常使用数组来存储它。节约空间也好定位父节点或者子节点。为了计算子节点方便，通常从下标为1的位置开始存储，如果i是父节点那么2i， 2i + 1就是子节点。
如下图所示

image.png

添加元素

添加元素通常是在数组的最末尾添加，这样添加之后数组仍然满足堆的特性1，但是不满足特性2了，所以必须进行调整，我们将这个调整过程称为heapify.
方法很简单： 就是顺着节点所在的路径，往上对比，需要换位置的就交换

image.png

下面是java代码实现：

public void insert(int value){
        if(count >= capacity) return ;
        data[++count] = value;
        int current = count;
        int parentIndex = count/2;
        while(parentIndex > 0 && data[parentIndex] < value){
            data[current] = data[parentIndex];
            data[parentIndex] = value;
            current = parentIndex;
            parentIndex = current/2;
        }
    }

删除堆顶元素

删除堆顶元素的方法是，将堆顶元素删除，然后将最后一个元素放到堆顶，这样就保证了特性1，然后再按住从上往下的顺序比较交换元素，以满足特性2

image.png

java代码实现

public void removeMax(){
        if(count <= 0) return;
        data[1] = data[count--];
        int current = 1;
        while(true){
            int maxIndex = current;
            if(current *2 <= count && data[current *2] > data[maxIndex]) {
                maxIndex = current * 2;
            }
            if(current *2 + 1 <= count && data[current * 2 + 1] > data[maxIndex]) {
                maxIndex = current * 2 + 1;
            }
            if(maxIndex == current) break;
            int temp = data[current];
            data[current] = data[maxIndex];
            data[maxIndex] = temp;
            current = maxIndex;
        }
    }

有了上述了解之后，接下来我们看看堆最重要的一个应用，堆排序
堆排序可以分成两步：
1. 建堆
我们先来分析一下原始数据，刚开始数据是无序的，但其中叶子节点其实已经是“有序”的了，即其满足堆的定义，大于它所有的子节点，因为它们没有子节点；所有我们只需要对非叶子节点进行排序即可，这里可以宣传从上往下heapify的方法来建堆

image.png
java代码实现如下：

public static void buildHeap(int[] array, int n){
        if(array == null || array.length < 2) return;
        for(int i = n/2; i >= 1; i--){
            heapify(array, n, i);
        }
    }

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

    private static void swap(int[] array, int i, int maxIndex) {
        int temp = array[i];
        array[i] = array[maxIndex];
        array[maxIndex] = temp;
    }

2. 排序
堆建成之后，我们能确定的是第一个元素就是最大元素了（或者最小元素），其他元素的顺序无法确定，所以我们此时将第一个元素和最好一个个元素互换，堆大小减一，此时给我没删除操作类似了，只需要再次堆话就可以得到第二大数据，依次类推可以对整个数组排序

image.png
java 代码实现

 public static void sort(int[] array, int n){
        buildHeap(array, n);
        if(array == null || array.length < 2) return;
        while(n > 1){
            swap(array, 1, n--);
            heapify(array, n, 1);
        }
    }

堆的应用场景

• 优先级队列
  java 中的PriorityQueue 就是用堆实现的
• 取数组中TopK的数据
  假如我们要取一组数据中的top 5,那么我们只需要维护一个5个元素大小的小根堆，当有数据加进来时只需要和堆顶元素做比较，如果比堆顶元素小直接忽略，如果比堆顶元素大，则置换调堆顶元素，然后做heapify.这样每次加数据都只需要和堆顶元素做比较

• 利用堆求中位数
  对应静态数据我们可以直接用快排找；对于动态变化的数据，用堆就比较合适了，这里需要维护两个堆，一个大根堆，一个小根堆；大根堆里面存储前一半小数据，小根堆里面存储后一半大数据。每次插入数据的时候和大根堆堆顶元素比较，小于则放入大根堆，大于则放入小根堆，放完之后为了保证大根堆的堆顶就是中位数，我们可能需要在两个堆之间移动一下数据；

  
  image.png