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

栏目: 编程工具 · 发布时间: 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 (优先队列的完全体)

  1. 首先声明一个大小为k的优先队列PriorityQueue,然后循环arrays数组,先添加k个数(理解这k个数已经满足要求了)
  2. 其次在[k+1,arrays.length]这个范围内,开始逐个与小顶堆的堆顶进行比较,满足条件则交换
  3. 最后将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;
    }复制代码

插入

  1. 堆空,插入大顶堆
  2. data比大顶堆元素大插入小顶堆,否则插入大顶堆
  3. 如果大顶堆(小顶堆)的数据数量超过了中间值,则需要平衡,移动数据数量多的堆。
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);
    }复制代码

测试结果

基于

end

基于

您的点赞和关注是对我最大的支持,谢谢!


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

STL源码剖析

STL源码剖析

侯捷 / 华中科技大学出版社 / 2002-6 / 68.00元

学习编程的人都知道,阅读、剖析名家代码乃是提高水平的捷径。源码之前,了无秘密。大师们的缜密思维、经验结晶、技术思路、独到风格,都原原本本体现在源码之中。 这本书所呈现的源码,使读者看到vector的实现、list的实现、heap的实现、deque的实现、Red Black tree的实现、hash table的实现、set/map的实现;看到各种算法(排序、查找、排列组合、数据移动与复制技术......一起来看看 《STL源码剖析》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试