基于"堆"的底层实现和应用

栏目: 编程工具 · 发布时间: 5年前

内容简介：Precious time, which cannot be recovered once lost.堆是一种特殊的树（完全二叉树）。本地主要分享了堆的实现原理，基于堆的排序以及堆的几个应用。所有源码均已上传至github：对于每个节点的值都大于等于子树中每个节点值的堆。

Precious time, which cannot be recovered once lost.

堆是一种特殊的树（完全二叉树）。本地主要分享了堆的实现原理，基于堆的排序以及堆的几个应用。所有源码均已上传至github：链接

准备

堆的定义：

必须是一个完全二叉树
堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

大顶堆：

对于每个节点的值都大于等于子树中每个节点值的堆。

小顶堆：

对于每个节点的值都小于等于子树中每个节点值的堆。

ps：堆化是堆的核心思想,想彻底了解堆排序，只需要学会堆化即可。

实现一个大顶堆（小顶堆的实现在github上）

初始化

从下标1开始存储数据 a[0]相当于一个哨兵

private MinHeap(int capacity) {
        arrays = new int[++capacity];
        size = capacity;
        count = 0;
    }复制代码

插入

这里涉及到一个堆化的问题。while循环不断得比较插入的数据和之前堆中的数据大小。满足条件则进行交换。

private void insert(int data) {
        if (count >= size) return;
        arrays[++count] = data;
        int i = count;
        while (i / 2 > 0 && arrays[i] < arrays[i / 2]) {
            swap(arrays, i, i / 2);
            i = i / 2;
        }
    }复制代码

删除

为什么堆也叫优先级队列呢，也正因为它也是有线性操作的，删除只能删除堆顶元素。

这是 arrays[1] = arrays[count];是删除堆顶元素前，先取最后一个元素塞入堆顶，然后进行堆化，防止出现 数组空洞 。

private void removeMin() {
        if (count == 0) return;
        arrays[1] = arrays[count];
        --count;
        heapify(arrays, count, 1);
    }复制代码

堆化有两种：自下向上堆化和自上向下堆化。这里以自上向下堆化为例。

private void heapify(int[] arrays, int count, int i) {
        while (true) {
            int max = i;
            if (i * 2 < count && arrays[i] > arrays[i * 2]) max = i * 2;
            if (i * 2 + 1 <= count && arrays[max] > arrays[i * 2 + 1]) max = i * 2 + 1;
            if (max == i) break;
            swap(arrays, i, max);
            i = max;
        }
    }复制代码

交换满足条件的元素

private void swap(int[] arrays, int p, int q) {
        int temp = arrays[p];
        arrays[p] = arrays[q];
        arrays[q] = temp;
    }复制代码

测试代码

public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(10);
        for (int i = 10; i > 0; --i) {
            minHeap.insert(i);
        }
        System.out.println("小顶堆:");
        minHeap.printAll();
        System.out.println("删除堆顶元素后:");
        minHeap.removeMin();
        minHeap.printAll();
    }复制代码

测试结果

堆排序

建堆

先将一个无序数组自上向下堆化，从前往上处理数据变成一个堆。

时间复杂度O(n)

private void buildHeap(int[] arrays, int size) {
        for (int i = size / 2; i > 0; --i) {
            heapify(arrays, size, i);
        }
    }复制代码

排序

类似于删除堆顶元素，然后再将这个堆（size-1）再堆化，利两两比较，不停的交换元素，以此类推。

时间复杂度O(nlogn)

private void sort() {
        buildHeap(arrays, count);
        System.out.println("建堆后:");
        printAll();
        int i = count;
        while (i > 1) {
            swap(arrays, 1, i--);
            heapify(arrays, i, 1);
        }
    }复制代码

测试代码

maxHeap.sort();
        System.out.println("排序后:");
        maxHeap.printAll();复制代码

测试结果

求一组动态数据集合的最大 Top K

