JZTXT

11、堆

发布时间 2023-04-11 00:29:45作者: lidongdongdong~

1、最大堆

二叉堆是是一棵完全二叉树
最大堆：所有节点都大于等于孩子节点

public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;

    public MaxHeap() {
        data = new Array<>();
    }

    public MaxHeap(int capacity) {
        data = new Array<>(capacity);
    }

    public MaxHeap(E[] arr) {
        heapify(arr);
    }

    public int size() {
        return data.getSize();
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

    /**
     * 返回完全二叉树的数组表示中, 一个索引所表示的元素的父亲节点的索引
     */
    private int parent(int index) {
        if (index == 0) throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }

    /**
     * 返回完全二叉树的数组表示中, 一个索引所表示的元素的左孩子节点的索引
     */
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    /**
     * 返回完全二叉树的数组表示中, 一个索引所表示的元素的右孩子节点的索引
     */
    private int rightChild(int index) {
        return index * 2 + 2;
    }

    /**
     * 上浮: O(logN)
     */
    private void siftUp(int index) {
        while (index > 0 && data.get(index).compareTo(data.get(parent(index))) > 0) {
            data.swap(index, parent(index));
            index = parent(index);
        }
    }

    /**
     * 下沉: O(logN)
     */
    private void siftDown(int index) {
        while (leftChild(index) < data.getSize()) {
            int bigger = leftChild(index);
            if (bigger + 1 < data.getSize() && data.get(bigger + 1).compareTo(data.get(bigger)) > 0) bigger++;

            if (data.get(index).compareTo(data.get(bigger)) >= 0) break;
            data.swap(index, bigger);
            index = bigger;
        }
    }

    /**
     * <p>将任意数组整理成堆的形状: O(n)
     * <p>最后一个节点的父节点就是最后一个非叶子节点
     */
    private void heapify(E[] arr) {
        data = new Array<>(arr);
        for (int i = parent(data.getSize() - 1); i >= 0; i--) siftDown(i);
    }

    /**
     * O(logN)
     */
    public void add(E e) {
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    /**
     * 查看堆中的最大元素
     */
    public E findMax() {
        if (isEmpty()) throw new RuntimeException("Heap is empty!");
        return data.get(0);
    }

    /**
     * 取出堆中的最大元素: O(logN)
     */
    public E extractMax() {
        E max = findMax();
        data.swap(0, data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return max;
    }

    /**
     * 取出堆中的最大元素, 并替换为一个新元素
     */
    public E replace(E e) {
        E max = findMax();
        data.set(0, e);
        siftDown(0);
        return max;
    }
}

2、最小堆

二叉堆是是一棵完全二叉树
最小堆：所有节点都小于等于孩子节点

public class MinHeap<E extends Comparable<E>> {

    private Array<E> data;

    public MinHeap() {
        data = new Array<>();
    }

    public MinHeap(int capacity) {
        data = new Array<>(capacity);
    }

    public MinHeap(E[] arr) {
        heapify(arr);
    }

    public int size() {
        return data.getSize();
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

    private int parent(int index) {
        if (index == 0) throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }

    private int leftChild(int index) {
        return index * 2 + 1;
    }

    private int rightChild(int index) {
        return index * 2 + 2;
    }

    private void siftUp(int index) {
        while (index > 0 && data.get(index).compareTo(data.get(parent(index))) < 0) {
            data.swap(index, parent(index));
            index = parent(index);
        }
    }

    private void siftDown(int index) {
        while (leftChild(index) < data.getSize()) {
            int smaller = leftChild(index);
            if (smaller + 1 < data.getSize() && data.get(smaller + 1).compareTo(data.get(smaller)) < 0) smaller++;

            if (data.get(index).compareTo(data.get(smaller)) <= 0) break;
            data.swap(index, smaller);
            index = smaller;
        }
    }

    private void heapify(E[] arr) {
        data = new Array<>(arr);
        for (int i = parent(data.getSize() - 1); i >= 0; i--) siftDown(i);
    }

    public void add(E e) {
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    public E findMin() {
        if (isEmpty()) throw new RuntimeException("Heap is empty!");
        return data.get(0);
    }

    public E extractMin() {
        E min = findMin();
        data.swap(0, data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return min;
    }

    public E replace(E e) {
        E min = findMin();
        data.set(0, e);
        siftDown(0);
        return min;
    }
}

3、优先队列

基于最大堆实现的优先队列

public interface Queue<E> {

    void enqueue(E e);

    E dequeue();

    E getFront();

    int getSize();

    boolean isEmpty();

}

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private final MaxHeap<E> maxHeap;

    public PriorityQueue() {
        maxHeap = new MaxHeap<>();
    }

    @Override
    public void enqueue(E e) {
        maxHeap.add(e);
    }

    @Override
    public E dequeue() {
        return maxHeap.extractMax();
    }

    @Override
    public E getFront() {
        return maxHeap.findMax();
    }

    @Override
    public int getSize() {
        return maxHeap.size();
    }

    @Override
    public boolean isEmpty() {
        return maxHeap.isEmpty();
    }
}

4、堆排序

堆排序：O(N * logN)
基于最大堆来实现

public class HeapSort {

    private HeapSort() {
    }

    /**
     * 自顶向下建堆: O(N * logN)
     */
    public static <E extends Comparable<E>> void sort1(E[] arr) {
        MaxHeap<E> maxHeap = new MaxHeap<>();
        for (E e : arr) maxHeap.add(e); // 自顶向下建堆: O(N * logN)
        for (int i = arr.length - 1; i >= 0; i--) arr[i] = maxHeap.extractMax();
    }

    /**
     * 堆排序优化, 自底向上建堆: O(n)
     */
    public static <E extends Comparable<E>> void sort2(E[] arr) {
        if (arr == null || arr.length <= 1) return;

        // 把 arr[] 变成最大堆, 自底向上建堆: O(n)
        int last = arr.length - 1;
        for (int i = (last - 1) / 2; i >= 0; i--) siftDown(arr, i, last);

        while (last >= 1) {
            swap(arr, 0, last);
            last--;
            siftDown(arr, 0, last);
        }
    }

    /**
     * 对 arr[0, last] 所形成的最大堆中, 索引 index 的元素, 执行 siftDown
     */
    private static <E extends Comparable<E>> void siftDown(E[] arr, int index, int last) {
        while (index * 2 + 1 <= last) {
            int bigger = index * 2 + 1;
            if (bigger + 1 <= last && arr[bigger + 1].compareTo(arr[bigger]) > 0) bigger++;

            if (arr[index].compareTo(arr[bigger]) >= 0) break;
            swap(arr, index, bigger);
            index = bigger;
        }
    }

    private static <E> void swap(E[] arr, int a, int b) {
        E k = arr[a];
        arr[a] = arr[b];
        arr[b] = k;
    }
}

堆排序：O(N * logN)
基于最小堆来实现

public class HeapSort {

    private HeapSort() {
    }

    public static <E extends Comparable<E>> void sort1(E[] arr) {
        MinHeap<E> minHeap = new MinHeap<>();
        for (E e : arr) minHeap.add(e);
        for (int i = arr.length - 1; i >= 0; i--) arr[i] = minHeap.extractMin();
    }

    public static <E extends Comparable<E>> void sort2(E[] arr) {
        if (arr == null || arr.length <= 1) return;

        int last = arr.length - 1;
        for (int i = (last - 1) / 2; i >= 0; i--) siftDown(arr, i, last);

        while (last >= 1) {
            swap(arr, 0, last);
            last--;
            siftDown(arr, 0, last);
        }
    }

    /**
     * 对 arr[0, last] 所形成的最小堆中, 索引 index 的元素, 执行 siftDown
     */
    private static <E extends Comparable<E>> void siftDown(E[] arr, int index, int last) {
        while (index * 2 + 1 <= last) {
            int smaller = index * 2 + 1;
            if (smaller + 1 <= last && arr[smaller + 1].compareTo(arr[smaller]) < 0) smaller++;

            if (arr[index].compareTo(arr[smaller]) <= 0) break;
            swap(arr, index, smaller);
            index = smaller;
        }
    }

    private static <E> void swap(E[] arr, int a, int b) {
        E k = arr[a];
        arr[a] = arr[b];
        arr[b] = k;
    }
}