文档章节

数据结构(堆)

翻个身原地打滚
 翻个身原地打滚
发布于 2019/12/14 21:39
字数 1967
阅读 18
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

定义:

    数据结构中的堆是一种特殊的二叉树。

    堆 必须符合以下两个条件:

  1. 是一棵完全二叉树。
  2. 任意一个节点的值都大于(或小于)左右子节点的值。

    从第一点可以知道,堆适合用数组来存储。

    第二点中,若父节点都大于等于左右子节点,则被称为大顶堆,反之则为 小顶堆。

 

堆的实现方案

    堆的存储

        完全二叉树采用数组存储最省空间,并且对 CPU 缓存 比 链表 友好。

        如图,采用数组表示并空出 0 号位置,节点i的父节点为2xi,左右子节点分别为i/2i/2+1

    堆的操作—插入数据

        在堆尾(即数组末尾)插入数据,会导致破坏堆的特性,如图:

    

        因此需要将被破坏的堆重新调整为堆,这个过程被称为堆化,堆化的操作可以自上而下,也可以自下而上。

        图中插入元素8后,打破了大顶堆的特性,将元素8向上与其父节点比较,判断是否交换,若交换,则继续向上比较,直到所有父子节点符合要求。

 

    代码实现(大顶堆):

public class Heap {
    private int[] heapData; // 数组,从下标 1 开始存储数据
    private int n;  // 堆可以存储的最大数据个数
    private int count; // 堆中已经存储的数据个数

    public Heap(int capacity) {
        heapData = new int[capacity + 1];
        n = capacity;
        count = 0;
    }

    public void insert(int data) {
        if (count >= n) 
    	    return; // 堆满了
        heapData[++count] = data;
        int i = count;
        while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化
            swap(heapData, i, i/2); //交换下标为 i 和 i/2 的两个元素
            i = i/2;
        }
    }
}

 

    堆的操作—删除堆顶元素

        如图,删除堆顶元素后,如何堆化?

        通过自上而下的堆化后,发现:虽然已经符合堆的大小规则,但是确不符合完全二叉树的定义了。

    改进

        删除堆顶元素后,将堆尾元素放到堆顶,再进行堆化操作。

 

    代码实现:

public void removeMax() {
    if (count == 0)
        return -1; // 堆中没有数据
    heapData[1] = heapData[count];
    --count;
    heapify(heapData, count, 1);
}

private void heapify(int[] heapData, int n, int i) { 
    // 自上往下堆化
    while (true) {
        int maxPos = i;
        int left = i*2;
        int right = i*2+1;
        if (left <= n && a[i] < heapData[left])
            maxPos = left;
        if (right <= n && heapData[maxPos] < heapData[right])
            maxPos = right;
        if (maxPos == i)
            break;
        swap(heapData, i, maxPos);
        i = maxPos;
    }
}

 

    堆化的时间复杂度分析:

        从前面的分析可知道,堆化的对象是一棵完全二叉树,并且自上而下或自下而上以高度为单位进行比较交换,因此堆化的时间复杂度与树的高度直接相关。

        完全二叉树的高度为:log2n,因此,删除、插入元素时间复杂度为 O(logN)。

 

堆的应用场景

    堆排序

        以大小为 K 的大顶堆为例,大顶堆的顶部元素为最大的值,我们将它与堆尾元素交换,再将前 K-1 个元素进行堆化,重复上述操作,直到堆中元素只剩 1 个为止,最后得到数据依次从小到大排列。

    代码实现:

// n 表示数据的个数,数组 heapData 中的数据从下标 1 到 n 的位置。
public static void heapSort(int[] heapData, int n) {
  buildHeap(heapData, n);//建堆
  int k = n;
  while (k > 1) {
    swap(heapData, 1, k);
    --k;
    heapify(heapData, k, 1);
  }
}

        由代码可知,堆排序是一种原地排序算法,因此,空间复杂度为O(1)。建堆过程时间复杂度为O(n),排序过程时间复杂度为O(nlog n),因此堆排序的时间复杂度为O(nlog n)。

        虽然堆排序的时间复杂度与快速排序一样,但是实际开发中依然还是采用快速排序比较多,为什么呢?

  • 堆排序在访问数组中元素时,是跳着访问的,因此对 CPU 缓存没有快速排序友好。
  • 同样的数据,堆排序的交换两个元素的次数比快速排序多。

 

    查找第K大(小)元素

        静态数据集合

            针对静态数据集合,我们可以通过数据集合建立大小为k的堆,若是大顶堆,则堆顶元素为第 k 小元素,否则为第 k 大元素。

        动态数据集合

            针对动态数据集合,我们可以一直维护一个大小为 k 的堆,增加元素时,将元素与堆顶元素比较,若为大顶堆,并且比对顶元素小,则替换,再堆化,得到新的第 k 小元素。

    题目:

        给定数字 K 和一组数据,每次插入一个数,得到插入后这组数据中的第 K 大 元素。

    解题思路

        维护一个大小为 K 的小顶堆,第 K 大元素,即为堆顶元素。

        同样,求第 K 小元素时,只需要维护一个大小为 K 的大顶堆即可,堆顶元素即为第 K 小元素。

 

    优先队列

        队列:先进先出,后进后出。优先队列:优先级高的先出队。

        堆可以直接看做一个优先队列,入队,即往堆中添加元素,并且按照优先级堆化,而出队时,即堆顶元素为优先级最高的元素。

        Java 中的 PriorityQueue 是优先级队列的一种实现。

 

    求动态集合中位数

        一组具有n个元素的有序数据中,若元素个数为偶数,则 n/2和 n/2 +1 位置的元素取一个作为中位数,若元素个数为偶数,则中位数在 n/2 + 1位置。

        对于静态数据,中位数是固定的,只需要排序后直接获取中位数即可。即便排序比较耗时,但只需一次排序,所以总体时间复杂度还能接受。

        但对于动态数据集合,由于数据是不断变化的,因此中位数也是不断变化的,若每次都需要重新排序来获取中位数,则时间复杂度比较高,因此,考虑采用同时维护两个堆来实现,大顶堆中存一半数据,小顶堆中存一半数据,并且小顶堆的数据都大于大顶堆的数据。

        1.元素个数为偶数时,取其中一个堆的堆顶元素即为中位数。

        2.元素个数为奇数时,大顶堆存 n/2 个数,小顶堆存 n/2+1个数,小顶堆堆顶元素为中位数。(也可以设置为大顶堆存 n/2+1 个数,则大顶堆堆顶元素为中位数)

        当数据增加时,导致两个堆的元素个数比例失调,所以,应该如何进行调整呢?

        可以从元素多的堆中,不停的将堆顶元素转移到另一个堆,直到两个堆元素比例恢复平衡,其中,堆化的操作时间复杂度为O(log n),而取中位数的操作的时间复杂度为O(1),因此整体时间复杂度为O(log n)。

    扩展

        在两个堆调整时,我们提到了两个堆的元素比例,在求中位数的场景中,比例为1:1。

        由此可以想到,是否可以求其他比例下的数据呢,比如,我们要求 60 百分位的数(假设有 100 个数,并且正序,第 60 个数即为 60 百分位的数),则大小顶堆的比例为3:2。

