目录

• 1. 什么是完全二叉树
• 2. 完全二叉树结构
• 3. 堆结构
• 4. 加强堆

1. 什么是完全二叉树

定义 ：如果一个树是满的，是完全二叉树，如果不满，处在变满的路上，并且是从左往右每一层依次变满，就是完全二叉树。空树也算是完全二叉树。

2. 完全二叉树结构

假如 数组 [1,2,3,4,5,6,7] 为完全二叉树结构

满足公式：

左节点 2*i+1

右节点 2*i+2

父节点 （i - 1） / 2 向下取整

3. 堆结构

• 是完全二叉树
• 大根堆 （在一个完全二叉树中，每一颗子树的最大值都是头节点的值）
• 小根堆 （在一个完全二叉树中，每一颗子树的最小值都是头节点的值）

public class Heap {
    //堆排序
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //将数组调整为堆结构  从上到下建立堆 复杂度 O(N * logN)
//        for (int i = 0; i < arr.length; i++) { //O(N)
//            heapInsert(arr, i); // log(N)
//        }

        //将数组调整为堆结构  从下到上建立堆 复杂度 O(N)
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }

        int heapSize = arr.length;
        //将头部最大值 调整到 最后
        swap(arr, 0, --heapSize);
        //O(N * logN)
        while (heapSize > 0) {//O(N)
            //调整为堆结构 O(logN)
            heapify(arr, 0, heapSize);
            //继续 将头部最大值 调整到 最后 O(1)
            swap(arr, 0, --heapSize);
        }
    }


    //加进来的数 停在了 index 位置 依次向上移动
    //直到 index = 0 或者 不比自己的父节点大 停止
    private static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 删除index 位置节点 往下看
     */
    private static void heapify(int[] arr, int index, int heapSize) {
        //左节点
        int left = 2 * index + 1;
        while (left < heapSize) { //左节点 不越界
            //右节点
            int right = left + 1;
            //左右节点  最大值下标
            int maxIndex = right < heapSize && arr[left] < arr[right] ? right : left;
            // 上一步的最大值下标  跟 index(父节点) 比较
            maxIndex = arr[index] > arr[maxIndex] ? index : maxIndex;
            if (maxIndex == index) {
                break;
            }
            swap(arr, maxIndex, index);
            index = maxIndex;
            left = 2 * index + 1;
        }
    }

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

    public static void main(String[] args) {
        // 默认小根堆 系统优先级队列 就是堆实现    
//        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int[] arr = {1, 3, 4, 5, 6, 2};
        heapSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

4. 加强堆

在原来堆的基础上 添加了 逆向索引indexMap， 降低了复杂度

/**
 * 加强堆
 * T一定要是非基础类型，有基础类型需求 包一层T
 */
public class HeapGreater<T> {

    private ArrayList<T> heap;
    private HashMap<T, Integer> indexMap;
    private int heapSize;
    private Comparator<? super T> comp;

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

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

    public boolean contains(T obj) {
        return indexMap.containsKey(obj);
    }

    public T peek() {
        return heap.get(0);
    }

    public int size() {
        return heapSize;
    }

    public void push(T obj) {
        heap.add(obj);
        indexMap.put(obj, 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 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);
        }
    }

    public void resign(T obj) {
        heapInsert(indexMap.get(obj));
        heapify(indexMap.get(obj));
    }

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

    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 best = left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? (left + 1) : left;
            best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
            if (best == index) {
                break;
            }
            swap(best, index);
            index = best;
            left = index * 2 + 1;
        }
    }

    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);
    }
}