不想说话,自闭中..

数据结构之堆

前言

堆也是一种特殊的数据结构,是一种特殊形式的完全二叉树。

堆分为两种:大顶堆(每个节点的值都不大于其父节点的值,也就是根节点的值是最大的)和小顶堆(每个节点的值都不小于其父节点的值,也就是根节点的值是最小的)。

堆的基本操作(以大顶堆为例)

既然堆本身是完全二叉树,所以我们可以使用一维数组的方式进行储存。0位置用来存储元素的个数,1~n用来存储元素。

所以对于任意一个元素i来说 ,如果它有左孩子,那么它的左孩子值可以是2i;如果它有右孩子,那么右孩子可以是2i+1。

  • 创建堆

    声明一个可包含最大元素数量的数组的堆,这里需要比最大数量大1,把下标为0的位置用来存储当前堆中元素的个数。

1
2
3
4
5
6
7
8
/**
* 创建堆
* @param maxSize
*/
public MyHeap(int maxSize) {
element = new int[maxSize + 1];
element[0] = 0;
}
  • 是否为空堆

    直接判断下标为0的元素的值是否为0即可。

1
2
3
4
5
6
7
/**
* 判断堆是否为空
* @return
*/
public boolean isEmpty() {
return element[0] == 0;
}
  • 是否堆满

    判断下标为0元素的值是否等于数组长度-1即可。

1
2
3
4
5
6
7
/**
* 判断是否堆满
* @return
*/
public boolean ifFull() {
return element[0] == element.length -1;
}
  • 插入元素

    如果是一个空堆,直接插入元素即可;如果不是空堆,就需要和自己的父节点进行比较,如果大于父节点,那么就需要交换位置,接着继续和自己新的父节点进行比较和交换,直到小于等于自己的父节点或者根节点为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 插入元素
* @param value
*/
public void insert(int value) {
if (this.ifFull()) {
throw new IndexOutOfBoundsException("大顶堆已经满了");
}
if (this.isEmpty()) {
element[1] = value;
} else {
//确定新增元素的下标
int i = element[0] + 1;
while (i != 1 && value > element[i / 2]) {
//如果比父节点值大,则父节点的值下移
element[i] = element[i / 2];
i /= 2;
}
//最终把值插入指定位置
element[i] = value;
}
element[0] ++;
}
  • 删除堆中最大的元素(即删除根节点元素)

    堆的删操作删除的都是根节点,那么需要考虑的就是根节点被删除之后怎么再重建堆。
    为了便于操作,我们一般都是先把数组的最后一个有效元素拿到下标为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
32
33
34
35
/**
* 删除大顶堆的根节点元素
*/
public int delete() {
if (this.isEmpty()) {
throw new IndexOutOfBoundsException("大顶堆已经空了");
}
//删除元素,先赋值为最后一个有效元素
int deleteElement = element[1];
element[1] = element[element[0]];
element[0] --;
int temp = element[1];
//重建堆
int parent = 1;
int child = 2;
//循环至叶子节点
while (child <= element[0]) {
if (child < element[0] && element[child] < element[child+1]) {
//首先要确保child+1之后不能越界,
//接着如果左孩子的值小于右孩子的值,那么选择使用右孩子进行比较和交换
child ++;
}
if (temp > element[child]) {
break;
} else {
element[parent] = element[child];
parent = child;
child *= 2;
}
}
//把最后一个有效元素放到该放的位置
element[parent] = temp;

return deleteElement;
}
  • 打印堆内信息
1
2
3
4
5
6
7
8
9
10
11
12
/**
* 打印堆内信息
*/
public void printAll() {
for (int i = 0; i < element[0] + 1; i++) {
System.out.print(element[i]);
if (i != element[0]) {
System.out.print(",");
}
}
System.out.println();
}

测试与运行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class TestMyHeap {
public static void main(String[] args) {
MyHeap heap = new MyHeap(100);
heap.insert(9);
heap.insert(18);
heap.insert(34);
heap.insert(15);
heap.insert(29);
heap.insert(66);
heap.insert(12);
heap.insert(48);

heap.printAll();

heap.delete();
heap.printAll();

}
}

这里写图片描述

堆的性能分析

堆的主要优势是插入和删除操作。

时间复杂度都为O(logn)。