[数据结构与算法]Java算法体系学习（四）堆（大根堆、小根堆、堆排序、加强堆）

四、堆、改进堆、堆排序及其应用

1、堆和完全二叉树

• 堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
  • 堆中某个结点的值总是不大于或不小于其父结点的值；
  • 堆总是一棵完全二叉树。
  • 大根堆：根节点的值不小于叶子节点的值，所有子树都是这样
  • 小根堆：根节点的值不大于叶子节点的值，所有子树都是这样
• 完全二叉树
  • 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与[满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
  • 简单来说，完全二叉树只可能出现两种情况。要么二叉树是满的；要么除了最后一层都是满的，并且最后一层的节点从左依次到右，不能间隔。
  • 对于数中的第i个节点
    1. 左孩子节点 ： 2 * i + 1
    2. 右孩子节点 ： 2 * i + 2
    3. 父亲节点 ： （i - 1） / 2 向下取整

2、用数组实现大根堆

• 同完全二叉树的编号一样。数组第0个位置表示堆的根，第i个位置的左孩子节点为2 * i + 1，右孩子节点 ： 2 * i + 2，父亲节点 ： （i - 1） / 2 向下取整。
• 对于n个元素的堆来说
• heapify和heapInsert时间复杂度都是O(log₂n)
• 所有堆的弹出和加入操作都是O(log₂n)操作

package heap;

public class Heap{
    //堆中真实存放的数据
    private int[] heapData;
    //堆的大小
    private int heapSize;
    //堆的容量限制
    private int limit;

    public Heap(int limit) {
        this.limit = limit;
        heapData = new int[limit];
        heapSize = 0;
    }

    public boolean isEmpty(){
        return heapSize == 0;
    }

    /**
     * 堆上浮操作，从当前位置开始，一直交互到合适的位置
     * @param index          从当前位置开始上浮
     */
    private void heapInsert(int index) {
        while (heapData[index] > heapData[(index - 1) / 2]){
            swap(index,(index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 堆下沉
     * @param index 当前需要下沉元素的索引
     */
    private void heapify(int index){
        int left = 2 * index + 1;
        //有左孩子
        while (left < heapSize){
            //找出左右孩子节点中较大的数值的索引，若没有则最大就是左孩子节点
            int largest = left + 1 < heapSize && heapData[left + 1] > heapData[left] ? left + 1 : left;
          //比较左右孩子中较大的数值与父亲节点的数值
            int maxIndex = heapData[largest] > heapData[index] ? largest : index;
            //说明父亲较大不需要比较，直接退出
            if(maxIndex == index){
                break;
            }
            swap(index,maxIndex);
            index = maxIndex;
            left = 2 * index + 1;
        }
    }

    /**
     * 给堆中加入数据，并将数据上浮到合适的位置
     * @param data          待插数据
     * @throws Exception    堆满
     */
    public void push(int data) throws Exception {
        if(heapSize == limit){
            throw new Exception("当前堆已满......");
        }
        heapData[heapSize] = data;
        heapInsert(heapSize++);
    }

    /**
     * 堆弹出操作
     * @return
     * @throws Exception
     */
    public int pop() throws Exception {
        if(heapSize == 0){
            throw new Exception("当前堆已空......");
        }
        //先将要弹出元素交换到最后一个位置
        //将交换后的元素下沉到合适位置
        int ans = heapData[0];
        heapData[0] = heapData[heapSize - 1];
        heapSize--;
        heapify(0);

        return ans;
    }

    private void swap(int i,int j){
        int temp = heapData[i];
        heapData[i] = heapData[j];
        heapData[j] = temp;
    }
    
}

3、堆排序

• 仿照前面写的堆，我们可以利用数组建立一个大根堆，从数组0号位置开始加入，建立好堆，然后依次弹出。这里进行排序可以不进行弹出，直接交换到数组最后位置即可。前面我们知到，所有堆的弹出和加入操作都是O(log₂n)操作。那么对于每个元素都要进行1次加入和 弹出操作，所以堆排序时间复杂度为O(nlog₂n)。

• 直接把数组改为堆

package heap;

import java.util.Arrays;

public class HeapSort {

    public static void heapInsert(int[] arr,int index){
        while (arr[index] > arr[(index - 1) / 2 ]){
            swap(arr,index,(index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[]  arr,int index,int heapSize){
        int left = 2 * index + 1;
        while (left < heapSize){
            //找出左右孩子节点中较大的数值的索引，若没有则最大就是左孩子节点
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            //比较左右孩子中较大的数值与父亲节点的数值
            int maxIndex = arr[largest] > arr[index] ? largest : index;
            //说明父亲较大不需要比较，直接退出
            if(maxIndex == index){
                break;
            }
            swap(arr,index,maxIndex);
            index = maxIndex;
            left = 2 * index + 1;
        }
    }

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


    public static void heapSort(int[] arr){
//        //先建立堆
//        //从上往下建立堆 O(n * log n)
//        for(int i = 1; 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);
        }
    }


    public static int[] generateRandomArray(int maxLen,int maxValue){
        int len = (int) (Math.random() * maxLen) + 1;
        int[] arr = new int[len];
        for (int i = 0;i < len;i++){
            arr[i] =  (int) (Math.random() * maxValue) + 1;
        }
        return arr;
    }

    public static void main(String[] args) {
        int testTime = 10000;
        int maxLen = 1000;
        int maxValue= 10000;

        System.out.println("测试开始...............");
        for (int time = 0; time < testTime;time++){
            int[] arr = generateRandomArray(maxLen, maxValue);
            int[] copyArr = new int[arr.length];
            System.arraycopy(arr,0,copyArr,0,arr.length);
            heapSort(arr);
            Arrays.sort(copyArr);
            for(int i = 0;i < arr.length;i++){
                if(arr[i] != copyArr[i]){
                    System.out.println("出错了.....");
                    System.exit(1);
                }
            }
        }
        System.out.println("测试结束...............");
    }


}

4、加强堆(小根堆)

• 加强堆可以修改堆中任一元素的大小且维护堆的性质，并且使得删除操作也是O(logN)操作
• 通过反向索引表，可以根据元素直接找到位置。用空间换区时间，进而执行其他操作。

package heap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

public class HeapGreater<T> {
    //堆中存放元素的地方
    private ArrayList<T> heap;
    //方向索引表，可以方便找到元素在堆中的位置
    private HashMap<T, Integer> indexMap;
    //记录堆的大小
    private int heapSize;
    //比较器，根据传入元素的排序要求进行排序
    private Comparator<T> comparator;

    public HeapGreater(Comparator<T> comparator) {
        this.comparator = comparator;
        heapSize = 0;
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
    }

    /**
     * 判断堆是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return heapSize == 0;
    }

    /**
     * 返回堆的大小
     *
     * @return
     */
    public int size() {
        return heapSize;
    }

    /**
     * 判断某个元素是否在堆中
     *
     * @param obj
     * @return
     */
    public boolean contains(T obj) {
        return indexMap.containsKey(obj);
    }

    /**
     * 加入堆
     *
     * @param obj
     */
    public void push(T obj) {
        heap.add(obj);
        indexMap.put(obj, heapSize);
        heapInsert(heapSize++);
    }

    /**
     * 弹出堆
     *
     * @return
     */
    public T pop() {
        T ans = heap.get(0);
        swap(0, heapSize - 1);
        indexMap.remove(ans);
        heap.remove(--heapSize);
        heapify(0);
        return ans;
    }

    /**
     * 修改某一位置的值
     *
     * @param obj
     */
    public void resign(T obj) {
        heapInsert(indexMap.get(obj));
        heapify(indexMap.get(obj));
    }

    /**
     * 删除堆中某个元素
     */
    public void remove(T obj) {
        //将最后一个元素先保存起来
        //并且找到需要删除元素的索引，删除堆中的左后一个元素
        //在以前索引的位置放入最后一个元素，并且调整堆大小
        T replace = heap.get(heapSize - 1);
        int index = indexMap.get(obj);
        indexMap.remove(obj);
        heap.remove(--heapSize);
        if (obj != replace) {
            heap.set(index, replace);
            indexMap.put(replace, index);
            resign(replace);
        }
    }

    private void heapInsert(int index) {
        while (comparator.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 = 2 * index + 1;
        while (left < heapSize) {
            int smallest = (left + 1 < heapSize) &&
                    comparator.compare(heap.get(left + 1), heap.get(left)) < 0
                    ? left + 1 : left;
            int minIndex = comparator.compare(heap.get(smallest), heap.get(index)) < 0 ? smallest : index;
            if (index == minIndex) {
                break;
            }
            swap(minIndex, index);
            index = minIndex;
            left = 2 * index + 1;
        }
    }

    /**
     * 交换堆中两个位置的元素，并且更改反向索引表中的相应记录
     *
     * @param i
     * @param j
     */
    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);

    }
}