堆，堆排序，加强堆

前置知识：比较器

比较器，顾名思义就是定义两个对象之间比较的标准，实质就是重载比较运算符，可以很好的应用在特殊标准的排序上，也可以很好的应用在根据特殊标准排序的结构上，Java的util包中，提供了比较器接口Comparator，实现此接口后用户需要去实现compara方法，此方法的作用是根据用户定义的标准去决定对象的优先级顺序，遵循的规范如下：

public int compare(T o1, T o2) ;
返回负数的情况，就是o1比o2优先的情况
返回正数的情况，就是o2比o1优先的情况
返回0的情况，就是o1与o2同样优先的情况

堆结构

堆结构（以下简称堆），本质就是用数组实现的完全二叉树结构。堆在使用上具体又分为大根堆和小根堆，在完全二叉树中如果每棵子树的最大值都在顶部就是大根堆，而如果每棵子树的最小值都在顶部就是小根堆，这就是二者之间的区别。在Java中，优先级队列就是堆结构的实现，那如果给你一个数组，如何把它调整成一个堆呢？

在讲堆的实现之前，我们得先知道一些二叉树结构的基本知识——对于树上的任意一个节点，如果在树中的位置为 i ，其左孩子的位置就是2 * i +1，右孩子的位置就是2 * i + 2,父节点的位置就是（i – 1）/ 2,。这里需要注意的是：树只是我们脑海中的结构，具体到计算机的内存结构中就是一个数组形式，所谓的位置信息其实就是数组的下标。

有了上面的铺垫，现在我们就开始讲堆结构的实现，先看建堆的过程，这里我们以大根堆为例，想象一个场景，用户源源不断的给你一些数，开始时用户先给你7，再给你 2，后面可能直接给你一批数，比如9,0,5，你要怎么把这些数加到堆里面去，并保证堆结构不被破坏？我们不妨把增加的操作记为heapInsert，这里我们先想象一下：在往堆里增加元素的时候，如果知道新增元素要去哪个位置，那么根据大根堆的定义，我们是不是就可以根据当前节点的位置坐标，算出父节点的位置，并与之进行pk，如果不大于父节点的值，不进行任何操作，但如果大于父节点的值，当前节点就往上升，来到父节点的位置，然后接着一路往上继续寻找父节点进行pk，直到pk不过为止。如果上面想法可行，那只就剩下一个问题：如何确定新增元素的位置，其实答案很简单，用指针，前面我们说了堆结构本质上就是数组结构，我们只需要申请一个指针，记为heapSize，记录每次新增元素时在堆中的位置，比如heapSize=3，如果此时要新增元素，则新增元素在堆中的位置为3，随后heapSize++，会计算出下一次新增元素时在堆中的位置，具体怎么使用，下面实现堆的完整代码中再介绍，这里先记住这个指针，先看heapInsert操作的代码：

