PriorityQueue/Heap Update

Question

Java có cách dễ dàng để đánh giá lại một đống khi ưu tiên của một đối tượng trong PriorityQueue đã thay đổi không? Tôi không thể tìm thấy bất kỳ dấu hiệu của nó trong Javadoc, nhưng phải có một cách để làm điều đó bằng cách nào đó, phải không? Tôi hiện đang loại bỏ các đối tượng sau đó lại thêm nó, nhưng đó là rõ ràng chậm hơn so với chạy cập nhật trên heap.

Answer 1

Bạn có thể cần phải thực hiện một đống như vậy chính mình. Bạn cần phải có một số xử lý cho vị trí của mục trong heap, và một số phương pháp để đẩy mục lên hoặc xuống khi ưu tiên của nó đã thay đổi.

Một số năm trước, tôi đã viết một đống như một phần của một tác phẩm ở trường. Đẩy một vật lên hoặc xuống là hoạt động O (log N). Tôi phát hành mã sau dưới dạng miền công cộng, vì vậy bạn có thể sử dụng nó theo bất kỳ cách nào bạn muốn. (Bạn có thể muốn cải thiện lớp này để thay vì phương pháp isGreaterOrEqual trừu tượng thứ tự sắp xếp sẽ dựa trên giao diện sánh và tương đương của Java, và cũng sẽ làm cho Generics sử dụng lớp.)

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()); 
     } 
    } 
} 

Answer 2

Tùy thuộc vào việc triển khai cấu trúc dữ liệu, có thể không có cách nào nhanh hơn. Hầu hết các thuật toán PQ/heap không cung cấp chức năng cập nhật. Việc triển khai Java có thể không khác nhau. Lưu ý rằng mặc dù xóa/chèn làm cho mã chậm hơn, nhưng không chắc sẽ dẫn đến mã có độ phức tạp thời gian chạy khác nhau.

Sửa: có một cái nhìn tại thread này: A priority queue which allows efficient priority update?

Answer 3

Các giao diện chuẩn don' t cung cấp khả năng cập nhật. Bạn đã sử dụng một loại tùy chỉnh thực hiện điều này.

Và bạn đã đúng; mặc dù độ phức tạp lớn của các thuật toán sử dụng một đống không thay đổi khi bạn loại bỏ và thay thế đỉnh của heap, thời gian chạy thực tế của chúng có thể gần gấp đôi. Tôi muốn xem hỗ trợ tích hợp tốt hơn cho kiểu sử dụng vùng heap peek() và update().

Answer 4

PriorityQueue có heapify phương pháp mà lại sắp xếp toàn bộ đống, các fixUp phương pháp, trong đó khuyến khích một yếu tố ưu tiên cao hơn lên đống, và fixDown phương pháp, trong đó đẩy một yếu tố ưu tiên thấp hơn xuống đống. Thật không may, tất cả các phương pháp này là riêng tư, vì vậy bạn không thể sử dụng chúng.

Tôi muốn xem xét sử dụng mẫu Observer để một phần tử có thể cho biết Hàng đợi ưu tiên của nó và Hàng đợi có thể thực hiện một số thứ như fixUp hoặc fixDown tùy theo mức độ ưu tiên tăng hoặc giảm tương ứng.

Answer 5

Đúng vậy. PriorityQueue của Java không cung cấp một phương pháp để cập nhật ưu tiên và có vẻ như việc xóa là lấy thời gian tuyến tính vì nó không lưu trữ các đối tượng dưới dạng khóa, như Map. Nó trong thực tế chấp nhận cùng một đối tượng nhiều lần.

Tôi cũng muốn thực hiện hoạt động cập nhật cung cấp PQ. Đây là mã mẫu sử dụng Generics. Bất kỳ lớp nào có thể so sánh có thể được sử dụng với nó.

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

Ở đây trong khi cập nhật, tôi chỉ tăng mức ưu tiên (để triển khai) và đang sử dụng MaxHeap, vì vậy tôi đang thực hiện bubbleUp. Người ta có thể cần phải heapify dựa trên yêu cầu.