Index Heap and Its Optimization

1. Concept and Introduction

Index heap is an optimization of the heap data structure.

Index heap uses a new int array to store index information.

Compared to heaps, the advantages are as follows:

  • Optimizes the overhead of swapping elements.
  • The position of the added data is fixed, making it easy to locate.

II. Applicability Instructions

If the elements stored in the heap are large, swapping them consumes a lot of time. In this case, the index heap data structure can be used as a replacement; the heap stores the indices of the array, and what we operate on are the indices.

III. Structure Diagram

We need to modify the previous heap implementation and switch to the mindset of directly operating on indices. First, add the index array property "indexes" to the constructor.

protected T[] data;      // Data in the max index heap
protected int[] indexes;    // Indices in the max index heap
protected int count;
protected int capacity;

Adjust the constructor accordingly by adding initialization of 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 insert operation: the elements added to the indexes array are the indices of the actual data array.indexes[count+1] = i。

...
// Insert a new element into the max index heap. The new element's index is i, and the element is item
// The passed i is 0-indexed from the user's perspective
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: the comparison is based on the size of the parent node data in the data array, so it needs to be expressed asdata[index[k/2]] < data[indexs[k]]swapping the indices in the index array, causing no changes to the data array; the same applies to shift down.

...
// k is the index in the heap
// In the index heap, comparisons are based on the size of data, but the actual operations are on indices
private void shiftUp(int k){

    while( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) < 0 ){
        swapIndexes(k, k/2);
        k /= 2;
    }
}
...

When extracting an element from the index heap, the largest element is the root element.data[index[1]]in the data, and then swap the index positions to proceed.shift downoperation.

...
public T extractMax(){
    assert count > 0;
    T ret = data[indexes[1]];
    swapIndexes( 1 , count );
    count --;
    shiftDown(1);
    return ret;
}
...

You can also directly retrieve the data array index of the maximum value.

...
// 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;
}
...

Modifying data at an index position

...
// Modify the element with 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), then shiftDown(j)
    for( int j = 1 ; j <= count ; j ++ )
        if( indexes[j] == i ){
            shiftUp(j);
            shiftDown(j);
            return;
        }
}
...

IV. Java Example Code

Source package download:Download

Code in src/example/heap/IndexMaxHeap.java:

package example.heap;

import java.util.Arrays;

/**
* Index Heap
 */
// Max index heap, idea: comparisons use data values, but swaps are on indices
public class IndexMaxHeap<T extends Comparable> {

    protected T[] data;      // Data in the max index heap
    protected int[] indexes;    // Indices in the max index heap
    protected int count;
    protected int capacity;

    // Constructor, constructs an empty heap that can hold capacity elements
    public IndexMaxHeap(int capacity){
        data = (T[])new Comparable[capacity+1];
        indexes = new int[capacity+1];
        count = 0;
        this.capacity = capacity;
    }

    // Return the number of elements in the index heap
    public int size(){
        return count;
    }

    // Return a boolean value indicating whether the index heap is empty
    public boolean isEmpty(){
        return count == 0;
    }

    // Insert a new element into the max index heap. The new element's index is i, and the element is item
    // The passed i is 0-indexed from the user's perspective
    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);
    }

    // Extract the top element from the max index heap, i.e., 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;
    }

    // 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;
    }

    // Get the top element of the max index heap
    public T getMax(){
        assert count > 0;
        return data[indexes[1]];
    }

    // Get the index of the top element in the max index heap
    public int getMaxIndex(){
        assert count > 0;
        return indexes[1]-1;
    }

    // Get the element with index i in the max index heap
    public T getItem( int i ){
        assert i + 1 >= 1 && i + 1 <= capacity;
        return data[i+1];
    }

    // Modify the element with index i in the max index heap to newItem
    public void change( int i , T newItem ){
        i += 1;
        data[i] = newItem;
        // Find indexes[j] = i, where j represents the position of data[i] in the heap
        // Then shiftUp(j), then shiftDown(j)
        for( int j = 1 ; j <= count ; j ++ )
            if( indexes[j] == i ){
                shiftUp(j);
                shiftDown(j);
                return;
            }
    }

    // Swap indices 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 helper functions of the max index heap
    //********************
    // k is the index in the heap
    // In the index heap, comparisons are based on the size of data, but the actual operations are on indices
    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 are based on the size of data, but the actual operations are on indices
    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) );
 
    }
}

In the above index position modification, we used traversal to find the index position, which is inefficient. We can optimize it further by maintaining a set ofreverse[i]arrays that represent the position of index i in indexes (the heap), reducing the time complexity of lookup to O(1).

It has the following properties:

indexes[i] = j
reverse[j] = i

indexes[reverse[i]] = i
reverse[indexes[i]] = i
other extensions