算法-大顶堆和小顶堆

发表于 更新于 分类于 Disqus：
如何通过一个无序数组构建一个大顶堆或小顶堆，进而实现诸如堆排序，topN算法。

堆可以看成是一个完全二叉树。

大顶堆：如果该完全二叉树满足双亲结点大于等于孩子节点，则这样的堆，称之为大顶堆。

小顶堆：如果该完全二叉树满足双亲结点小于等于孩子节点，则这样的堆，称之为小顶堆。

对于一个由二叉树生成的大顶堆或小顶堆（完全二叉树），若堆中的一个非叶子节点对应数组的下标索引为index，则这个节点的左右子节点和index有如下对应关系：

​ 左节点：left = 2 * index + 1;

​ 右节点：right = 2 * index + 2;

数组生成大顶堆

非叶结点index > 左结点：2 * index + 1

非叶结点index > 右结点：2 * index + 2

从最后一个非叶结点开始生成大顶堆。最后一个非叶结点：(len - 1)/2或len/2 - 1。

代码实现

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
private void buidMaxHeap(int[] array) {
  // 最后一个非叶结点
  int start = array.length/2 - 1;
  for(int i = start; i >= 0; i--) {
    maxHeap(array, array.length, i);
  }
}

private void maxHeap(int[] array, int size, int index) {
  // 左孩子
  int left = 2 * index + 1;
  // 右孩子
  int right = 2 * index + 2;
  int max = index;
  
  // 通过比较当前结点和左右孩子，找到最大的结点
  if(left < size && array[left] > array[max]) {
    max = left;
  }
  if(rigth < size && array[right] > array[max]) {
    max = right;
  }
  // 最大结点与当前结点进行交换
  if(max != index) {
    int tmp = array[index];
    array[index] = array[max];
    array[max] = tmp;
    // 继续构建
    maxHeap(array, size, max);
  }
}

示例

对于如下的一个无序数组：

1
int[] arr = new int[]{9,6,8,7,0,1,10,4,2};

通过构建大顶堆，输出结果如下：

1
10,7,9,6,0,1,8,4,2

对应的堆结构变化如下：

生成后：

数组生成小顶堆

小顶堆的生成和大顶堆类似，特点如下：

非叶结点index < 左结点：2 * index + 1

非叶结点index < 右结点：2 * index + 2

从最后一个非叶结点开始生成大顶堆。最后一个非叶结点：(len - 1)/2或len/2 - 1。

代码实现

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
private void buidMinHeap(int[] array) {
  // 最后一个非叶结点
  int start = array.length/2 - 1;
  for(int i = start; i >= 0; i--) {
    minHeap(array, array.length, i);
  }
}

private void minHeap(int[] array, int size, int index) {
  // 左孩子
  int left = 2 * index + 1;
  // 右孩子
  int right = 2 * index + 2;
  int min = index;
  
  // 通过比较当前结点和左右孩子，找到最小的结点
  if(left < size && array[left] < array[min]) {
    min = left;
  }
  if(rigth < size && array[right] > array[min]) {
    min = right;
  }
  // 最小结点与当前结点进行交换
  if(min != index) {
    int tmp = array[index];
    array[index] = array[min];
    array[min] = tmp;
    // 继续构建
    maxHeap(array, size, min);
  }
}

示例

对于如下的一个无序数组：

1
int[] arr = new int[]{9,6,8,7,0,1,10,4,2};

通过构建大顶堆，输出结果如下：

1
0,2,1,4,6,8,10,9,7

对应的堆结构变化如下：

生成后：

应用

topN

对于大顶堆来说，前N位就是数组中最大的N个数，对于小顶堆来说，前N位就是数组中最小的N个数。

堆排序

  1. 升序：需要构建大顶堆，即根节点为最大的结点，交换根节点和最后一个元素，即可生成升序数组。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public void ascHeapSort(int[] array) {
      int len = array.length;
      if(array == null || len = 1) {
        return;
      }
      
      buildMaxHeap(array);
      
      while(len > 0) {
        swap(array, 0, len - 1);
        len--;
        maxHeap(array, len, 0);
      }
    }

  2. 降序：需要构建小顶堆，即根节点为最小的结点，交换根节点和最后一个元素，即可生成降序数组。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public void descHeapSort(int[] array) {
      int len = array.length;
      if(array == null || len = 1) {
        return;
      }
      
      buildMinHeap(array);
      
      while(len > 0) {
        swap(array, 0, len - 1);
        len--;
        minHeap(array, len, 0);
      }
    }
0%