YouTip

# Indexed Heap and Its Optimization \n\n## Indexed Heap and Its Optimization\n\n### 1. Concept and Introduction\n\nAn indexed heap is an optimization of the heap data structure.\n\nAn indexed heap uses a new `int` type array to store index information.\n\nCompared to a heap, its advantages are as follows:\n\n* Optimizes the cost of swapping elements.\n* The position of added data is fixed, making it easier to locate.\n\n### 2. Application Notes\n\nIf the elements stored in the heap are large, swapping them can be time-consuming. In such cases, an indexed heap data structure can be used as a substitute. The heap stores the indices of the array, and the operations are performed on these indices.\n\n### 3. Structure Illustration\n\n!(#)\n\nWe need to modify the previous heap implementation to operate directly on indices. First, add an index array property `indexes` to the constructor.\n\n```java\nprotected T[] data;// Data in the max indexed heap\n\nprotected int[] indexes;// Indices in the max indexed heap\n\nprotected int count;\n\nprotected int capacity;\n\nThe corresponding constructor is adjusted to initialize the index array.\n\n```java\n...\n\npublic IndexMaxHeap(int capacity){\n data = (T[])new Comparable[capacity+1];\n indexes = new int[capacity+1];\n count = 0;\n this.capacity = capacity;\n}\n\n...\n\nAdjust the insert operation: the element added to the `indexes` array is the actual index of the `data` array, `indexes[count+1] = i`.\n\n```java\n...\n\n// Insert a new element into the max indexed heap, the new element's index is i, the element is item\n// The passed i is 0-indexed for the user\npublic void insert(int i, Item item){\n assert count + 1 = 1 && i + 1 <= capacity;\n i += 1;\n data = item;\n indexes[count+1] = i;\n count ++;\n shiftUp(count);\n}\n\n...\n\nAdjust the `shiftUp` operation: it compares the size of the parent node's data in the `data` array, so it should be expressed as `data[index[k/2]] 1 && data[indexes[k/2]].compareTo(data[indexes]) 0;\n T ret = data[indexes];\n swapIndexes(1 , count );\n count --;\n shiftDown(1);\n return ret;\n}\n\n...\n\nYou can also directly extract the `data` array index of the maximum value.\n\n```java\n...\n\n// Extract the index of the top element from the max indexed heap\npublic int extractMaxIndex(){\n assert count > 0;\n int ret = indexes - 1;\n swapIndexes(1 , count );\n count --;\n shiftDown(1);\n return ret;\n}\n\n...\n\nModify the data at an index position.\n\n```java\n...\n\n// Modify the element at index i in the max indexed heap to newItem\npublic void change(int i , Item newItem ){\n i += 1;\n data = newItem;\n // Find indexes = i, where j is the position of data in the heap\n // Then shiftUp(j), then shiftDown(j)\n for(int j = 1; j <= count ; j ++)\n if( indexes == i ){\n shiftUp(j);\n shiftDown(j);\n return;\n }\n}\n\n...\n\n### 4. Java Example Code\n\n**Source code package download:*## src//heap/IndexMaxHeap.java file code:\n\n```java\npackage .heap;\n\nimport java.util.Arrays;\n\n/**\n * Heap Index\n */\n// Max indexed heap, idea: element comparison is based on data, element swapping is on indices\npublic class IndexMaxHeap{\n\n protected T[] data;// Data in the max indexed heap\n protected int[] indexes;// Indices in the max indexed heap\n protected int count;\n protected int capacity;\n\n // Constructor, constructs an empty heap that can hold capacity elements\n public IndexMaxHeap(int capacity){\n data = (T[])new Comparable[capacity+1];\n indexes = new int[capacity+1];\n count = 0;\n this.capacity = capacity;\n }\n\n // Return the number of elements in the indexed heap\n public int size(){\n return count;\n }\n\n // Return a boolean value indicating whether the indexed heap is empty\n public boolean isEmpty(){\n return count == 0;\n }\n\n // Insert a new element into the max indexed heap, the new element's index is i, the element is item\n // The passed i is 0-indexed for the user\n public void insert(int i, T item){\n assert count + 1 = 1 && i + 1 0;\n T ret = data[indexes];\n swapIndexes(1 , count );\n count --;\n shiftDown(1);\n return ret;\n }\n\n // Extract the index of the top element from the max indexed heap\n public int extractMaxIndex(){\n assert count > 0;\n int ret = indexes - 1;\n swapIndexes(1 , count );\n count --;\n shiftDown(1);\n return ret;\n }\n\n // Get the top element in the max indexed heap\n public T getMax(){\n assert count > 0;\n return data[indexes];\n }\n\n // Get the index of the top element in the max indexed heap\n public int getMaxIndex(){\n assert count > 0;\n return indexes - 1;\n }\n\n // Get the element at index i in the max indexed heap\n public T getItem(int i ){\n assert i + 1 >= 1 && i + 1 <= capacity;\n return data[i+1];\n }\n\n // Modify the element at index i in the max indexed heap to newItem\n public void change(int i , T newItem ){\n i += 1;\n data = newItem;\n // Find indexes = i, where j is the position of data in the heap\n // Then shiftUp(j), then shiftDown(j)\n for(int j = 1; j 1 && data[indexes[k/2]].compareTo(data[indexes]) < 0){\n swapIndexes(k, k/2);\n k /= 2;\n }\n }\n\n // In an indexed heap, data comparison is based on the size of data, but the actual operation is on indices\n private void shiftDown(int k){\n while(2*k <= count ){\n int j = 2*k;\n if( j+1 0)\n j ++;\n if( data[indexes].compareTo(data[indexes]) >= 0)\n break;\n swapIndexes(k, j);\n k = j;\n }\n }\n\n // Test IndexMaxHeap\n public static void main(String[] args){\n int N = 1000000;\n IndexMaxHeap indexMaxHeap = new IndexMaxHeap(N);\n for(int i = 0; i < N ; i ++)\n indexMaxHeap.insert( i , (int)(Math.random()*N));\n }\n}\n\nThe above modification for finding the index position used traversal, which is inefficient. We can optimize it further by maintaining a `reverse` array, which indicates the position of index `i` in the `indexes` (heap), reducing the time complexity of lookup to O(1).\n\n!(#)\n\nIt has the following properties:\n\nindexes = j\nreverse = i\nindexes[reverse] = i\nreverse[indexes] = i