算法-大顶堆和小顶堆

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

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

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

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

左节点:left = 2 * index + 1;

右节点:right = 2 * index + 2;

数组生成大顶堆

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

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

从最后一个非叶结点开始生成大顶堆。最后一个非叶结点:(len - 1)/2len/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)/2len/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%