首页 > 代码库 > 堆 续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

4reverse[index[i]]=i

   

   

   

   

 

   

   

   

【made by siwuxie095】

堆 续4