最近几年来，地理信息系统无论是在理论上还是应用上都处在一个飞速发展的阶段。 GIS被应用于多个领域的建模和决策支持，如城市管理、区划、环境整治等等，地理信息成为信息时代重要的组成部分之一； “数字地球”概念的提出，更进一步推动了作为其技术支撑的GIS的发展。 与此同时，一些学者致力于相关的理论研究，如空间感知、空间数据误差、空间关系的形式化等等。 这恰好说明了地理信息系统作为应用技术和学科的两个方面，并且这两个方面构成了相互促进的发展过程。
5.14.1. I. the concept and its introduction ¶
Index heap is the optimization of the data structure of heap.
The index heap uses a new array of int types to hold index information.
Compared with heap, the advantages are as follows:
The consumption of exchange elements is optimized.
The position of the added data is fixed, so it is easy to find.
5.14.2. II. Applicable instructions ¶
If the elements stored in the heap are large, it takes a lot of time to swap, which can be replaced by the data structure of the index heap. The index of the array is stored in the heap, and we operate on the index accordingly.
5.14.3. III. Structural diagram ¶
We need to modify the code implementation of the previous heap with the idea of directly manipulating the index. First, the constructor adds the indexed array attribute indexes.
protected T[] data; // 最大索引堆中的数据 protected int[] indexes; // 最大索引堆中的索引 protected int count; protected int capacity; The corresponding constructor is adjusted to add an array of initialized indexes.
... public IndexMaxHeap(int capacity){ data = (T[])new Comparable[capacity+1]; indexes = new int[capacity+1]; count = 0; this.capacity = capacity; } ... Adjust the insert operation. The element added to the indexes array is the index indexes of the real data array. [count+1] = I.
... // 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item // 传入的i对用户而言,是从0索引的 public void insert(int i, Item item){ assert count + 1 <= capacity; assert i + 1 >= 1 && i + 1 <= capacity; i += 1; data[i] = item; indexes[count+1] = i; count ++; shiftUp(count); } ... Adjust the shift up operation: compare the size of the parent node data in the data array, so it needs to be expressed as data [index[k/2] ] < data [indexs[k] Exchange the index of the index array without any change to the data array, the same goes for shift down.
... //k是堆的索引 // 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引 private void shiftUp(int k){ while( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) < 0 ){ swapIndexes(k, k/2); k /= 2; } } ... Fetch the element from the index heap and data the root element for the large element [index[1] And then exchange index locations for shift down operations.
... public T extractMax(){ assert count > 0; T ret = data[indexes[1]]; swapIndexes( 1 , count ); count --; shiftDown(1); return ret; } ... You can also directly fetch the data array index value of the maximum value
... // 从最大索引堆中取出堆顶元素的索引 public int extractMaxIndex(){ assert count > 0; int ret = indexes[1] - 1; swapIndexes( 1 , count ); count --; shiftDown(1); return ret; } ... Modify index location data
... // 将最大索引堆中索引为i的元素修改为newItem public void change( int i , Item newItem ){ i += 1; data[i] = newItem; // 找到indexes[j] = i, j表示data[i]在堆中的位置 // 之后shiftUp(j), 再shiftDown(j) for( int j = 1 ; j <= count ; j ++ ) if( indexes[j] == i ){ shiftUp(j); shiftDown(j); return; } } ... 5.14.4. 4. Java instance code ¶
源码包下载： Download The above modification index location in the search index location we use traversal, the efficiency is not high. We can also optimize it again to maintain a set of reverse [i] Array, which represents the position of index I in the indexes (heap), reducing the time complexity of the search to O (1). It has the following properties: Src/runoob/heap/IndexMaxHeap.java file code: ¶
package runoob.heap; import java.util.Arrays; /*\* \* 索引堆 */ // 最大索引堆，思路：元素比较的是data数据,元素交换的是索引 public class IndexMaxHeap
indexes[i] = j reverse[j] = i indexes[reverse[i]] = i reverse[indexes[i]] = i