Index-Heap und seine Optimierung

1. Konzept und Einführung

Der Index-Heap ist eine Optimierung der Heap-Datenstruktur.

Der Index-Heap verwendet ein neues int-Array, um Indexinformationen zu speichern.

Im Vergleich zu Heaps sind die Vorteile wie folgt:

  • Optimiert den Overhead beim Austauschen von Elementen.
  • Die Position der hinzugefügten Daten ist fest, was das Auffinden erleichtert.

II. Hinweise zur Anwendbarkeit

Wenn die im Heap gespeicherten Elemente groß sind, kostet das Vertauschen viel Zeit. In diesem Fall kann die Index-Heap-Datenstruktur als Ersatz verwendet werden; der Heap speichert die Indizes des Arrays, und wir operieren auf den Indizes.

III. Strukturdiagramm

Wir müssen die vorherige Heap-Implementierung ändern und zur Denkweise übergehen, direkt auf Indizes zu operieren. Zuerst fügen wir dem Konstruktor die Index-Array-Eigenschaft "indexes" hinzu.

protected T[] data;      // Daten im Max-Index-Heap
protected int[] indexes⟦⟧// Indizes im Max-Index-Heap;    // Indices in the max index heap
protected int count;
protected int capacity;

Passen Sie den Konstruktor entsprechend an, indem Sie die Initialisierung des Index-Arrays hinzufügen.

...
public IndexMaxHeap(int capacity){
    data = (T[])new Comparable[capacity+1];
    indexes = new int[capacity+1];
    count = 0;
    this.capacity = capacity;
}
...

Passen Sie die Einfügeoperation an: Die Elemente, die dem indexes-Array hinzugefügt werden, sind die Indizes des tatsächlichen Daten-Arrays.indexes[count+1] = i。

...
// Fügen Sie ein neues Element in den Max-Index-Heap ein. Der Index des neuen Elements ist i, und das Element ist item
// Das übergebene i ist aus Sicht des Benutzers 0-indiziert
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);
}
...

Passen Sie die Shift-up-Operation an: Der Vergleich basiert auf der Größe der Daten des übergeordneten Knotens im Daten-Array, daher muss er alsdata[index[k/2]] < data[indexs[k]]ausgedrückt werden, wobei die Indizes im Index-Array vertauscht werden, was keine Änderungen am Daten-Array verursacht; dasselbe gilt für Shift-down.

