比较器与堆

我要就业

Created At : 2022-07-05 22:03

Count:2.1k Views 👀 :

堆
堆排序
语言提供的堆结构VS手写的堆结构
1. 系统版本的堆结构
  1. 如果上过堆的东西,需要改动某些东西,自己手动写
比较器

堆

满二叉树、完全二叉树、平衡二叉树、最优二叉树的基本概念和区别
1. 堆结构就是用数组实现的完全二叉树结构
2. 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3. 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4. 堆结构的heapInsert与heapify操作
5. 堆结构的增大和减少
6. 优先级队列结构，就是堆结构
- 用数组来保存完全二叉树，如果从0下标开始存，那么推断：
  - 这个节点的左孩子为：2*i+1
  - 这个节点的右孩子为：2*i+2
  - 这个节点的父亲为：(i-1)/2
- 但是有的会把数组的0位置弃而不用（因为计算左孩子比较多的情况，可以直接利用位运算，这样速度最快），这个公式是什么样子呢？
  - 这个节点的左孩子为：2*i（i<<1）
  - 这个节点的右孩子为：2*i+1（i<<1 | 1）
  - 这个节点的父亲为：i/2（i>>1）
1. 有N个数,想象的树,的高度,是logN级别的
2. 收到一个数字,调整到合适的未知,只需要探父节点,也就是logN的代价

public static class MyMaxHeap {
    private int[] heap;
    private final int limit;
    private int heapSize;

    public MyMaxHeap(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 value) {
        if (heapSize == limit) {
            throw new RuntimeException("heap is full");
        }
        heap[heapSize] = value;
        // value heapSize
        heapInsert(heap, heapSize++);
    }

    // 用户此时，让你返回最大值，并且在大根堆中，把最大值删掉
    // 剩下的数，依然保持大根堆组织
    public int pop() {
        int ans = heap[0];
        swap(heap, 0, --heapSize);
        heapify(heap, 0, heapSize);
        return ans;
    }

    // 新加进来的数，现在停在了index位置，请依次往上移动，
    // 移动到0位置，或者干不掉自己的父亲了，停！
    private void heapInsert(int[] arr, int index) {
        // [index] [index-1]/2
        // index == 0
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    // 从index位置，往下看，不断的下沉
    // 停：较大的孩子都不再比index位置的数大；已经没孩子了
    // heapSize 想象中的最大值
    private void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            // 如果有左孩子，有没有右孩子，可能有可能没有！
            // 把较大孩子的下标，给largest
            // 右孩子胜出条件：1有右孩子，2右孩子的值比左孩子大；否则就是左孩子胜出

            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;

            // 找到较大孩子的值，如果比父亲要大，largest不变，否则，如果没有pk过父亲，那父亲节点给largest
            // 谁大谁把节点给largest
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            // index和较大孩子，要互换
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

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

}

堆排序

先让整个数组都变成大根堆结构，
建立堆的过程：
1. 从上到下的方法，时间复杂度为O(N*logN)；
2. 从下到上的方法，时间复杂度为O(N)；
把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N*logN)；
堆的大小减小成0之后，排序完成。

// 堆排序额外空间复杂度O(1)
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); // O(logN)
//		}
    // 从后往前走
    // 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)
        heapify(arr, 0, heapSize); // O(logN)
        swap(arr, 0, --heapSize); // O(1)
    }
}

// arr[index]刚来的数，往上
public static void heapInsert(int[] arr, int index) {
    // arr[index]
    // arr[index]不比 arr[index父]大了，停
    // index = 0;
    while (arr[index] > arr[(index - 1) / 2]) {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}

// arr[index]位置的数，能否往下移动
public static void heapify(int[] arr, int index, int heapSize) {
    int left = index * 2 + 1; // 左孩子的下标
    while (left < heapSize) { // 下方还有孩子的时候
        // 两个孩子中，谁的值大，把下标给largest
        // 1）只有左孩子，left -> largest
        // 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest
        // 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest
        int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        // 父和较大的孩子之间，谁的值大，把下标给largest
        largest = arr[largest] > arr[index] ? largest : index;
        if (largest == index) {
            break;
        }
        swap(arr, largest, index);
        index = largest;
        left = index * 2 + 1;
    }
}

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

语言提供的堆结构VS手写的堆结构

（优先级队列PriorityQueue，底层就是堆，默认为小根堆）
为什么还要手写堆结构？

取决于你有没有动态修改信息的需求。
对于语言自身的堆结构而言，你如果动态改数据，不保证依然有序；
对于手写堆结构，因为增加了对象的位置表，所以能够满足动态改信息的需求。

系统版本的堆结构

与堆有关的题目：已知一个几乎有序的数组，(几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。)请选择一个合适的排序策略，对这个数组进行排序。时间复杂度为O(N*logK)

小根堆
把0~0+k个数放到小根堆,第0个位置的数可以确定
把1~1+k个数放到小根堆,第1个位置的数可以确定
…
排序完成

如果上过堆的东西,需要改动某些东西,自己手动写

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

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

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

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

    public int size() {
        return heapSize;
    }

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

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

    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));
//		int valueIndex = indexMap.get(value);
//		// 只会中一个，所以都写
//		heapInsert(valueIndex);
//		heapify(valueIndex, heapSize);
    }

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

    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 = index * 2 + 1;
        while (left < heapSize) {
            int best = left + 1 < heapSize && comparator.compare(heap.get(left + 1), heap.get(left)) < 0 ? (left + 1) : left;
            best = comparator.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(o2, i);
        indexMap.put(o1, j);
    }

}

比较器

比较器的实质就是重载比较运算符；
比较器可以很好地应用在特殊标准的排序上；
比较器可以很好地应用在根据特殊标准排序的结构上；
写代码变得异常容易，还可以用于泛型编程。
案例:compare(Student o1, Student o2)
- 返回负数的时候，第一个参数排在前面
- 返回正数的时候，第二个参数排在前面
- 返回0的时候，谁在前面无所谓

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 963614756@qq.com。