在之前文章中记述了堆的实现(插入方式建堆、heapify 方式建堆以及堆排序)《 堆的实现及其应用 》。今天来看看索引堆是个什么东西,对于我们所关心的这个数组而言,数组中的元素位置发生了改变。正是因为这些元素的位置发生了改变,我们才能将其构建为最大堆。 如果元素十分复杂的话,比如像每个位置上存的是一篇上万字的文章。那么交换它们之间的位置将产生大量的时间消耗。并且由于数组元素的位置在构建成堆之后发生了改变,那么我们就很难索引到它,很难去改变它。可以在每一个元素上再加上一个属性来表示原来的位置可以解决,但是这样的话,必须将这个数组遍历一下才能解决。针对以上问题,我们就需要引入索引堆(Index Heap)的概念。
索引堆基本实现
对于索引堆来说,我们将数据和索引这两部分分开存储。真正表征堆的这个数组是由索引这个数组构建成的。

而在构建堆(以最大索引堆为例)的时候,比较的是 data 中的值(即原来数组中对应索引所存的值),构建成堆的却是 index 域。而构建完之后,data 域并没有发生改变,位置改变的是 index 域。

那么现在这个最大堆该怎么解读呢?例如,堆顶元素为 Index=10 代表的就是索引为 10 的 data 域的值,即 62。这时我们来看,构建堆的过程就是简单地索引之间的交换,索引就是简单的 int 型。效率很高。
现在如果我们想对这个数组进行一些改变,比如我们想将索引为 7 的元素值改为 100,那我们需要做的就是将索引 7 所对应 data 域的 28 改为 100。时间复杂度为 O (1)。当然改完之后,我们还需要进行一些操作来维持最大堆的性质。不过调整的过程改变的依旧是 index 域的内容。
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
| package imooc.heap;
public class MaxIndexHeap { protected int[] data; protected int[] indexes;
protected int count;
protected int capacity;
public MaxIndexHeap(int capacity) { data = new int[capacity + 1]; indexes = new int[capacity + 1]; count = 0; this.capacity = capacity; }
public MaxIndexHeap(int[] arr){ data = new int[arr.length + 1]; capacity = arr.length + 1; for (int i = 0; i < arr.length; i++) { data [i + 1] = arr [i]; } count = arr.length; for (int i = count / 2; i >= 1; i--) { shiftDown (i); } }
public int size(){ return count; }
public boolean isEmpty(){ return count == 0; }
public void insert(int i, int item){ assert i + 1 >= 1; i++; if(count + 1 >= capacity){ resize (); } data [i] = item; indexes [count + 1] = i; count++; shiftUp (count); }
public int extractIndexMax(){ if(count == 0) throw new RuntimeException("Heap is null"); int ret = indexes [1] - 1; swapIndexes (1, count); count--; shiftDown (1); return ret; }
public int getItemByIndex(int index){ return data [index]; }
public void changeItem(int index, int newValue){ index++; data [index] = newValue; for (int j = 1; j <= count; j++) { if(indexes [j] == index){ shiftUp (j); shiftDown (j); return; } } }
private void shiftDown(int k) { while (2 * k <= count){ int j = 2 * k; if(j + 1 <= count && data [indexes [j+1]] > data [indexes [j]]){ j++; } if(data [indexes [k]] >= data [indexes [j]]){ break; } swapIndexes (k, j); k = j; } }
private void shiftUp(int k) { while(k > 1 && data [indexes [k / 2]] < data [indexes [k]]){ swapIndexes (k/2, k); k /= 2; } }
private void swapIndexes(int i, int j){ int tmp = indexes [i]; indexes [i] = indexes [j]; indexes [j] = tmp; }
private void resize() { int[] newData = new int[capacity * 2]; System.arraycopy (data, 0, newData, 0, count); data = newData; capacity *= 2;
int[] newIndexes = new int[capacity * 2]; System.arraycopy (indexes, 0, newIndexes, 0, count); indexes = newIndexes; } }
|
索引堆的优化:反向查找
如何优化呢? 反向查找: 再建立一个数组,这个数组的下标和原始数据数组的下标的意思是一样的,就是索引的意思。而数组中存储的元素则是索引在索引堆数组中的位置。

