数据结构 - 堆

Heap

2018-02-09 约 2857 字预计阅读 6 分钟

堆（英语：Heap）是计算机科学中的一种特别的完全二叉树。若是满足以下特性，即可称为堆：“给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于（或大于等于）C的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。

堆始于J. W. J. Williams在1964年发表的堆排序（heap sort），当时他提出了二叉堆树作为此算法的数据结构。

性质

堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质。

任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。
堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆有许多种高级类型包含了适合制作双端队列的最大—最小堆及制作优先权队列的斐波那契堆等。

堆序性（英文：heap order）在最大堆中，父节点的值比每一个子节点的值都要大。在最小堆中，父节点的值比每一个子节点的值都要小。

堆和普通树的区别

堆并不能取代二叉搜索树，它们之间有相似之处也有一些不同。我们来看一下两者的主要差别：

节点的顺序。在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。

内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配内存。堆仅仅使用一个数据来存储数组，且不使用指针。

平衡。二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足堆属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。

搜索。在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。

来自数组的数

堆就是用数组实现的特别的完全二叉树，所以它没有使用父指针或者子指针。

1
2
3
4


// i 是数组索引
parent(i) = floor((i - 1)/2)
leftChild(i)   = 2i + 1
rightChild(i)  = 2i + 2

注意：根节点没有父节点 -1 不是一个有效数组索引；叶子节点没有子节点，这些索引操作数组大小，处理这些节点需要保证索引是有效的。

支持的基本操作

操作	描述	时间复杂度
build	采用罗伯特·弗洛伊德提出的较快方式创建堆	O(n)
insert	向堆中插入一个新元素	O(log n)
update	将新元素提升使其符合堆的性质	O(log n)
get	获取当前堆顶元素的值	O(1)
delete	删除堆顶元素	O(log n)
heapify	使删除堆顶元素的堆再次成为堆	O(log n)

某些堆实现还支持其他的一些操作，如斐波那契堆支持检查一个堆中是否存在某个元素。

原始操作

有两个原始操作用于保证插入或删除节点以后堆是一个有效的最大堆或者最小堆：

shiftUp(): 如果一个节点比它的父节点大（最大堆）或者小（最小堆），那么需要将它同父节点交换位置。这样是这个节点在数组的位置上升。
shiftDown(): 如果一个节点比它的子节点小（最大堆）或者大（最小堆），那么需要将它向下移动。这个操作也称作“堆化（heapify）”。

shiftUp 或者 shiftDown 是一个递归的过程，所以它的时间复杂度是 O(log n)。

shiftUp 向上调整算法

下面我们给出两个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

先设定倒数的第一个叶子节点为当前节点(通过下标获取，标记为cur)，找出他的父亲节点，用parent来标记。
比较parent和cur的值，如果cur比parent小，则不满足小堆的规则，需要进行交换。
如果cur比parent大，满足小堆的规则，不需要交换，调整结束。
处理完一个节点之后，从当前的parent出发，循环之前的过程。

shiftDown 向下调整算法

先设定根节点为当前节点(通过下标获取，标记为cur)，比较左右子树的值，找出更小的值，用child来标记。
比较child和cur的值，如果child比cur小，则不满足小堆的规则，需要进行交换。
如果child比cur大，满足小堆的规则，不需要交换，调整结束。
处理完一个节点之后，从当前的child出发，循环之前的过程。

插入

将数据插入到数组最后，再进行向上调整修复堆序性。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


  public boolean offer(E e) {
    if (e == null) {
      throw new NullPointerException();
    } else {
      ++this.modCount;
      int i = this.size;
      if (i >= this.queue.length) {
        this.grow(i + 1);
      }

      this.siftUp(i, e);
      this.size = i + 1;
      return true;
    }
  }

删除根节点

删除堆顶的数据。取出数组中的最后一个元素，将它放到树的顶部，然后再进行向下调整算法修复堆属性。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


  public E poll() {
    Object[] es;
    Object result;
    if ((result = (es = this.queue)[0]) != null) {
      ++this.modCount;
      int n;
      E x = es[n = --this.size];
      es[n] = null;
      if (n > 0) {
        Comparator cmp;
        if ((cmp = this.comparator) == null) {
          siftDownComparable(0, x, es, n);
        } else {
          siftDownUsingComparator(0, x, es, n, cmp);
        }
      }
    }

    return result;
  }

删除任意节点

绝大多数时候你需要删除的是堆的根节点，因为这就是堆的设计用途。

但是，删除任意节点也很有用。这是 remove() 的通用版本，它可能会使用到 shiftDown 和 shiftUp。

将删除元素与最后一个元素交换
删除最后一个元素
然后根据最后元素根据堆序性选择 shiftDown 或 shiftUp

heapify()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


private void heapify() {
    Object[] es = this.queue;
    int n = this.size;
    int i = (n >>> 1) - 1;
    Comparator cmp;
    if ((cmp = this.comparator) == null) {
      while(i >= 0) {
        siftDownComparable(i, es[i], es, n);
        --i;
      }
    } else {
      while(i >= 0) {
        siftDownUsingComparator(i, es[i], es, n, cmp);
        --i;
      }
    }

  }

private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
    Comparable<? super T> key = (Comparable)x;

    int child;
    for(int half = n >>> 1; k < half; k = child) {
      child = (k << 1) + 1;
      Object c = es[child];
      int right = child + 1;
      if (right < n && ((Comparable)c).compareTo(es[right]) > 0) {
        child = right;
        c = es[right];
      }

      if (key.compareTo(c) <= 0) {
        break;
      }

      es[k] = c;
    }

    es[k] = key;
  }

构建最大堆模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


public void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    public void maxHeapify(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

应用

堆排序

堆（通常是二叉堆）常用于排序。这种算法称作堆排序。

基本思想：

将待排序序列构造成一个大顶堆
此时，整个序列的最大值就是堆顶的根节点。
将其与末尾元素进行交换，此时末尾就为最大值。
然后将剩余n-1个元素重新构造成一个堆，这样会得到n-1个元素的次小值。如此反复执行，便能得到一个有序序列了。

事件模拟

主要运用堆的排序以选择优先。

优先权队列

在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的最佳数据结构。

Dijkstra 算法

在迪杰斯特拉算法中使用斐波那契堆或二元堆可使得队列的操作更为快速。

目录