索引堆的实现与优化
在之前文章中记述了堆的实现（插入方式建堆、heapify方式建堆以及堆排序） 《 堆的实现及其应用 》 。今天来看看索引堆是个什么东西，对于我们所关心的这个数组而言，数组中的元素位置发生了改变。正是因为这些元素的位置发生了改变，我们才能将其构建为最大堆。 如果元素十分复杂的话，比如像每个位置上存的是一篇上万字的文章。那么交换它们之间的位置将产生大量的时间消耗。并且由于数组元素的位置在构建成堆之后发生了改变，那么我们就很难索引到它，很难去改变它。可以在每一个元素上再加上一个属性来表示原来的位置可以解决，但是这样的话，必须将这个数组遍历一下才能解决。针对以上问题，我们就需要引入索引堆（Index Heap）的概念。
索引堆基本实现
对于索引堆来说，我们将数据和索引这两部分分开存储。真正表征堆的这个数组是由索引这个数组构建成的。
而在构建堆（以最大索引堆为例）的时候，比较的是data中的值（即原来数组中对应索引所存的值），构建成堆的却是index域。而构建完之后，data域并没有发生改变，位置改变的是index域。
那么现在这个最大堆该怎么解读呢？例如，堆顶元素为Index=10代表的就是索引为10的data域的值，即62。这时我们来看，构建堆的过程就是简单地索引之间的交换，索引就是简单的int型。效率很高。
现在如果我们想对这个数组进行一些改变，比如我们想将索引为7的元素值改为100，那我们需要做的就是将索引7所对应data域的28改为100。时间复杂度为O(1)。当然改完之后，我们还需要进行一些操作来维持最大堆的性质。不过调整的过程改变的依旧是index域的内容。
1package imooc.heap;
2
3public class MaxIndexHeap {
4 protected int[] data;
5 protected int[] indexes;
6
7 //堆里有多少元素
8 protected int count;
9
10 //堆的容量
11 protected int capacity;
12
13 //因为0号位置不使用，所以capacity + 1
14 public MaxIndexHeap(int capacity) {
15 data = new int[capacity + 1];
16 indexes = new int[capacity + 1];
17 count = 0;
18 this.capacity = capacity;
19 }
20
21 public MaxIndexHeap(int[] arr){
22 data = new int[arr.length + 1];
23 capacity = arr.length + 1;
24 for (int i = 0; i < arr.length; i++) {
25 data[i + 1] = arr[i];
26 }
27 count = arr.length;
28 //从第一个不是叶子节点的位置开始
29 for (int i = count / 2; i >= 1; i--) {
30 shiftDown(i);
31 }
32 }
33
34 //获取现存元素个数
35 public int size(){
36 return count;
37 }
38
39 //判断是否为空
40 public boolean isEmpty(){
41 return count == 0;
42 }
43
44 //插入数据(传入的i对于用户而言，是从0开始索引的)
45 public void insert(int i, int item){
46 assert i + 1 >= 1;
47 i++; //i += 1
48 //判断容量知否超出
49 if(count + 1 >= capacity){
50 //开始扩容
51 resize();
52 }
53 //先存储到末尾
54 data[i] = item;
55 indexes[count + 1] = i;
56 count++;
57 //开始向上调堆
58 shiftUp(count);
59 }
60
61 //取出数据的索引
62 public int extractIndexMax(){
63 if(count == 0) throw new RuntimeException("Heap is null");
64 int ret = indexes[1] - 1;
65 swapIndexes(1, count);
66 count--;
67 //开始向下调堆
68 shiftDown(1);
69 return ret;
70 }
71
72 //根据索引获得元素
73 public int getItemByIndex(int index){
74 return data[index];
75 }
76
77 //根据索引修改某个元素
78 public void changeItem(int index, int newValue){
79 index++;
80 data[index] = newValue;
81 //找到indexes[j] = index; j表示data[index]在堆中的位置
82 //找到shiftUp(j)，再shiftDown(j)
83 for (int j = 1; j <= count; j++) {
84 if(indexes[j] == index){
85 shiftUp(j);
86 shiftDown(j);
87 return;
88 }
89 }
90 }
91
92 //向下调堆
93 private void shiftDown(int k) {
94 while (2 * k <= count){
95 int j = 2 * k;
96 if(j + 1 <= count && data[indexes[j+1]] > data[indexes[j]]){
97 j++;
98 }
99 if(data[indexes[k]] >= data[indexes[j]]){
100 break;
101 }
102 swapIndexes(k, j);
103 k = j;
104 }
105 }
106
107 //向上调堆
108 private void shiftUp(int k) {
109 while(k > 1 && data[indexes[k / 2]] < data[indexes[k]]){
110 swapIndexes(k/2, k);
111 k /= 2;
112 }
113 }
114
115 //交换对应两个位置的值(这是其实是交换索引的位置)
116 private void swapIndexes(int i, int j){
117 int tmp = indexes[i];
118 indexes[i] = indexes[j];
119 indexes[j] = tmp;
120 }
121
122 //扩充容量
123 private void resize() {
124 int[] newData = new int[capacity * 2];
125 System.arraycopy(data, 0, newData, 0, count);
126 data = newData;
127 capacity *= 2;
128
129 int[] newIndexes = new int[capacity * 2];
130 System.arraycopy(indexes, 0, newIndexes, 0, count);
131 indexes = newIndexes;
132 }
133}
索引堆的优化：反向查找
如何优化呢？ 反向查找：再建立一个数组，这个数组的下标和原始数据数组的下标的意思是一样的，就是索引的意思。而数组中存储的元素则是索引在索引堆数组中的位置。
对反向查找表的维护就是，将索引堆中的值取出来（值就是索引值），这个值就是方向查找表的下标，那这个下标应该对应的元素就是索引堆中的位置。
1public class MaxIndexHeapOptimize {
2 protected int[] data;
3 protected int[] indexes;
4 protected int[] reverse;
5
6 //堆里有多少元素
7 protected int count;
8
9 //堆的容量
10 protected int capacity;
11
12 //因为0号位置不使用，所以capacity + 1
13 public MaxIndexHeapOptimize(int capacity) {
14 data = new int[capacity + 1];
15 indexes = new int[capacity + 1];
16 reverse = new int[capacity + 1];
17 count = 0;
18 for (int i = 0; i <= capacity ; i++) {
19 reverse[i] = 0;
20 }
21 this.capacity = capacity;
22 }
23
24 public MaxIndexHeapOptimize(int[] arr){
25 data = new int[arr.length + 1];
26 capacity = arr.length + 1;
27 for (int i = 0; i < arr.length; i++) {
28 data[i + 1] = arr[i];
29 }
30 count = arr.length;
31 //从第一个不是叶子节点的位置开始
32 for (int i = count / 2; i >= 1; i--) {
33 shiftDown(i);
34 }
35 }
36
37 //获取现存元素个数
38 public int size(){
39 return count;
40 }
41
42
43 //判断是否为空
44 public boolean isEmpty(){
45 return count == 0;
46 }
47
48 //插入数据(传入的i对于用户而言，是从0开始索引的)
49 public void insert(int i, int item){
50 assert i + 1 >= 1;
51 i++; //i += 1
52 //判断容量知否超出
53 if(count + 1 >= capacity){
54 //开始扩容
55 resize();
56 }
57 //先存储到末尾
58 data[i] = item;
59 indexes[count + 1] = i;
60 reverse[i] = count + 1;
61 count++;
62 //开始向上调堆
63 shiftUp(count);
64 }
65
66 //取出数据的索引
67 public int extractIndexMax(){
68 if(count == 0) throw new RuntimeException("Heap is null");
69 int ret = indexes[1] - 1;
70 swapIndexes(1, count);
71 reverse[indexes[1]] = 1;
72 reverse[indexes[count]] = 0;
73 count--;
74 //开始向下调堆
75 shiftDown(1);
76 return ret;
77 }
78
79 //取出数据的索引
80 public int extractMax(){
81 if(count == 0) throw new RuntimeException("Heap is null");
82 int ret = data[indexes[1]];
83 swapIndexes(1, count);
84 reverse[indexes[1]] = 1;
85 reverse[indexes[count]] = 0;
86 count--;
87 //开始向下调堆
88 shiftDown(1);
89 return ret;
90 }
91
92 //根据索引获得元素
93 public int getItemByIndex(int index){
94 if(contain(index)){
95 throw new RuntimeException("This index is not in heap!");
96 }
97 return data[index];
98 }
99
100 //根据索引修改某个元素
101 public void changeItemOld(int index, int newValue){
102 index++;
103 data[index] = newValue;
104 //找到indexes[j] = index; j表示data[index]在堆中的位置
105 //找到shiftUp(j)，再shiftDown(j)
106 for (int j = 1; j <= count; j++) {
107 if(indexes[j] == index){
108 shiftUp(j);
109 shiftDown(j);
110 return;
111 }
112 }
113 }
114
115 //根据索引修改某个元素
116 public void changeItem(int index, int newValue){
117 if(contain(index)){
118 throw new RuntimeException("This index is not in heap!");
119 }
120 index++;
121 data[index] = newValue;
122 //找到indexes[j] = index; j表示data[index]在堆中的位置
123 int j = reverse[index]; //O(1)的时间复杂度
124 shiftUp(j);
125 shiftDown(j);
126 }
127
128 private boolean contain(int index) {
129 if(!(index + 1 >= 0 && index + 1 <= capacity)){
130 throw new RuntimeException("This index is illegal");
131 }
132 return reverse[index + 1] == 0;
133 }
134
135 //向下调堆
136 private void shiftDown(int k) {
137 while (2 * k <= count){
138 int j = 2 * k;
139 if(j + 1 <= count && data[indexes[j+1]] > data[indexes[j]]){
140 j++;
141 }
142 if(data[indexes[k]] >= data[indexes[j]]){
143 break;
144 }
145 swapIndexes(k, j);
146 reverse[indexes[k]] = k;
147 reverse[indexes[j]] = j;
148 k = j;
149 }
150 }
151
152 //向上调堆
153 private void shiftUp(int k) {
154 while(k > 1 && data[indexes[k / 2]] < data[indexes[k]]){
155 swapIndexes(k/2, k);
156 reverse[indexes[k/2]] = k/2;
157 reverse[indexes[k]] = k;
158 k /= 2;
159 }
160 }
161
162 //交换对应两个位置的值(这是其实是交换索引的位置)
163 private void swapIndexes(int i, int j){
164 int tmp = indexes[i];
165 indexes[i] = indexes[j];
166 indexes[j] = tmp;
167 }
168
169 //扩充容量
170 private void resize() {
171 int[] newData = new int[capacity * 2];
172 System.arraycopy(data, 0, newData, 0, count);
173 data = newData;
174 capacity *= 2;
175
176 int[] newIndexes = new int[capacity * 2];
177 System.arraycopy(indexes, 0, newIndexes, 0, count);
178 indexes = newIndexes;
179 }
180}
其他和堆相关的问题
1、使用堆来实现优先队列
动态选择优先级最高的任务执行
2、实现多路归并排序
将整个数组分成n个子数组，子数组排完序之后，将每个子数组中最小的元素取出，放到一个最小堆里面，每次从最小堆里取出最小值放到归并结束的数组中，被取走的元素属于哪个子数组，就从哪个子数组中再取出一个补充到最小堆里面，如此循环，直到所有子数组归并到一个数组中。