前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构之堆

数据结构之堆

作者头像
呼延十
发布2019-07-01 16:57:51
3570
发布2019-07-01 16:57:51
举报
文章被收录于专栏:呼延

介绍

堆(英语:heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:

  1. 堆中某个节点的值总是不大于或不小于其父节点的值;
  2. 堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

定义

堆的定义如下:

n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。

(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)

数据结构

在介绍中说,堆是一颗完全二叉树,那么你当然可以用二叉树的Node实现它.

但是,堆是一棵完全二叉树,那么就说明他的父节点和子节点是永远符合一个逻辑的,即i为父节点,他的子节点为:2*i+1和2i+2.

那么就可以使用线性数组来实现,一来可以节省后继节点的空间,二来在索引时更加迅速.

操作及实现代码(以大顶堆为例,测试数据[15, 13, 1, 5, 20, 12, 8, 9, 11 ])

对堆的操作主要有下面几种:

  1. 新建一个堆. —–从无序序列构造堆.
  2. 插入元素. —–在堆中插入元素,并调整堆.因为插入后可能破坏堆的性质.
  3. 删除元素. —–删除一个元素,并调整堆,删除元素也可能破坏堆的性质.
  4. 获取对顶元素. —–获取而不删除.

接下来将逐一分析上面四个操作并用代码进行实现.(由于相同操作较多,代码不适合放在每次个操作下,因此讲述完操作后统一贴代码.)

新建一个堆

新建一个堆,有两种思路:

  1. 先将第一个数据作为原始的堆,然后不断执行”insert”操作.
  2. 直接将所有数据形成完全二叉树,然后不断调整,使其符合堆的特性.

本文选用第二种方案.先形成完全二叉树,然后从最后一个非叶子节点开始,遍历所有的”有孩子节点的节点”,进行调整,直至调整到根节点.这是一种从下而上的调整策略.

如下图所示:

注意,图中在每个父节点,只调整了一次,这是选取的数据巧合.真正的调整方法为:将当前节点与其左右节点相比,取其中较大的值交换,然后递归的对与其交换的节点进行调整,直到没有交换或者到达叶子节点.

此时考虑的是,将当前调整的元素,下沉到合适的位置

插入元素

插入元素,直接在数据的最后一位添加一个元素,就相当于放在了堆的最后一位,然后调整此节点.调整方式为:将插入节点和父节点进行比较,如果大于父节点,则交换,然后递归的调整父节点.

如下图所示:

此时是将调整的元素上浮到合适的位置.

删除元素

删除元素是指移除堆顶元素,一般采用的方式是将堆顶元素和堆的最后一个元素交换,然后堆的元素减1.

之后,将堆顶元素下沉到合适的位置.

获取堆顶元素.

直接返回数组在[0]的元素即可.

全部代码

代码语言:javascript
复制
package heap;

import java.util.Arrays;

/**
 * created by huyanshi on 2019/1/16
 */
public class MaxHeap {


  public static void main(String[] args) {

    MaxHeap heap = new MaxHeap();

    int[] data = {15, 13, 1, 5, 20, 12, 8, 9, 11};
    // 测试建堆
    heap.buildMaxHeap(data, data.length);
    System.out.println(Arrays.toString(data));

    // 测试插入
    int[] newArr = heap.insert(data, 14, data.length);
    System.out.println(Arrays.toString(newArr));

    // 测试删除
    heap.delete(newArr, data.length + 1);
    System.out.println(Arrays.toString(newArr));
  }

  /**
   * 建立最大堆
   */
  private void buildMaxHeap(int[] array, int len) {
    //从最后一个非叶子节点开始,逐个节点向前进行下沉
    for (int i = (len / 2 - 1); i >= 0; i--) {
      down(array, len, i);
    }
  }

  /**
   * 插入元素
   */
  private int[] insert(int[] array, int a, int len) {
    //copy到新数组,长度加1,并将添加的值放入末尾
    int[] newArr = Arrays.copyOf(array, len + 1);
    newArr[len] = a;
    //对新加入的值进行上浮
    return up(newArr, len + 1, len);
  }

  /**
   * 删除元素
   */
  private void delete(int[] array, int len) {
    //交换第一个和最后一个节点
    exchange(array, 0, len - 1);
    //从根节点进行下沉
    down(array, len - 1, 0);
  }

  /**
   * 元素下沉
   */
  private void down(int[] array, int len, int i) {
    int maxIndex = i;
    //如果有左子树,且左子树大于父节点,则将最大指针指向左子树
    if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex]) {
      maxIndex = i * 2 + 1;
    }
    //如果有右子树,且右子树大于父节点,则将最大指针指向右子树
    if (i * 2 + 2 < len && array[i * 2 + 2] > array[maxIndex]) {
      maxIndex = i * 2 + 2;
    }
    //如果父节点不是最大值,则将父节点与最大值交换,并且递归调整与父节点交换的位置。
    if (maxIndex != i) {
      exchange(array, maxIndex, i);
      down(array, len, maxIndex);
    }
  }


  /**
   * 元素上浮
   */
  private int[] up(int[] array, int len, int i) {
    //如果上浮到根节点了,则结束
    if (i == 0) {
      return array;
    }
    //如果当前节点大于其父节点,则交换值,并且对其父节点进行上浮.
    if (array[i] > array[(i - 1) / 2]) {
      exchange(array, i, (i - 1) / 2);
      array = up(array, len, (i - 1) / 2);
    }
    return array;
  }

  /**
   * 交换数组在两个下标的值
   */
  private void exchange(int[] input, int i, int j) {
    int tmp = input[i];
    input[i] = input[j];
    input[j] = tmp;
  }

}

时间复杂度分析

建堆

建堆有两种方案:

  1. 逐一插入法. 时间复杂度为O(nlogn)
  2. 父节点逐一调整. 时间复杂度为O(n)

对于第二点的证明:

有n个节点,堆的高度为H=logn,那么对于最后一行的父节点,最多下沉一次,对于倒数第二行的父节点,最多下沉2次…..父节点最多下沉H次.

所以: s = 1 * 2^(H-1) + 2 * 2^(H-2) + ... + (H-1) * 2^1 + H * 2^0

带入H后可以算的O(n).

插入和删除

插入和删除都是对一个元素的调整,上浮或者下沉最多logn次.因此插入删除的时间复杂度为:O(logn).

完。

ChangeLog

2019-01-15 完成 2019-01-16 添加时间复杂度分析

以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com


本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 介绍
  • 定义
  • 数据结构
  • 操作及实现代码(以大顶堆为例,测试数据[15, 13, 1, 5, 20, 12, 8, 9, 11 ])
    • 新建一个堆
      • 插入元素
        • 建堆
        • 插入和删除
        • ChangeLog
    • 删除元素
    • 获取堆顶元素.
    • 全部代码
    • 时间复杂度分析
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档