ダイクストラアルゴリズム。最小優先度キューとしての最小ヒープ

CLRS第3版（p。662）のダイクストラのアルゴリズムについて読んでいます。これは私が理解できない本の一部です：

グラフが十分にまばらである場合、特に、E = o(V^2/lg V)バイナリの最小ヒープを持つ最小優先度キューを実装することで、アルゴリズムを改善できます。

なぜグラフを疎にする必要があるのですか？

ここに別の部分があります：

各DECREASE-KEY操作には時間がかかりますがO(log V)、そのような操作は最大でE個あります。

私のグラフが次のようになっているとします。

1から6までの最短経路を計算し、最小ヒープアプローチを使用したいと思います。まず、すべてのノードを最小優先度キューに追加します。最小ヒープを構築すると、最小ノードがソースノードになります（それ自体への距離が0であるため）。私はそれを抽出し、そのすべての隣人の距離を更新します。

次にdecreaseKey、ヒープの新しい最小値を作成するために、距離が最も短いノードを呼び出す必要があります。しかし、どのようにして一定の時間でそのインデックスを知ることができますか？

ノード

private static class Node implements Comparable<Node> {

    final int key;
    int distance = Integer.MAX_VALUE;
    Node prev = null;

    public Node(int key) {
        this.key = key;
    }

    @Override
    public int compareTo(Node o) {
        if (distance < o.distance) {
            return -1;
        } else if (distance > o.distance) {
            return 1;
        } else {
            return 0;
        }
    }

    @Override
    public String toString() {
        return "key=" + key + " distance=" + distance;
    }

    @Override
    public int hashCode() {
        return key;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof Node)) {
            return false;
        }
        Node other = (Node) obj;
        return key == other.key;
    }
}

MinPriorityQueue

public static class MinPriorityQueue {

    private Node[] array;
    private int heapSize;

    public MinPriorityQueue(Node[] array) {
        this.array = array;
        this.heapSize = this.array.length;
    }

    public Node extractMin() {
        Node temp = array[0];
        swap(0, heapSize - 1, array);
        heapSize--;
        sink(0);
        return temp;
    }

    public boolean isEmpty() {
        return heapSize == 0;
    }

    public void buildMinHeap() {
        for (int i = heapSize / 2 - 1; i >= 0; i--) {
            sink(i);
        }
    }

    public void decreaseKey(int index, Node key) {
        if (key.compareTo(array[index]) >= 0) {
            throw new IllegalArgumentException("the new key must be greater than the current key");
        }
        array[index] = key;
        while (index > 0 && array[index].compareTo(array[parentIndex(index)]) < 0) {
            swap(index, parentIndex(index), array);
            index = parentIndex(index);
        }
    }

    private int parentIndex(int index) {
        return (index - 1) / 2;
    }

    private int left(int index) {
        return 2 * index + 1;
    }

    private int right(int index) {
        return 2 * index + 2;
    }

    private void sink(int index) {
        int smallestIndex = index;
        int left = left(index);
        int right = right(index);
        if (left < heapSize && array[left].compareTo(array[smallestIndex]) < 0) {
            smallestIndex = left;
        }
        if (right < heapSize && array[right].compareTo(array[smallestIndex]) < 0) {
            smallestIndex = right;
        }
        if (index != smallestIndex) {
            swap(smallestIndex, index, array);
            sink(smallestIndex);
        }
    }

    public Node min() {
        return array[0];
    }

    private void swap(int i, int j, Node[] array) {
        Node temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}