首页 > 代码库 > 堆 续4
堆 续4
--------------------siwuxie095
索引堆
这里介绍一个比普通堆更加高级的数据结构:索引堆(Index Heap)
首先来看一下普通堆有什么问题 或 缺点:
将一个数组通过 Heapify 构建成一个堆,对于这个数组而言,
在堆构建前和堆构建后,它的元素位置发生了改变,正是因为
元素位置的改变,才使得它被看做是一个堆
但在构建堆的过程中,改变元素的位置将会有一些局限性:
(1)如果元素是非常复杂的结构,如:元素是字符串,那么交换这些元素
本身,消耗就是巨大的
比如说:如果每一个元素都是一篇有十万字的文章,那么对于这些巨型的字
符串,让它们来回交换会产生大量的性能上的消耗
不过这种性能上的消耗,还可以使用技术手段来解决,另一个问题可能相对
就更加致命
(2)由于元素在数组中的位置发生了改变,使得堆建成以后很难索引到它,
当难以索引到元素时,就很难去改变它
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
- |
15 |
17 |
19 |
13 |
22 |
16 |
28 |
30 |
41 |
62 |
比如说:这个数组里的元素表示一个一个的系统任务,可能在初始的
时候,索引表示进程的 ID 号(从 1 开始),元素表示的是优先级
(每一个进程都表示一个系统任务)
可是当把这个表示系统任务的数组构建成堆之后,这些元素的索引和
系统任务之间就不再产生关联了
如果现在想提升原来进程的 ID 号为 6 的那个系统任务的优先级,应
该怎么做?
这个操作就变的非常难,在以前的数组中,可以用 O(1) 的性能效率
直接将这个任务提取出来,但当把它组建成堆以后,元素的位置发生
了改变,索引不到了
有人可能会说,在这个元素里再添加一个属性,来表示 ID 号就好了
这样的确可以解决,但要将整个数组遍历一遍,才能够找到相应的进
程,这个性能也是低效的
为此,就需要引入索引堆来解决这个问题
什么是索引堆?
其实非常简单,对于索引堆来说:
数据 data 和索引 index 这两部分内容分开存储,而真正表征
堆的数组是由索引 index 构建成的
以最大索引堆为例(索引从 1 开始):
数组在初始情况下:
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
index |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
data |
15 |
17 |
19 |
13 |
22 |
16 |
28 |
30 |
41 |
62 |
当将数组构建成堆以后:
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
index |
10 |
9 |
5 |
7 |
8 |
6 |
2 |
4 |
3 |
1 |
data |
15 |
17 |
19 |
13 |
22 |
16 |
28 |
30 |
41 |
62 |
对于 data 域来说,它们没有发生任何改变,真正改变的是 index 域,
这个 index 数组发生了改变,形成了一个堆
这个堆怎么解读呢?堆顶的元素为 10,实际指向的是 10 这个 index
所指向的 data,也就是 62,相应的堆顶元素有左孩子和右孩子,左
孩子的元素为 9,实际指向的是 41,右孩子的元素是 7,实际指向的
是 28 … 依此类推
这样一来,可以观察到索引堆的两个好处:
(1)构建堆的过程只是索引 index 的位置发生交换
索引 index 就是一个简单的 int 型,如果数据 data 是非常复杂的结构,
只交换 int 型的索引 index,交换效率非常高
(2)如果现在想对堆中的数据进行一个操作,如:修改 index 为 7 的
data,也就是 28,修改完后,相应的还要做一些维护的操作来维持堆
的性质,那么维持堆的性质只是根据新的 data 数组来改变 index 数组
即可
简而言之:索引堆比较的是 data,交换的是 index
索引堆的优化
在修改数据 data 时是从外部传入进来一个索引来修改 data 数组,
而在维护索引堆的过程中,要先用 O(n) 的时间来遍历 index 数组
找到传入进来的索引的位置
如果要修改 n 个 data,算法的时间复杂度就是 O(n^2) 级别的
所以可以通过 反向查找 的方式来进行优化,在查找时就可以直接
用 O(1) 的时间找到传入进来的索引在 index 数组中的位置
如果要修改 n 个 data,算法的时间复杂度就是 O(n*lgn) 级别的
以最大索引堆为例(索引从 1 开始):
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
index |
10 |
9 |
5 |
7 |
8 |
6 |
2 |
4 |
3 |
1 |
data |
15 |
17 |
19 |
13 |
22 |
16 |
28 |
30 |
41 |
62 |
reverse |
10 |
7 |
9 |
8 |
3 |
6 |
4 |
5 |
2 |
1 |
其中:reverse[i] 表示 index 为 i 的值在堆中的位置
另,有公式如下:
(1)index[i]=j
(2)reverse[j]=i
(3)index[reverse[i]]=i
(4)reverse[index[i]]=i
【made by siwuxie095】
堆 续4