// 新增的元素，现在停在index位置，不断往上看
// 依次与父节点进行pk，赢了就交换，直到干不过父节点
private static void heapInsert(int[] arr, int index) {
    /**
     * 注意：隐含的条件
     * index == 0 时，(index - 1) / 2 == 0，自己和自己比较，不可能出现大于的情况
     */
    while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

// 可以考虑异或运算
public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
复制代码

讲完新增操作，我们再来看看删除操作，相当于用户此时让你弹出此时堆中的最大值，你要怎么处理，才能保持堆结构呢？首先在大根堆中最大值一定在0位置，这是由于堆的定义决定的，这里我们的做法是把堆顶元素与堆中最后一个位置的元素进行交换，因为我们有heapSize指针，所以只需 heapSize – 1 更新指针就可以算出当前堆中的最后一个元素的位置，进行交换操作之后，交换到堆顶的元素再进行调整操作：和自己的左右孩子比较，看自己的孩子能不能把自己干掉，能就交换，重复此过程，直到干不过自己的孩子为止，相当于逻辑删除。具体操作如代码所示：

// 从index位置往下看，不断往下沉
// 停止条件：较大的孩子都不再比index位置的数大 或 没有孩子
private static void heapify(int[] arr, int index, int heapSize) {
    // 算出左孩子位置
    int left = index * 2 + 1;
    while (left < heapSize) { // 说明有左孩子,但可能没有右孩子
        // ① left + 1 < heapSize : 判断有没有右孩子,注意heapSize的定义，条件<=其实是不成立的
        // ② 左右孩子比较，拿到较大孩子的位置
        int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        // 父节点与较大的孩子进行pk，谁大获取其坐标
        largest = arr[largest] > arr[index] ? index : largest;
        if (largest == index) {
            break;
        }
        swap(arr, largest, index);
        index = largest;
        left = index * 2 + 1;
    }
}
复制代码

说到这里，关于堆的新增与删除操作我们已经有了，这里解释一下，为什么关于两个方法的权限修饰符不是public，而是private，其实也很简单，这两个方法是关于堆的基本调整，未来在面向用户的时候，我们会在两个方法的基础上，实现功能特定的方法供用户使用，不让用户直接使用基础方法，也就是设计模式中的开闭原则，对扩展开放，对修改关闭。关于堆的具体实现代码如下：

public class heap{
    // 堆结构
    private int[] heap;
    // 堆的容量
    private int limit;
    // 位置指针
    private int heapSize;

    public Heap(int limit) {
        heap = new int[limit];
        this.limit = limit;
        heapSize = 0;
    }
    
    public boolean isEmpty() {
        return heapSize == 0;
    }

    public boolean isFull() {
        return heapSize == limit;
    }
    
    // 面向用户的增加操作
    public void push(int val) {
        if (heapSize == limit) 
            throw new RuntimeException("heap is full");
        }
        heap[heapSize] = val;
        heapInsert(heap, heapSize++);
    }
    
    // 面向用户的弹出操作
    public int pop() {
        if (heapSize == 0) {
            throw new RuntimeException("heap is empty");
        }
        int ans = heap[0];
        swap(heap, 0, --heapSize);
        heapify(heap, 0, heapSize);
        return ans;
    }
}
复制代码

堆排序

根据上述的流程，我们已经手写实现了一个堆结构，虽然是大根堆，但小根堆也是一样的道理，就是在heapInsert和heapify的操作中，比较的顺序换一下即可，这里就不过多赘述了，讲回堆排序前，我们先看看heapInsert和heapify的时间复杂度，两者的时间复杂度都是 logN，为什么呢？开始我们说了堆其实就是一个二叉树结构，当数据量为N，加入树中，树的高度就是 logN，而仔细观察heapInsert和heapify操作，每一次都是找自己的父亲或者孩子去pk，最差情况所经历的代价就是整颗树的高度，也就是logN的代价，所以堆的时间复杂度就是logN。

经过上面的过程，我们已经可以实现一个堆的结构，那么堆排序其实就很简单了，比如用户给你一个数组，要求你排有序，首先你先把数组调整成大根堆，就是heapInsert操作，那么此时堆顶的元素就是原数组中的最大值，把它和堆中最后一个位置的元素进行交换，再把最后一个元素跟堆断连，也就是heapify操作，每次重复此过程搞定一个堆中最大值，最后的结果不就是数组从小到大排好序了吗？具体代码如下：

public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    // 建堆 --> 从上到下 --> O(N * logN)
    // for (int i = 0; i < arr.length; i++) {
    //      heapInsert(arr, i);
    // }
    // 建堆 --> 从下到上 --> O(N)
    for (int i = arr.length - 1; i >= 0; i--) {
        heapify(arr, i, arr.length);
    }
    int heapSize = arr.length;
    swap(arr, 0, --heapSize);
    while (heapSize > 0) {
        heapify(arr, 0, heapSize);
        swap(arr, 0, --heapSize);
    }
}
复制代码

讲到这里，堆排序的时间复杂度，相信已经很容易理解了，假设数组的长度为N，根据代码所示，需要遍历数组去建堆，复杂度是O(N * log N)，然后堆顶元素和堆中最后一个元素交换，交换之后再继续调整堆结构，直到堆大小减为0，时间复杂度也是O(N * log N),所以堆排序的时间复杂度就是O(N * log N)。
这里扩充一点，就是建堆的时候其实有两种方法，一种是自顶向下建堆，这种方法很容易理解，就是根据树的结构一层层往下落，越往下树上的节点个数也就越多，时间复杂度也就是O(N * logN)。还有一种方法是自底向上建堆，它的时间复杂度是O(N),怎么理解呢，比如用户给你一个数组，可以把它想象成一个二叉树，只不过它目前还不是堆结构，既然是一颗二叉树，最底层的节点是满足堆结构的，然后依次往上一层看，看看是不是可以进行heapify操作，最后可以收敛于O(N)，怎么证明呢？比如一棵树上的节点个数N，叶子节点的数量接近2/N,这一层heapify操作时其实是只看了一回，所以复杂度为 (2/N) * 1, 在往上一层,节点数量接近4/N，看了 2 回，所以 复杂度 (4 / N) * 2，依次类推，整个时间复杂度的表达式为：
T(N) = (2/N) * 1 + (4/N) * 2 + (8/N) * 3 + …
表达式 * 2 :
2T(N) = N + (2/N) * 2 + (4/N) * 3 +…
两个表达式相减
T(N) = N + N/2 + N/4 + N/8 …
呈现等比数列，所以时间复杂度 O(N)。

