Index Heap and Its Optimization
I. Concept and Introduction
An index heap is an optimization of the heap data structure.
An index heap uses a new array of type int to store index information.
Compared to a heap, the advantages are as follows:
- Optimizes the cost of swapping elements.
- The positions of added data are fixed, making them easy to locate.
II. Application Description
If the elements stored in the heap are large, swapping them would consume a significant amount of time. In such cases, the index heap data structure can be used as an alternative. The heap stores the indexes of the array, and we operate on these indexes.
III. Structural Diagram
We need to modify the previous heap implementation to directly operate on indexes. First, add an index array attribute indexes to the constructor.
protected T[] data; // Data in the max index heap
protected int[] indexes; // Indexes in the max index heap
protected int count;
protected int capacity;
Adjust the constructor accordingly, adding initialization for the index array.
...
public IndexMaxHeap(int capacity){
data = (T[])new Comparable[capacity+1];
indexes = new int[capacity+1];
count = 0;
this.capacity = capacity;
}
...
Adjust the insertion operation, where the element added to the indexes array is the index of the actual data array: indexes[count+1] = i.
...
// Insert a new element into the max index heap, with the new element's index as i and item as the element
// The input i is indexed from 0 for the user
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 shiftUp operation: Compare the data in the parent node of the data array, so it needs to be represented as data[indexes[k/2]] < data[indexes[k]]. Swap the indexes in the indexes array without changing the data array, and the shiftDown operation is similar.
...
// k is the index of the heap
// In the index heap, comparisons are based on the size of the data, but the actual operation is on the indexes
private void shiftUp(int k){
while( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) < 0 ){
swapIndexes(k, k/2);
k /= 2;
}
}
...
Extract an element from the index heap, where the largest element is the data in the root element data[indexes[1]], then swap the index positions for the shiftDown operation.
...
public T extractMax(){
assert count > 0;
T ret = data[indexes[1]];
swapIndexes( 1 , count );
count --;
shiftDown(1);
return ret;
}
...
You can also directly extract the index value of the largest element in the data array.
...
// Extract the index of the top element from the max index heap
public int extractMaxIndex(){
assert count > 0;
int ret = indexes[1] - 1;
swapIndexes( 1 , count );
count --;
shiftDown(1);
return ret;
}
...
Modify the data at the index position.
...
// Modify the element at index i in the max index heap to newItem
public void change( int i , Item newItem ){
i += 1;
data[i] = newItem;
// Find indexes[j] = i, where j represents the position of data[i] in the heap
// Then shiftUp(j) and shiftDown(j)
for( int j = 1 ; j <= count ; j ++ )
if( indexes[j] == i ){
shiftUp(j);
shiftDown(j);
return;
}
}
...
### Four, Java Example Code
**Source Code Download:** [Download](https://www.tutorialpro.org/wp-content/uploads/2020/09/tutorialpro-algorithm-IndexMaxHeap.zip)
## src/tutorialpro/heap/IndexMaxHeap.java File Code:
```java
package tutorialpro.heap;
import java.util.Arrays;
/**
* Index Heap
*/
// Maximum Index Heap, idea: element comparison is based on data, element swapping is based on indexes
public class IndexMaxHeap<T extends Comparable> {
protected T[] data; // Data in the maximum index heap
protected int[] indexes; // Indexes in the maximum index heap
protected int count;
protected int capacity;
// Constructor, creates an empty heap with capacity for `capacity` elements
public IndexMaxHeap(int capacity) {
data = (T[]) new Comparable[capacity + 1];
indexes = new int[capacity + 1];
count = 0;
this.capacity = capacity;
}
// Returns the number of elements in the index heap
public int size() {
return count;
}
// Returns a boolean indicating whether the index heap is empty
public boolean isEmpty() {
return count == 0;
}
// Inserts a new element into the maximum index heap, with the new element's index being `i` and the element being `item`
// The input `i` is 0-indexed for the user
public void insert(int i, T item) {
assert count + 1 <= capacity;
assert i + 1 >= 1 && i + 1 <= capacity;
i += 1;
data[i] = item;
indexes[count + 1] = i;
count++;
shiftUp(count);
}
// Extracts the top element from the maximum index heap, which is the maximum data stored in the index heap
public T extractMax() {
assert count > 0;
T ret = data[indexes[1]];
swapIndexes(1, count);
count--;
shiftDown(1);
return ret;
}
// Extracts the index of the top element from the maximum index heap
public int extractMaxIndex() {
assert count > 0;
int ret = indexes[1] - 1;
swapIndexes(1, count);
count--;
shiftDown(1);
return ret;
}
// Gets the top element in the maximum index heap
public T getMax() {
assert count > 0;
return data[indexes[1]];
}
// Gets the index of the top element in the maximum index heap
public int getMaxIndex() {
assert count > 0;
return indexes[1] - 1;
}
// Gets the element at index `i` in the maximum index heap
public T getItem(int i) {
assert i + 1 >= 1 && i + 1 <= capacity;
return data[i + 1];
}
// Changes the element at index `i` in the maximum index heap to `newItem`
public void change(int i, T newItem) {
i += 1;
data[i] = newItem;
// Find the position of index `i` in the indexes array and shift it up or down if necessary
for (int j = 1; j <= count; j++) {
if (indexes[j] == i) {
shiftUp(j);
shiftDown(j);
return;
}
}
}
// Helper function to swap two indexes
private void swapIndexes(int i, int j) {
int t = indexes[i];
indexes[i] = indexes[j];
indexes[j] = t;
}
// Helper function to shift up the element at index `k` to maintain the heap property
private void shiftUp(int k) {
while (k > 1 && data[indexes[k / 2]].compareTo(data[indexes[k]]) < 0) {
swapIndexes(k, k / 2);
k /= 2;
}
}
// Helper function to shift down the element at index `k` to maintain the heap property
private void shiftDown(int k) {
while (2 * k <= count) {
int j = 2 * k;
if (j + 1 <= count && data[indexes[j + 1]].compareTo(data[indexes[j]]) > 0) {
j++;
}
if (data[indexes[k]].compareTo(data[indexes[j]]) >= 0) {
break;
}
swapIndexes(k, j);
k = j;
}
}
}
data[i] = newItem;
// Find indexes[j] = i, where j represents the position of data[i] in the heap
// Then perform shiftUp(j) and shiftDown(j)
for (int j = 1; j <= count; j++) {
if (indexes[j] == i) {
shiftUp(j);
shiftDown(j);
return;
}
}
// Swap the indexes i and j in the index heap
private void swapIndexes(int i, int j) {
int t = indexes[i];
indexes[i] = indexes[j];
indexes[j] = t;
}
//********************
//* Core auxiliary functions for the maximum index heap
//********************
// k is the index in the heap
// In the index heap, comparisons between data are based on the data's size, but the actual operations are on indexes
private void shiftUp(int k) {
while (k > 1 && data[indexes[k / 2]].compareTo(data[indexes[k]]) < 0) {
swapIndexes(k, k / 2);
k /= 2;
}
}
// In the index heap, comparisons between data are based on the data's size, but the actual operations are on indexes
private void shiftDown(int k) {
while (2 * k <= count) {
int j = 2 * k;
if (j + 1 <= count && data[indexes[j + 1]].compareTo(data[indexes[j]]) > 0)
j++;
if (data[indexes[k]].compareTo(data[indexes[j]]) >= 0)
break;
swapIndexes(k, j);
k = j;
}
}
// Test IndexMaxHeap
public static void main(String[] args) {
int N = 1000000;
IndexMaxHeap<Integer> indexMaxHeap = new IndexMaxHeap<Integer>(N);
for (int i = 0; i < N; i++)
indexMaxHeap.insert(i, (int) (Math.random() * N));
}
The above modification of index positions uses a traversal for finding the index position, which is not efficient. We can further optimize this by maintaining a reverse[i] array that indicates the position of index i in the indexes (heap), reducing the time complexity of the search to O(1).
The following properties hold:
indexes[i] = j
reverse[j] = i
indexes[reverse[i]] = i
reverse[indexes[i]] = i