प्राथमिकता क्यूई/हीप अपडेट

Question

क्या प्राथमिकता क्यूई में किसी ऑब्जेक्ट की प्राथमिकता बदल जाने के बाद जावा के पास एक ढेर का पुनर्मूल्यांकन करने का एक आसान तरीका है? मुझे Javadoc में इसका कोई संकेत नहीं मिल रहा है, लेकिन इसे किसी भी तरह से करने का कोई तरीका होना चाहिए, है ना? मैं वर्तमान में ऑब्जेक्ट को फिर से जोड़ रहा हूं, लेकिन यह ढेर पर अपडेट चलाने से स्पष्ट रूप से धीमा है।

Answer 1

आप इस तरह के एक ढेर अपने आप को लागू करने के लिए आवश्यकता हो सकती है: इस सूत्र पर एक नजर है। आपको ढेर में आइटम की स्थिति में कुछ संभाल करने की आवश्यकता है, और इसकी प्राथमिकता बदल जाने पर आइटम को ऊपर या नीचे धक्का देने के कुछ तरीके हैं।

कुछ साल पहले मैंने स्कूल के काम के हिस्से के रूप में इस तरह के ढेर को लिखा था। किसी आइटम को ऊपर या नीचे धक्का देना ओ (लॉग एन) ऑपरेशन है। मैं निम्नलिखित कोड को सार्वजनिक डोमेन के रूप में रिलीज़ करता हूं, ताकि आप इसे किसी भी तरह से उपयोग कर सकें। (आप वर्ग उपयोग जेनरिक होगा इस वर्ग में सुधार करने के लिए इतना है कि सार isGreaterOrEqual विधि के बजाय सॉर्ट क्रम जावा के तुलनाकारी और तुलनीय इंटरफेस पर भरोसा होगा चाहते हो सकता है, और यह भी।)

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

डेटा संरचना के कार्यान्वयन के आधार पर, एक तेज़ तरीका नहीं हो सकता है। अधिकांश पीक्यू/हीप एल्गोरिदम अद्यतन फ़ंक्शन प्रदान नहीं करते हैं। जावा कार्यान्वयन कोई अलग नहीं हो सकता है। ध्यान दें कि यद्यपि एक निकालने/डालने से कोड धीमा हो जाता है, लेकिन अलग-अलग रनटाइम जटिलता वाले कोड में परिणाम होने की संभावना नहीं है।

संपादित: A priority queue which allows efficient priority update?

Answer 3

मानक इंटरफेस डॉन ' एक अद्यतन क्षमता प्रदान नहीं करते हैं। आपने एक कस्टम प्रकार का उपयोग किया है जो इसे लागू करता है।

और आप सही हैं; यद्यपि एक हीप का उपयोग करने वाले एल्गोरिदम की बड़ी-जटिलता तब नहीं बदलती जब आप ढेर के शीर्ष को हटाते और बदलते हैं, उनका वास्तविक रन टाइम लगभग दोगुना हो सकता है। मैं peek() और update() ढेर उपयोग की शैली के लिए बेहतर अंतर्निहित समर्थन देखना चाहता हूं।

Answer 4

PriorityQueue, heapify विधि है जो फिर से क्रमबद्ध करता पूरे ढेर है fixUp विधि है, जो उच्च प्राथमिकता ऊपर ढेर का एक तत्व को बढ़ावा देता है, और fixDown विधि है, जिसमें ढेर नीचे कम प्राथमिकता का एक तत्व धक्का। दुर्भाग्यवश, ये सभी विधियां निजी हैं, इसलिए आप उनका उपयोग नहीं कर सकते हैं।

मैं ऑब्जर्वर पैटर्न के उपयोग पर विचार तो यह है कि एक निहित तत्व कतार बता सकता है कि उसकी प्राथमिकता बदल गया है, और कतार फिर अगर प्राथमिकता वृद्धि हुई है या क्रमश: कमी आई के आधार पर fixUp या fixDown की तरह कुछ कर सकते हैं चाहते हैं।

Answer 5

यह सही है। जावा के PriorityQueue प्राथमिकता को अद्यतन करने के लिए एक विधि प्रदान नहीं करते हैं और ऐसा लगता है कि हटाना रैखिक समय ले रहा है क्योंकि यह ऑब्जेक्ट्स को कुंजी के रूप में संग्रहीत नहीं करता है, क्योंकि Map करता है। यह वास्तव में एक ही वस्तु को कई बार स्वीकार करता है।

मैं भी पीक्यू पेशकश अद्यतन ऑपरेशन बनाना चाहता था। जेनेरिक का उपयोग कर नमूना कोड यहां दिया गया है। तुलनात्मक किसी भी वर्ग का उपयोग इसके साथ किया जा सकता है।

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 कर रहा हूं। आवश्यकता के आधार पर किसी को ढेर करने की आवश्यकता हो सकती है।