文档章节

数据结构(堆)

潦草的犀牛
 潦草的犀牛
发布于 2019/12/14 21:39
字数 1967
阅读 8
收藏 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。

本文转载自:https://blog.csdn.net/m0_37264516/article/details/84941656

潦草的犀牛
粉丝 16
博文 293
码字总数 589852
作品 0
虹口
程序员
私信 提问
堆和栈(Java数据结构)

堆 常见使用场景: (英语:heap)亦被称为: 优先队列 (英语:priority queue),是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中,调度程序反...

晓阳
2015/10/14
95
0
关于PriorityQueue 二叉堆的问题

场景:最近在研究java中的队列,当研究到优先队列的时候去读 PriorityQueue的源码的时候发现一种数据结构,我数据结构这块基本上上是空白,所以让我晦涩难懂啊,于是我查阅了大量资料以及手动...

skyline520
2013/06/01
924
0
【从蛋壳到满天飞】JS 数据结构解析和算法实现-堆和优先队列(一)

前言 【从蛋壳到满天飞】JS 数据结构解析和算法实现,全部文章大概的内容如下: Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜...

哎哟迪奥
2019/03/26
0
0
LeetCode题集整理- 栈、队列、堆

1、预备知识点 栈(Stack)和队列(Queue)是两种操作受限的线性表。 (线性表:线性表是一种线性结构,它是一个含有n≥0个结点的有限序列,同一个线性表中的数据元素数据类型相同并且满足“...

Blank_佐毅
2017/11/28
0
0
源码阅读(12):Java中主要的Queue、Deque结构——PriorityQueue集合(上)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 https://blog.csdn.net/yinwenjie/article/details/99655861 (接上文《源码阅读(11):Java中...

说好不能打脸
2019/08/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Kettle自定义jar包供javascript使用

我们都知道 Kettle 是用 Java 语言开发,并且可以在 JavaScript 里面直接调用 java 类方法。所以有些时候,我们可以自定义一些方法,来供 JavaScript 使用。 本篇文章有参考自:https://www...

CREATE_17
昨天
102
0
处理CSV文件中的逗号

我正在寻找有关如何处理正在创建的csv文件的建议,然后由我们的客户上传,并且该值可能带有逗号(例如公司名称)。 我们正在研究的一些想法是:带引号的标识符(值“,”值“,”等)或使用|...

javail
昨天
79
0
如何克隆一个Date对象?

将Date变量分配给另一个变量会将引用复制到同一实例。 这意味着更改一个将更改另一个。 如何实际克隆或复制Date实例? #1楼 简化版: Date.prototype.clone = function () { return new ...

技术盛宴
昨天
73
0
计算一个数的数位之和

计算一个数的数位之和 例如:128 :1+2+8 = 11 public int numSum(int num) { int sum = 0; do { sum += num % 10; } while ((num = num / 10) > 0); return sum;......

SongAlone
昨天
124
0
为什么图片反复压缩后普遍会变绿,而不是其他颜色?

作者:Lion Yang 链接:https://www.zhihu.com/question/29355920/answer/119088684 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 业余版概要:安卓的...

shzwork
昨天
81
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部