...
// k ist der Index im Heap
// Im Index-Heap basieren Vergleiche auf der Größe der Daten, aber die eigentlichen Operationen beziehen sich auf Indizes
private void shiftUp(int k){

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

Beim Extrahieren eines Elements aus dem Index-Heap ist das größte Element das Wurzelelement.data[index[1]]in den Daten, und dann werden die Indexpositionen getauscht, um fortzufahren.shift downOperation.

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

Sie können auch direkt den Index des Datenarrays des Maximalwerts abrufen.

...
// Den Index des obersten Elements aus dem Max-Index-Heap extrahieren
public int extractMaxIndex(){
    assert count > 0;
    int ret = indexes[1] - 1;
    swapIndexes( 1 , count );
    count --;
    shiftDown(1);
    return ret;
}
...

Daten an einer Indexposition ändern

...
// Das Element mit Index i im Max-Index-Heap zu newItem ändern
public void change( int i , Item newItem ){
    i += 1;
    data[i] = newItem;
    // Finde indexes[j] = i, wobei j die Position von data[i] im Heap darstellt
    // Dann shiftUp(j), dann shiftDown(j)
    for( int j = 1 ; j <= count ; j ++ )
        if( indexes[j] == i ){
            shiftUp(j);
            shiftDown(j);
            return;
        }
}
...

IV. Java-Beispielcode

Quellpaket herunterladen:Herunterladen

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

package example.heap;

import java.util.Arrays;

/**
* Index-Heap
 */

// Max-Index-Heap, Idee: Vergleiche verwenden Datenwerte, aber Vertauschungen erfolgen anhand von Indizes
public class IndexMaxHeap<T extends Comparable> {

    protected T[] data;      // Daten im Max-Index-Heap
    protected int[] indexes⟦⟧// Indizes im Max-Index-Heap;    // Indices in the max index heap
    protected int count;
    protected int capacity;

    // Konstruktor, erzeugt einen leeren Heap, der capacity Elemente aufnehmen kann
    public IndexMaxHeap(int capacity){
        data = (T[])new Comparable[capacity+1];
        indexes = new int[capacity+1];
        count = 0;
        this.capacity = capacity;
    }

    // Gibt die Anzahl der Elemente im Index-Heap zurück
    public int size(){
        return count;
    }

    // Gibt einen booleschen Wert zurück, der angibt, ob der Index-Heap leer ist
    public boolean isEmpty(){
        return count == 0;
    }

    // Fügen Sie ein neues Element in den Max-Index-Heap ein. Der Index des neuen Elements ist i, und das Element ist item
    // Das übergebene i ist aus Sicht des Benutzers 0-indiziert
    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);
    }

    // Extrahiert das oberste Element aus dem Max-Index-Heap, d. h. das Maximum der im Index-Heap gespeicherten Daten
    public T extractMax(){
        assert count > 0;

        T ret = data[indexes[1]];
        swapIndexes( 1 , count );
        count --;
        shiftDown(1);

        return ret;
    }

    // Den Index des obersten Elements aus dem Max-Index-Heap extrahieren
    public int extractMaxIndex(){
        assert count > 0;

        int ret = indexes[1] - 1;
        swapIndexes( 1 , count );
        count --;
        shiftDown(1);

        return ret;
    }

    // Gibt das oberste Element des Max-Index-Heaps zurück
    public T getMax(){
        assert count > 0;
        return data[indexes[1]];
    }

    // Gibt den Index des obersten Elements im Max-Index-Heap zurück
    public int getMaxIndex(){
        assert count > 0;
        return indexes[1]-1;
    }

    // Gibt das Element mit Index i im Max-Index-Heap zurück
    public T getItem( int i ){
        assert i + 1 >= 1 && i + 1 <= capacity;
        return data[i+1];
    }

    // Das Element mit Index i im Max-Index-Heap zu newItem ändern
    public void change( int i , T newItem ){
        i += 1;
        data[i] = newItem;
        // Finde indexes[j] = i, wobei j die Position von data[i] im Heap darstellt
        // Dann shiftUp(j), dann shiftDown(j)
        for( int j = 1 ; j <= count ; j ++ )
            if( indexes[j] == i ){
                shiftUp(j);
                shiftDown(j);
                return;
            }
    }

    // Vertauscht die Indizes i und j im Index-Heap
    private void swapIndexes(int i, int j){
        int t = indexes[i];
        indexes[i] = indexes[j];
        indexes[j] = t;
    }

    //********************
    //* Kern-Hilfsfunktionen des Max-Index-Heaps
    //********************
    // k ist der Index im Heap
    // Im Index-Heap basieren Vergleiche auf der Größe der Daten, aber die eigentlichen Operationen beziehen sich auf Indizes
    private void shiftUp(int k){

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

    // Im Index-Heap basieren Vergleiche auf der Größe der Daten, aber die eigentlichen Operationen beziehen sich auf Indizes
    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;
        }
    }

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

Bei der obigen Änderung der Indexposition haben wir eine Traversierung verwendet, um die Indexposition zu finden, was ineffizient ist. Wir können es weiter optimieren, indem wir eine Menge vonreverse[i]Arrays verwalten, die die Position des Index i in indexes (dem Heap) repräsentieren, wodurch die Zeitkomplexität des Nachschlagens auf O(1) reduziert wird.

Es hat die folgenden Eigenschaften:

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

indexes[reverse[i]] = i
reverse[indexes[i]] = i
Weitere Erweiterungen