41

PriorityQueue 内のオブジェクトの優先度が変更された場合、Java にはヒープを再評価する簡単な方法がありますか? 私はその兆候を見つけることができませんが、Javadoc何らかの方法でそれを行う必要がありますよね? 現在、オブジェクトを削除してから再度追加していますが、ヒープで更新を実行するよりも明らかに遅いです。

4

7 に答える 7

19

このようなヒープを自分で実装する必要がある場合があります。ヒープ内のアイテムの位置へのハンドルと、優先度が変更されたときにアイテムを上下にプッシュするいくつかのメソッドが必要です。

数年前、私は学校の課題の一部としてそのようなヒープを書きました。アイテムを上下に押すのは O(log N) 操作です。次のコードをパブリック ドメインとして公開しますので、自由に使用してください。(抽象 isGreaterOrEqual メソッドの代わりに、並べ替え順序が Java の Comparator および Comparable インターフェイスに依存し、クラスがジェネリックを使用するように、このクラスを改善することもできます。)

import java.util.*;

public abstract class Heap {

    private List heap;

    public Heap() {
        heap = new ArrayList();
    }

    public void push(Object obj) {
        heap.add(obj);
        pushUp(heap.size()-1);
    }

    public Object pop() {
        if (heap.size() > 0) {
            swap(0, heap.size()-1);
            Object result = heap.remove(heap.size()-1);
            pushDown(0);
            return result;
        } else {
            return null;
        }
    }

    public Object getFirst() {
        return heap.get(0);
    }

    public Object get(int index) {
        return heap.get(index);
    }

    public int size() {
        return heap.size();
    }

    protected abstract boolean isGreaterOrEqual(int first, int last);

    protected int parent(int i) {
        return (i - 1) / 2;
    }

    protected int left(int i) {
        return 2 * i + 1;
    }

    protected int right(int i) {
        return 2 * i + 2;
    }

    protected void swap(int i, int j) {
        Object tmp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, tmp);
    }

    public void pushDown(int i) {
        int left = left(i);
        int right = right(i);
        int largest = i;

        if (left < heap.size() && !isGreaterOrEqual(largest, left)) {
            largest = left;
        }
        if (right < heap.size() && !isGreaterOrEqual(largest, right)) {
            largest = right;
        }

        if (largest != i) {
            swap(largest, i);
            pushDown(largest);
        }
    }

    public void pushUp(int i) {
        while (i > 0 && !isGreaterOrEqual(parent(i), i)) {
            swap(parent(i), i);
            i = parent(i);
        }
    }

    public String toString() {
        StringBuffer s = new StringBuffer("Heap:\n");
        int rowStart = 0;
        int rowSize = 1;
        for (int i = 0; i < heap.size(); i++) {
            if (i == rowStart+rowSize) {
                s.append('\n');
                rowStart = i;
                rowSize *= 2;
            }
            s.append(get(i));
            s.append(" ");
        }
        return s.toString();
    }

    public static void main(String[] args){
        Heap h = new Heap() {
            protected boolean isGreaterOrEqual(int first, int last) {
                return ((Integer)get(first)).intValue() >= ((Integer)get(last)).intValue();
            }
        };

        for (int i = 0; i < 100; i++) {
            h.push(new Integer((int)(100 * Math.random())));
        }

        System.out.println(h+"\n");

        while (h.size() > 0) {
            System.out.println(h.pop());
        }
    }
}
于 2009-04-03T17:18:25.960 に答える
4

標準インターフェースは更新機能を提供しません。これを実装するカスタムタイプを使用しています。

そして、あなたは正しいです。ヒープを使用するアルゴリズムの非常に複雑な部分は、ヒープのトップを削除して置き換えても変わりませんが、実際の実行時間はほぼ 2 倍になります。peek()ヒープの使用方法とupdate()スタイルの組み込みサポートが改善されることを望みます。

于 2009-04-03T17:23:57.697 に答える
4

それは正しい。PriorityQueueof Java は優先度を更新する方法を提供しておらず、オブジェクトをキーとして保存しないため、削除には直線的な時間がかかるようですMap。実際、同じオブジェクトを複数回受け入れます。

また、PQ オファリングの更新操作を行いたいと考えていました。ジェネリックを使用したサンプル コードを次に示します。Comparable である任意のクラスを使用できます。

class PriorityQueue<E extends Comparable<E>> {
    List<E> heap = new ArrayList<E>();
    Map<E, Integer> map = new HashMap<E, Integer>();

    void insert(E e) {
        heap.add(e);
        map.put(e, heap.size() - 1);
        bubbleUp(heap.size() - 1);
    }

    E deleteMax() {
        if(heap.size() == 0)
            return null;
        E result = heap.remove(0);
        map.remove(result);
        heapify(0);
        return result;
    }

    E getMin() {
        if(heap.size() == 0)
            return null;
        return heap.get(0);
    }

    void update(E oldObject, E newObject) {
        int index = map.get(oldObject);
        heap.set(index, newObject);
        bubbleUp(index);
    }

    private void bubbleUp(int cur) {
        while(cur > 0 && heap.get(parent(cur)).compareTo(heap.get(cur)) < 0) {
            swap(cur, parent(cur));
            cur = parent(cur);
        }
    }

    private void swap(int i, int j) {
        map.put(heap.get(i), map.get(heap.get(j)));
        map.put(heap.get(j), map.get(heap.get(i)));
        E temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    private void heapify(int index) {
        if(left(index) >= heap.size())
            return;
        int bigIndex = index;
        if(heap.get(bigIndex).compareTo(heap.get(left(index))) < 0)
            bigIndex = left(index);
        if(right(index) < heap.size() && heap.get(bigIndex).compareTo(heap.get(right(index))) < 0)
            bigIndex = right(index);
        if(bigIndex != index) {
            swap(bigIndex, index);
            heapify(bigIndex);
        }
    }

    private int parent(int i) {
        return (i - 1) / 2;
    }

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

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

ここで更新中、私は（私の実装のために）優先度を上げているだけで、MaxHeap を使用しているので、bubbleUp を行っています。要件に基づいてヒープ化する必要がある場合があります。

于 2015-10-18T05:58:12.527 に答える
2

データ構造の実装によっては、より高速な方法がない場合があります。ほとんどの PQ/ヒープ アルゴリズムは更新機能を提供しません。Java の実装に違いはないかもしれません。削除/挿入によってコードが遅くなりますが、ランタイムの複雑さが異なるコードになる可能性は低いことに注意してください。

編集：このスレッドを見てください：効率的な優先度の更新を可能にする優先度キュー？

于 2009-04-03T17:07:43.100 に答える