对反向查找表的维护就是,将索引堆中的值取出来(值就是索引值),这个值就是方向查找表的下标,那这个下标应该对应的元素就是索引堆中的位置。

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
| public class MaxIndexHeapOptimize { protected int[] data; protected int[] indexes; protected int[] reverse;
protected int count;
protected int capacity;
public MaxIndexHeapOptimize(int capacity) { data = new int[capacity + 1]; indexes = new int[capacity + 1]; reverse = new int[capacity + 1]; count = 0; for (int i = 0; i <= capacity ; i++) { reverse [i] = 0; } this.capacity = capacity; }
public MaxIndexHeapOptimize(int[] arr){ data = new int[arr.length + 1]; capacity = arr.length + 1; for (int i = 0; i < arr.length; i++) { data [i + 1] = arr [i]; } count = arr.length; for (int i = count / 2; i >= 1; i--) { shiftDown (i); } }
public int size(){ return count; }
public boolean isEmpty(){ return count == 0; }
public void insert(int i, int item){ assert i + 1 >= 1; i++; if(count + 1 >= capacity){ resize (); } data [i] = item; indexes [count + 1] = i; reverse [i] = count + 1; count++; shiftUp (count); }
public int extractIndexMax(){ if(count == 0) throw new RuntimeException("Heap is null"); int ret = indexes [1] - 1; swapIndexes (1, count); reverse [indexes [1]] = 1; reverse [indexes [count]] = 0; count--; shiftDown (1); return ret; }
public int extractMax(){ if(count == 0) throw new RuntimeException("Heap is null"); int ret = data [indexes [1]]; swapIndexes (1, count); reverse [indexes [1]] = 1; reverse [indexes [count]] = 0; count--; shiftDown (1); return ret; }
public int getItemByIndex(int index){ if(contain (index)){ throw new RuntimeException("This index is not in heap!"); } return data [index]; }
public void changeItemOld(int index, int newValue){ index++; data [index] = newValue; for (int j = 1; j <= count; j++) { if(indexes [j] == index){ shiftUp (j); shiftDown (j); return; } } }
public void changeItem(int index, int newValue){ if(contain (index)){ throw new RuntimeException("This index is not in heap!"); } index++; data [index] = newValue; int j = reverse [index]; shiftUp (j); shiftDown (j); }
private boolean contain(int index) { if(!(index + 1 >= 0 && index + 1 <= capacity)){ throw new RuntimeException("This index is illegal"); } return reverse [index + 1] == 0; }
private void shiftDown(int k) { while (2 * k <= count){ int j = 2 * k; if(j + 1 <= count && data [indexes [j+1]] > data [indexes [j]]){ j++; } if(data [indexes [k]] >= data [indexes [j]]){ break; } swapIndexes (k, j); reverse [indexes [k]] = k; reverse [indexes [j]] = j; k = j; } }
private void shiftUp(int k) { while(k > 1 && data [indexes [k / 2]] < data [indexes [k]]){ swapIndexes (k/2, k); reverse [indexes [k/2]] = k/2; reverse [indexes [k]] = k; k /= 2; } }
private void swapIndexes(int i, int j){ int tmp = indexes [i]; indexes [i] = indexes [j]; indexes [j] = tmp; }
private void resize() { int[] newData = new int[capacity * 2]; System.arraycopy (data, 0, newData, 0, count); data = newData; capacity *= 2;
int[] newIndexes = new int[capacity * 2]; System.arraycopy (indexes, 0, newIndexes, 0, count); indexes = newIndexes; } }
|
其他和堆相关的问题
1、使用堆来实现优先队列
动态选择优先级最高的任务执行
2、实现多路归并排序
将整个数组分成 n 个子数组,子数组排完序之后,将每个子数组中最小的元素取出,放到一个最小堆里面,每次从最小堆里取出最小值放到归并结束的数组中,被取走的元素属于哪个子数组,就从哪个子数组中再取出一个补充到最小堆里面,如此循环,直到所有子数组归并到一个数组中。