堆之索引堆

发表于

索引堆

索引堆的原理与实现

索引堆实际上是对二叉堆的优化。

在原来的数据结构中为每个数据增加一个索引，这样在数据更新的时候，只交换其索引，这样对于复杂的数据结构能提高一些性能。如下图：

当索引 10 对应的值改为 70时，进行堆维护之后，则变为：

可以看到，我们仅仅只是对 index 进行了交换，data 的顺序不变。其它的思路不变。

可以把在上节实现的堆排序的代码拿过来修改一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static void index_max_heap_shift_up(Index_max_heap *index_max_heap,int k) {
    while (k > 1 && index_max_heap->item[index_max_heap->indexs[k/2]] < index_max_heap->item[index_max_heap->indexs[k]]) {
        /// 仅交换 index
        swap(&index_max_heap->indexs[k/2], &index_max_heap->indexs[k]);
        k /= 2;
    }
}

static void index_max_heap_shift_down(Index_max_heap *index_max_heap,int k) {
    while (2*k <= index_max_heap->count) {
        int index = 2*k;
        if (index + 1 <= index_max_heap->count && index_max_heap->item[index_max_heap->indexs[index + 1]] > index_max_heap->item[index_max_heap->indexs[index]]) {
            index += 1;
        }
        if (index_max_heap->item[index_max_heap->indexs[k]] > index_max_heap->item[index_max_heap->indexs[index]]) {
            break;
        }
        
        swap(&index_max_heap->indexs[k], &index_max_heap->indexs[index]);
        k = index;
    }
}

实现更改索引堆的数据

当数据变化的时候，我们要更改索引堆中对应的数据。假设 indexs 中存储的是数据的索引，现在我们要更改 索引为 5 对应的数据：

1
item[5] = newItem;

现在我们要维护索引堆，但是并不知道 5 在 indexs 中的哪个位置，所以只能循环遍历出 i：

1
2
3
4
5
6
7
for (int i = 1; i <= count; i++) {
    if (indexs[i] == 5) {
        shiftUp(i);
        shiftDown(i);
        return;
    }
}

增加反向查找索引 index

可以看到上面的查找还是比较耗时的，这里我们做一下优化，增加一个反向查找 index 的数组 reverses。

我们再将索引 10 对应的值改为 70：

全部的代码如下

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
184
185
186
187
188
189
190
#include "IndexMaxHeap.h"
#include "SortHelper.h"
#include <stdlib.h>
#include <assert.h>


typedef struct Index_max_heap_s Index_max_heap;

typedef struct Index_max_heap_s {
    int count;                                      //-> 当前堆内数据的大小
    int capacity;                                   //-> 当前堆的容量
    void (*insert)(Index_max_heap *,int,int);       //-> 插入函数
    int (*extract_max)(Index_max_heap *);           //-> 输出一个最大值
    int (*extract_max_index)(Index_max_heap *);     //-> 输出一个最大值的索引
    int (*get_item_by_index)(Index_max_heap *,int); //-> 返回一个指定的索引值
    void (*change_item_by_index)(Index_max_heap *,int,int); //-> 更改指定索引的值
    int *item;                                      //-> 数组指针
    int *indexs;                                    //-> 数组指针 索引
    int *reverses;                                  //-> 数组指针 反向查找索引
    void (*print_to_dot)(Index_max_heap *);         //-> 生成 dot 语言 函数
} Index_max_heap;


static void index_max_heap_shift_up(Index_max_heap *index_max_heap,int k) {
    while (k > 1 && index_max_heap->item[index_max_heap->indexs[k/2]] < index_max_heap->item[index_max_heap->indexs[k]]) {
        /// 仅交换 index
        swap(&index_max_heap->indexs[k/2], &index_max_heap->indexs[k]);
        index_max_heap->reverses[index_max_heap->indexs[k/2]] = k/2;
        index_max_heap->reverses[index_max_heap->indexs[k]] = k;
        k /= 2;
    }
}

static void index_max_heap_shift_down(Index_max_heap *index_max_heap,int k) {
    while (2*k <= index_max_heap->count) {
        int index = 2*k;
        if (index + 1 <= index_max_heap->count && index_max_heap->item[index_max_heap->indexs[index + 1]] > index_max_heap->item[index_max_heap->indexs[index]]) {
            index += 1;
        }
        if (index_max_heap->item[index_max_heap->indexs[k]] > index_max_heap->item[index_max_heap->indexs[index]]) {
            break;
        }
        
        swap(&index_max_heap->indexs[k], &index_max_heap->indexs[index]);
        index_max_heap->reverses[index_max_heap->indexs[k]] = k;
        index_max_heap->reverses[index_max_heap->indexs[index]] = index;

        k = index;
    }
}

static void insert(Index_max_heap* index_max_heap,int index,int item) {
    if (index_max_heap->count > index_max_heap->capacity) {
        return;
    }
    index_max_heap->count += 1;
    index_max_heap->item[index_max_heap->count] = item;
    index_max_heap->reverses[index] = index_max_heap->count;
    index_max_heap->indexs[index_max_heap->count] = index;
    index_max_heap_shift_up(index_max_heap, index_max_heap->count);
}

