堆

»数据结构与算法

目录：

概念

堆是一种类似树状的结构，有大顶堆和小顶堆之分，如果是大顶堆，那么堆中任意一个节点的值都大于等于他的任意子节点的值

适用求解问题

比如有N个数，需要得出其中最大的M个数，那么就可以维护一个M个大小的小顶堆，然后将N个数依次插入这个堆，最后返回这个堆，即得到了其中最大的M个数。

这样的时间复杂度是O(NlogM)，空间复杂度是O(M)

简单的代码实现如下:

public class MinHeap {
    public static void main(String[] args) {
        // 输入数组
        int[] arr = new int[]{10, 9, 3, 4, 15, 6, 7, 8, 9};
        int m = 20;
        int[] maxM = getMaxM(arr, 3);
        System.out.println(Arrays.toString(maxM));
    }

    /**
     * 取前M大的数
     *
     * @param arr
     */
    public static int[] getMaxM(int[] arr, int M) {
        if (arr.length <= M) {
            return arr;
        }
        int[] heap = new int[M];
        for (int i = 0; i < M; i++) {
            heap[i] = Integer.MIN_VALUE;
        }
        for (int i = 0; i < arr.length; i++) {
            doPut(heap, arr[i]);
        }
        return heap;
    }

    /**
     * 往最小堆里插入元素，并且维护堆
     *
     * @param heap
     * @param num
     */
    public static void doPut(int[] heap, int num) {
        int index = 0;
        // 如果不大于堆顶，那么无需插入
        if (num <= heap[index]) {
            return;
        }
        // 与堆顶交换，堆顶出栈
        heap[index] = num;
        int size = heap.length;
        // 维护堆
        int left = index * 2 + 1;
        int right = index * 2 + 2;
        while (left < size) {
            // 右孩子越界，但是需要交换左孩子
            if (right >= size && heap[index] > heap[left]) {
                heap[index] = heap[index] ^ heap[left];
                heap[left] = heap[index] ^ heap[left];
                heap[index] = heap[left] ^ heap[index];
                index = left;
            } else {
                // 左右孩子都没有越界
                int min = heap[left] < heap[right] ? left : right;
                if (heap[min] < heap[index]) {
                    heap[index] = heap[index] ^ heap[min];
                    heap[min] = heap[index] ^ heap[min];
                    heap[index] = heap[min] ^ heap[index];
                    index = min;
                } else {
                    return;
                }
            }
            left = index * 2 + 1;
        }
    }
}