堆(Heap)

概念

  • 堆是一个完全二叉树（即如果以数组的形式存储的话，是一个连续数组）。
  • 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
    堆

分类

  • 大顶堆：每个节点的值都大于等于子树中每个节点值的堆。
  • 小顶堆：对于每个节点的值都小于等于子树中每个节点值的堆。

操作

关键词：堆化（heapify）。堆化，通俗点讲就是，对堆进行操作之后，将堆中的元素进行调整，使其满足堆的要求。其中，又分为从下往上堆化和从上往下堆化。

在堆中插入一个元素和删除堆顶元素的时间复杂度均为O(logn)。

关键点（假设数组的第一个元素坐标为1，当前节点为i）

  • 左子节点：2 * i
  • 右子节点：2 * i + 1
  • 父节点：i/2

    同理，若将数组第一个元素的下标视为0，则左子节点为2i+1，右子节点为2i+2，父节点为(i-1)/2。

往堆中插入一个元素

图示

  1. 将新的元素data放在堆的末位（i）；
  2. 从下往上堆化：将该元素与其父节点（i/2）进行比较，若不满足大小关系，则进行交换（swap）操作。直到满足关系不用交换为止。
    insert

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Heap {
  private int[] a; // 数组，从下标1开始存储数据
  private int n;  // 堆可以存储的最大数据个数
  private int count; // 堆中已经存储的数据个数

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

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

删除堆顶元素

图示

  1. 删除堆顶的元素，将堆末的元素放到堆顶。
  2. 从上往下堆化：从堆顶（i）（初始节点为1）开始，分别与其左节点（i * 2）和右节点（i * 2 + 1）进行比较。若与其中一个不满足大小关系，则与其进行交换（swap）；若与两者均不满足大小关系，则与其中较大者进行交换（swap）。直到满足关系不用交换为止。
    delete

    代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public void removeMax() {
      if (count == 0) return -1; // 堆中没有数据
      a[1] = a[count];
      --count;
      heapify(a, count, 1);
    }

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

堆排序

堆排序的过程大致分为两步：建堆和排序。建堆其实就是将一个普通的数组“堆化”，排序，则是在大小为n的堆中，每次将堆顶元素与堆末位进行交换，然后对n-1的数组进行堆化，重复上面的操作。

堆排序的时间复杂度为O(nlogn)。

建堆

图示

从最后一个非叶子节点（n/2）开始，从下到上进行堆化。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static void buildHeap(int[] a, int n) {
  for (int i = n/2; i >= 1; --i) {
    heapify(a, n, i);
  }
}
private static void heapify(int[] a, int n, int i) {
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}

排序

图示

  1. 假设数组为n且已经“建堆”。
  2. 先将堆顶元素与堆末元素进行交换（swap），然后在堆顶处从上到下，将数组n-1中进行堆化（类比删除堆顶元素操作）。

    代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // n表示数据的个数，数组a中的数据从下标1到n的位置。
    public static void sort(int[] a, int n) {
      buildHeap(a, n);
      int k = n;
      while (k > 1) {
        swap(a, 1, k);
        --k;
        heapify(a, k, 1);
      }
    }

堆的应用

优先级队列

合并有序小文件

高性能定时器

Top K问题

维护一个K大小的小顶堆，遍历数组n，若取出的数比堆顶元素大，则删除堆顶元素，将取出的数插入堆中；若比堆顶元素小则不处理。

适用于数组n为静态及动态的情况。

中位数问题