static int extract_max(Index_max_heap* index_max_heap) {
    assert(index_max_heap->count > 0);
    int ret = index_max_heap->item[index_max_heap->indexs[1]];
    
    swap(&index_max_heap->indexs[1], &index_max_heap->indexs[index_max_heap->count]);
    index_max_heap->reverses[index_max_heap->indexs[1]] = 1;
    index_max_heap->reverses[index_max_heap->indexs[index_max_heap->count]] = 0;
    
    index_max_heap->count -= 1;
    
    index_max_heap_shift_down(index_max_heap, 1);
    
    return ret;
}

static int extract_max_index(Index_max_heap* index_max_heap) {
    assert(index_max_heap->count > 0);
    int ret = index_max_heap->indexs[1];
    
    swap(&index_max_heap->indexs[1], &index_max_heap->indexs[index_max_heap->count]);
    index_max_heap->reverses[index_max_heap->indexs[1]] = 1;
    index_max_heap->reverses[index_max_heap->indexs[index_max_heap->count]] = 0;

    index_max_heap->count -= 1;
    
    index_max_heap_shift_down(index_max_heap, 1);
    
    return ret;
}

static int contain(Index_max_heap* index_max_heap,int i) {
    assert(i + 1 >= 1 && i + 1 <= index_max_heap->capacity );
    return index_max_heap->reverses[i + 1] != 0;
}

static int get_item_by_index(Index_max_heap* index_max_heap,int index) {
    assert(contain(index_max_heap,index));
    return index_max_heap->item[index + 1];
}

static void change_item_by_index(Index_max_heap* index_max_heap,int index,int item) {
    assert(contain(index_max_heap,index));
    index += 1;
    index_max_heap->item[index] = item;
    
//    for (int i = 1; i <= index_max_heap->count; i++) {
//        if (index_max_heap->indexs[i] == index) {
//            index_max_heap_shift_up(index_max_heap, i);
//            index_max_heap_shift_down(index_max_heap, i);
//            return;
//        }
//    }
    
    int i = index_max_heap->reverses[index];
    index_max_heap_shift_up(index_max_heap, i);
    index_max_heap_shift_down(index_max_heap, i);
}

static void print_to_dot(Index_max_heap *index_max_heap) {
    printf("\n<---------- dot start ---------->\n\n");
    printf("digraph heap {\nnode[shape=circle];\nnodesep=0.3;\n");
    int count = index_max_heap->count;
    for (int i = 1; i <= count; i++) {
        int leftIndex = 2 * i;
        int rightIndex = 2 * i + 1;
        if (leftIndex <= count) {
            printf("\t%d -> %d;\n",index_max_heap->item[index_max_heap->indexs[i]],index_max_heap->item[index_max_heap->indexs[leftIndex]]);
        }
        if (rightIndex <= count) {
            printf("\t%d -> %d;\n",index_max_heap->item[index_max_heap->indexs[i]],index_max_heap->item[index_max_heap->indexs[rightIndex]]);
        }
    }
    printf("}\n");
    printf("\n\n<---------- dot end ---------->\n");
}


static Index_max_heap create_index_max_heap(int capacity) {
    
    int *item = (int *)malloc(sizeof(int) * (capacity + 1));
    int *indexs = (int *)malloc(sizeof(int) * (capacity + 1));
    int *reverses = (int *)malloc(sizeof(int) * (capacity + 1));
    for (int i = 0; i < capacity; i++) {
        item[i] = 0;
        indexs[i] = 0;
        reverses[i] = 0;
    }
    Index_max_heap index_max_heap = {
        .count = 0,
        .capacity = capacity,
        .insert = insert,
        .extract_max = extract_max,
        .extract_max_index = extract_max_index,
        .get_item_by_index = get_item_by_index,
        .change_item_by_index = change_item_by_index,
        .item = item,
        .indexs = indexs,
        .reverses = reverses,
        .print_to_dot = print_to_dot
    };
    return index_max_heap;
}


#pragma mark - test
void test_index_max_heap() {
    
//    int *a = generateNoRepeatRandomArray(20,0,100);
    
    int arr[] = { 31,2, 1,45,73, 69, 60, 59,91, 49,  43, 32,  29, 18,88, 17, 9,76, 6,  0};
    
    Index_max_heap index_max_heap = create_index_max_heap(50);
    
    for (int i = 0; i < 20; i++) {
        index_max_heap.insert(&index_max_heap,i,arr[i]);
    }
    
    void (*change_item_by_index)(Index_max_heap *index_max_heap,int,int) = index_max_heap.change_item_by_index;
    change_item_by_index(&index_max_heap,8,22);
    
    void (*print_to_dot)(Index_max_heap *index_max_heap) = index_max_heap.print_to_dot;
    print_to_dot(&index_max_heap);
    
    int (*extract_max)(Index_max_heap *index_max_heap) = index_max_heap.extract_max;
    for (int i = 1; i <= 20; i ++) {
        printf("%d, ",extract_max(&index_max_heap));
    }
}