加强堆

上面具体介绍了堆和堆排的具体过程，其实Java中的PriorityQueue（优先级队列）就是系统提供的堆实现，那么为什么还要手动去实现？原因也很简单，假如现在你手里有一个堆，里面存着一些元素，用户此时说要改变元素的排序指标且要求高效，怎么办？用系统实现的堆，你是不是只能把堆中的元素拿出来再重新去调整。哎呀，此时你的用户又想删除堆中的某一个元素，你要怎么删除指定元素又能保证堆结构呢？系统提供的堆是不是无能为力，或者说系统提供的堆不能高效的满足你的需求，你只能去手动改写。这里我们想一想：系统的堆为什么不能满足我们的需求，根本原因在于：元素进堆之后，我们不能确定元素在堆的位置，如果我们能知道堆中元素的位置，不管调整还是删除元素，是不是只需要在它的当前位置进行heapInsert或者heapify操作就可以了。这就是加强堆的作用，给堆中的元素增加一张反向索引表，记录入堆元素的位置，用来满足我们的需求。具体代码如下：

public class HeapGreater<T> {

    // 堆结构
    private ArrayList<T> heap;
    // key:元素  value:位置
    private HashMap<T, Integer> indexMap;
    // 位置指针
    private int heapSize;
    // 比较器
    private Comparator<? super T> comp;

    public HeapGreater(Comparator<T> c) {
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        heapSize = 0;
        comp = c;
    }

    // 交换、更新位置信息
    private void swap(int i, int j) {
        T o1 = heap.get(i);
        T o2 = heap.get(j);
        heap.set(i, o2);
        heap.set(j, o1);
        indexMap.put(o1, j);
        indexMap.put(o2, i);
    }
    
    public boolean isEmpty() {
        return heapSize == 0;
    }

    public int size() {
        return heapSize;
    }

    // 获取堆顶元素
    public T peek() {
        return heap.get(0);
    }

    // 判断元素是否在堆中
    public boolean contains(T o) {
        return indexMap.containsKey(o);
    }

    public void push(T o) {
        heap.add(o);
        indexMap.put(o, heapSize);
        heapInsert(heapSize++);
    }
    
    public T pop() {
        T ans = heap.get(0);
        swap(0, heapSize - 1);
        indexMap.remove(ans);
        heap.remove(--heapSize);
        heapify(0);
        return ans;
    }

    // 删除指定的元素
    public void remove(T o) {
        // 获取堆上最后一个元素
        T replace = heap.get(heapSize - 1);
        // 获取指定元素的位置
        int index = indexMap.get(o);
        // 从索引表中删除指定元素位置信息
        indexMap.remove(o);
        // 最后位置的元素从堆中断连
        heap.remove(--heapSize);
        // 注意:删除的元素可能就是堆中的最后一个元素 --> 不进行后续操作
        if (o != replace) {
            // 删除的不是最后一个元素
            // 用最后一个元素去替删除元素
            heap.set(index, replace);
            // 替换之后更新位置信息
            indexMap.put(replace, index);
            // 调整堆结构
            resign(replace);
        }
    }

    // 获取堆上所有的元素
    public List<T> getAllElements() {
        List<T> ans = new ArrayList<>();
        for (T o : heap) {
            ans.add(o);
        }
        return ans;
    }

    // 调整堆结构 --> 两个方法只会执行一个,时间复杂度O(log N)
    public void resign(T o) {
        heapInsert(indexMap.get(o));
        heapify(indexMap.get(o));
    }

    private void heapInsert(int index) {
        while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void heapify(int index) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize
                    && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? left + 1 : left;
            largest = comp.compare(heap.get(largest), heap.get(index)) < 0 ? largest : index;
            if (largest == index) {
                break;
            }
            swap(largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }
}
复制代码