数据结构之堆

介绍

堆(英语: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]的元素即可.

全部代码

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


本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券