索引堆的优化之处
在前面的堆排序当中，学习了堆排序，并且基于数组创建了堆。但以数组作为二叉树创建的堆，在排序过程中直接移动了元素来完成排序，这样的操作有一下几个局限性：
- 排序时直接移动了元素，若元素本身的内容非常大，则这个操作将会比较费时间
- 元素的顺序发生了改变，则元素的索引与元素的关系将发生变化，若某些操作依赖由索引查找元素，则将无法完成
对于以上两点，可以在结构中插入一层索引，对元素的索引进行排序，这样就可以在不破坏原有元素的顺序下完成堆排序，索引堆即由此而来。
索引堆的实现
索引堆机遇原有的堆实现，代码如下：
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
#include <cassert>
#include "iostream"
using namespace std;
class IndexMaxHeap{
private:
int* data;
int count;
int capacity;
int *indexes;
void shiftUp(int k){
while(k > 1 && data[indexes[k/2]] < data[indexes[k]]){
swap(indexes[k/2], indexes[k]);
k /= 2;
}
}
void shiftDown(int k){
int ok = data[indexes[k]];
int startIndex = indexes[k];
while ( 2 * k <= count){
int j = 2 * k;
if( j + 1 <= count && data[indexes[j+1]]>data[indexes[j]]){
j = j+1;
}
if(ok >= data[indexes[j]]){
break;
}
indexes[k] = indexes[j];
k = j;
}
indexes[k] = startIndex;
}
public:
IndexMaxHeap(int capacity){
data = new int[capacity + 1];
indexes = new int[capacity + 1];
count = 0;
this->capacity = capacity;
}
IndexMaxHeap(int arr[], int capacity){
data = new int[capacity + 1];
for(int i=0;i<capacity;i++){
data[i+1] = arr[i];
}
count = capacity;
for(int i = capacity/2; i >= 1; i--){
shiftDown(i);
}
}
~IndexMaxHeap(){
delete[] data;
delete[] indexes;
}
int size(){
return count;
}
bool isEmpty(){
return count == 0;
}
void insert(int i, int item){
assert(count + 1 <= capacity);
assert(i + 1 >=1 && i + 1 <= capacity);
i += 1;
data[i] = item;
indexes[count + 1] = i;
count ++;
shiftUp(count);
}
int extractMax(){
assert(count>0);
int item = data[indexes[1]];
swap(indexes[count], indexes[1]);
count --;
shiftDown(1);
return item;
}
void change(int i, int item){
i += 1;
cout << data[i] << "\n";
data[i] = item;
for(int j = 1; j <= count; j++){
if (indexes[j] == i) {
shiftUp(j);
shiftDown(j);
return;
}
}
}
void printArr(){
for(int i=0;i<=count;i++){
cout<<data[indexes[i]]<<" ";
}
cout << "\n";
}
};
int main(){
int arr[] = {4,1,3,6,7,2,8,22,12,23,21,9,42,90};
IndexMaxHeap maxHeap = IndexMaxHeap(14);
for(int i=1;i<14;i++){
maxHeap.insert(i, arr[i]);
}
maxHeap.printArr();
maxHeap.change(13, 41);
cout << "\n";
maxHeap.printArr();
}
|
原有的插入删除操作，在维护元素数组本身的同时，需要维护对应的索引，此处新增了一个indexes数组来保存索引。同时，shifUp和shifDown操作将是对索引数组进行操作。由于原有元素位置未发生改变，因此，可以方便的进行改变元素的操作。其中新增的change方法即是对指定位置的元素进行替换，替换后需要重新的索引进行维护，保持最大堆的性质。
索引堆的优化
考察change函数，其遍历了整个数组，时间复杂度为O(n)级别，shiftUp和shiftDown为log(n)级别，所以整个时间复杂度为O(n) + log(n)即 O(n)级别，在最坏的情况下可能退化为O(n^2)级别，因此，此处可以对其进行优化.
通过它的查找过程可以看出来，寻找索引为线性查找，那么可以用一个数组来保存指定索引在数组中的位置，参见下表:
索引堆结构优化
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| index |
10 |
9 |
7 |
8 |
5 |
6 |
3 |
1 |
4 |
2 |
| data |
15 |
17 |
19 |
13 |
22 |
16 |
28 |
30 |
41 |
62 |
| rev |
8 |
10 |
7 |
9 |
5 |
6 |
3 |
4 |
2 |
1 |
如上表格所示，index为索引堆新增的索引数组，data为原始数据，rev为新增的保存索引位置的数组。
在此处定义：rev[i] 表示索引i在indexes中的位置，则有这些等式： indexes[i] = j, rev[j] = i; indexes[rev[i]] = i, rev[indexes[i]] = i;
在维护了rev数组后，之前的查找过程将变更为O(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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
#include <cassert>
#include "iostream"
using namespace std;
class IndexMaxHeap{
private:
int* data;
int count;
int capacity;
int *indexes;
int *reverse;
void shiftUp(int k){
while(k > 1 && data[indexes[k/2]] < data[indexes[k]]){
swap(indexes[k/2], indexes[k]);
reverse[indexes[k/2]] = k/2;
reverse[indexes[k]] = k;
k /= 2;
}
}
void shiftDown(int k){
int ok = data[indexes[k]];
int startIndex = indexes[k];
while ( 2 * k <= count){
int j = 2 * k;
if( j + 1 <= count && data[indexes[j+1]]>data[indexes[j]]){
j = j+1;
}
if(ok >= data[indexes[j]]){
break;
}
indexes[k] = indexes[j];
reverse[indexes[k]] = k;
reverse[indexes[j]] = j;
k = j;
}
indexes[k] = startIndex;
}
public:
IndexMaxHeap(int capacity){
data = new int[capacity + 1];
indexes = new int[capacity + 1];
reverse = new int[capacity + 1];
for(int i = 0; i <= capacity; i ++){
reverse[i] = 0;
}
count = 0;
this->capacity = capacity;
}
IndexMaxHeap(int arr[], int capacity){
data = new int[capacity + 1];
for(int i=0;i<capacity;i++){
data[i+1] = arr[i];
}
count = capacity;
for(int i = capacity/2; i >= 1; i--){
shiftDown(i);
}
}
~IndexMaxHeap(){
delete [] data;
delete [] indexes;
delete [] reverse;
}
int size(){
return count;
}
bool isEmpty(){
return count == 0;
}
void insert(int i, int item){
assert(count + 1 <= capacity);
assert(i + 1 >=1 && i + 1 <= capacity);
i += 1;
data[i] = item;
indexes[count + 1] = i;
reverse[i] = count + 1;
count ++;
shiftUp(count);
}
int extractMax(){
assert(count>0);
int item = data[indexes[1]];
swap(indexes[count], indexes[1]);
reverse[indexes[1]] = 1;
reverse[indexes[count]] = 0;
count --;
shiftDown(1);
return item;
}
bool contain(int i){
assert( i + 1 >= 1&& i + 1 <= capacity );
return reverse[i + 1] != 0;
}
void change(int i, int item){
assert(contain(i));
i += 1;
cout << data[i] << "\n";
data[i] = item;
int j = reverse[i];
shiftDown(j);
shiftUp(j);
}
void printArr(){
for(int i=0;i<=count;i++){
cout<<data[indexes[i]]<<" ";
}
cout << "\n";
}
};
int main(){
int arr[] = {4,1,3,6,7,2,8,22,12,23,21,9,42,90};
IndexMaxHeap maxHeap = IndexMaxHeap(14);
for(int i=1;i<14;i++){
maxHeap.insert(i, arr[i]);
}
maxHeap.printArr();
maxHeap.change(13, 41);
cout << "\n";
maxHeap.printArr();
}
|
此处的reverse数组为上述的rev数组，它与indexes的关系比较绕，需要自己理清楚。暂时到这里吧，晕。