翻个身原地打滚
粉丝 19
博文 352
码字总数 597710
作品 0
虹口
程序员
私信 提问
代码生成器--Codgen

Codgen是一个基于数据库元数据模型,使用freemarker模板引擎来构建输出的代码生成器。freemarker的数据模型结构通常来说都是一个Map树状结构模型,codgen也不例外,它的数据模型这棵树的根节...

黄天政
2013/01/29
1.4W
2
C++模板库--C++ B-tree

这是一个google开源的C++模板库,实现了基于B-tree数据结构的有序内存容器。类似于STL的map、set、multimap和multiset模板,C++ B-tree也提供了btreemap、btreeset、btreemultimap和btreemu...

匿名
2013/02/05
3.4K
1
开源数据访问组件--Smark.Data

Smark.Data是基于Ado.net实现的数据访问组件,提供基于强类型的查询表达式进行灵活的数据查询,统计,修改和删除等操作;采用基于条件驱动的操作模式,使数据操作更简单轻松;内部通过标准SQL...

泥水佬
2013/03/12
2.6K
0
数据中心生命周期管理--Foreman

Foreman是一个集成的数据中心生命周期管理工具,提供了服务开通,配置管理以及报告 功能,和Puppet Dahboard一样,Foreman也是一个Ruby on Rails程序.Foreman和 Dashboard不同的地方是在于,Fore...

匿名
2012/10/24
1.5W
0
Python数据分析工具包--Pandas

Python Data Analysis Library 或 pandas 是连接 SciPy 和 NumPy 的一种工具,该工具是为了解决数据分析任务而创建的。Pandas 纳入了大量库和一些标准的数据模型,提供了高效地操作大型数据集...

匿名
2012/10/30
2.1W
2

没有更多内容

加载失败,请刷新页面

加载更多

微服务为什么选Spring Cloud?

现如今微服务架构十分流行,而采用微服务构建系统也会带来更清晰的业务划分和可扩展性。同时,支持微服务的技术栈也是多种多样的,本系列文章主要介绍这些技术中的翘楚——Spring Cloud。这是...

osc_6t6cjs45
18分钟前
32
0
后缀三姐妹

目录 写在前面 前置小碎骨 后缀数组 定义 举例 倍增法构造 优化 再优化 代码 后缀树 后缀自动机 写在最后 绝对不咕 写在前面 会考虑整个与标题相关的二次创作。 什么时候有能力再说 前置小碎...

osc_7e2pw1w9
19分钟前
8
0
主题搭建-初始化

方式一# 特点# 推荐的方式 项目做的任何升级都能远程推送到你的博客 支持在线切换项目中已经集成的所有皮肤 步骤# 1.你的博客首页 -> 管理 -> 设置 2.设置博客默认皮肤为 Custom 3.使用 load...

osc_lyz4aksj
20分钟前
0
0
我的前端知识体系构建(上)

❝ 前沿:树酱君是个渣渣,梳理了下发现还是蛮多知识点不够扎实,童鞋有机会也定期给自己做个复盘和回顾,梳理自己的知识体系。再加上前端娱乐圈变化多端,以至于我们既要加强对底层基础知识...

前端试炼
23分钟前
12
0
Codeforces Round #662 Div.2 (CF1392)

有人说这场背景描述挺烂,不过我觉得还不错( A题意有点烦,建议直接去看英文原文(( 手动画图然后推个结论,挺简单的,不赘述了: /*ID: LoxilanteTime: 2020/08/07Prog: CF1393A...

osc_5l7bcj86
22分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部