思考

针对静态数据，如何在一个包含 n 个数据的数组中，查找前 K 大数据呢？可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出取数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。

topK

这里为了更简便一些，用到了java PriorityQueue （优先队列的完全体）

首先声明一个大小为k的优先队列PriorityQueue，然后循环arrays数组，先添加k个数(理解这k个数已经满足要求了)
其次在[k+1,arrays.length]这个范围内，开始逐个与小顶堆的堆顶进行比较，满足条件则交换
最后将PriorityQueue的数据以此取出即可

offer 添加一个元素并返回true 如果队列已满，则返回false

poll 移除并返问队列头部的元素如果队列为空，则返回null

peek 返回队列头部的元素如果队列为空，则返回null

private int[] topK(int[] arrays,int k){
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k);
        for (int i = 0; i < arrays.length; i++) {
            if (priorityQueue.size() < k){
                priorityQueue.offer(arrays[i]);
            }else{
                int value = priorityQueue.peek();
                if (arrays[i] > value){
                    priorityQueue.poll();
                    priorityQueue.offer(arrays[i]);
                }
            }
        }
        int[] result = new int[k];
        int index = 0;
        while (!priorityQueue.isEmpty()){
            result[index++] = priorityQueue.poll();
        }
        return result;
    }复制代码

测试代码

public static void main(String[] args) {
        GetTopKArrays getTopKArrays = new GetTopKArrays();
        int[] arrays = new int[10];
        for (int i = 0; i <10 ; i++) {
            arrays[i] = i;
        }
        System.out.println("一组动态数据:");
        getTopKArrays.print(arrays);
        int k = 3;
        int[] result = getTopKArrays.topK(arrays,k);
        System.out.println("前三的数据为:");
        getTopKArrays.print(result);
    }
}复制代码

测试结果

求一组动态数据集合的中位数

维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。

初始化

public Median(int capacity) {
        maxHeap = new MaxHeap(capacity);
        minHeap = new MinHeap(capacity);
        count = 0;
    }复制代码

插入

堆空，插入大顶堆
data比大顶堆元素大插入小顶堆，否则插入大顶堆
如果大顶堆（小顶堆）的数据数量超过了中间值，则需要平衡，移动数据数量多的堆。

private void insert(int data) {
        ++count;
        if (maxHeap.count == 0 && minHeap.count == 0) {
            maxHeap.insert(data);
            return;
        }
        int max = maxHeap.removeMax();
        if (data > max) {
            maxHeap.insert(max);
            maxHeap.insert(data);
        } else {
            maxHeap.insert(max);
            minHeap.insert(data);
        }
        int mid = count / 2;
        if (maxHeap.count > mid) {
            moveMaxMin(maxHeap, minHeap, maxHeap.count - mid);
        }
        if (minHeap.count > mid) {
            moveMinMax(maxHeap, minHeap, minHeap.count - mid);
        }
    }复制代码

移动

因为这里是基于上面的堆的实现，没有封装彻底，因此手动实现

private void moveMaxMin(MaxHeap maxHeap, MinHeap minHeap, int index) {
        for (int i = 0; i < index; i++) {
            int data = maxHeap.removeMax();
            minHeap.insert(data);
        }
    }
	private void moveMinMax(MaxHeap maxHeap, MinHeap minHeap, int index) {
        for (int i = 0; i < index; i++) {
            int data = minHeap.removeMin();
            maxHeap.insert(data);
        }
    }复制代码

测试代码

public static void main(String[] args) {
        int capacity = 10;
        Median median = new Median(5);
        for (int i = 1; i < capacity; i++) {
            median.insert(i);
        }
        System.out.println("大顶堆:");
        median.maxHeap.printAll();
        System.out.println("小顶堆:");
        median.minHeap.printAll();
        int midNum = median.maxHeap.removeMax();
        System.out.println("中位数为:" + midNum);
    }复制代码