जावास्क्रिप्ट में प्राथमिकता कतार लागू करने के लिए कुशल तरीका?

Question

प्राथमिकता पंक्तियों में प्रत्येक प्रविष्टि के लिए प्राथमिकता मान और डेटा होता है।

इस प्रकार, कतार में एक नया तत्व जोड़ते समय, यह सतह पर बुलबुले हो जाता है यदि संग्रह में पहले से मौजूद तत्वों की तुलना में यह उच्च प्राथमिकता मान है।

जब कोई पॉप कॉल करता है, तो हमें उच्च प्राथमिकता वाले तत्व के लिए डेटा मिलता है।

जावास्क्रिप्ट में ऐसी प्राथमिकता कतार का कुशल कार्यान्वयन क्या है?

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

ऐसा करने का एक अच्छा तरीका क्या है?

Answer 1

नीचे है जो मैं एक PriorityQueue जो एक सरणी आधारित द्विआधारी ढेर (जहां जड़ सूचकांक 0 में है का उपयोग करता है की एक सही मायने में कुशल संस्करण, और सूचकांक i में एक नोड के बच्चों को विश्वास सूचकांक पर हैं 2i + 1 और 2i + 2 क्रमशः)।

इस कार्यान्वयन push, peek, pop, और size, साथ ही सुविधा तरीकों isEmpty और replace की तरह शास्त्रीय प्राथमिकता कतार तरीकों (उत्तरार्द्ध एक pop के लिए एक अधिक कुशल विकल्प जा रहा है एक push द्वारा तुरंत बाद) भी शामिल है। मान [value, priority] जोड़े के रूप में संग्रहीत नहीं हैं, लेकिन बस value एस के रूप में; यह उन प्रकारों के स्वचालित प्राथमिकता के लिए अनुमति देता है जिन्हें > ऑपरेटर का उपयोग करके तुलनात्मक रूप से तुलना की जा सकती है। PriorityQueue कन्स्ट्रक्टर को पारित एक कस्टम तुलनित्र फ़ंक्शन का उपयोग उदाहरण के उदाहरण में दिखाए गए अनुसार, जोड़ी के अर्थशास्त्र के व्यवहार को अनुकरण करने के लिए किया जा सकता है।

ढेर आधारित कार्यान्वयन:

const top = 0; 
const parent = i => ((i + 1) >>> 1) - 1; 
const left = i => (i << 1) + 1; 
const right = i => (i + 1) << 1; 

class PriorityQueue { 
    constructor(comparator = (a, b) => a > b) { 
    this._heap = []; 
    this._comparator = comparator; 
    } 
    size() { 
    return this._heap.length; 
    } 
    isEmpty() { 
    return this.size() == 0; 
    } 
    peek() { 
    return this._heap[top]; 
    } 
    push(...values) { 
    values.forEach(value => { 
     this._heap.push(value); 
     this._siftUp(); 
    }); 
    return this.size(); 
    } 
    pop() { 
    const poppedValue = this.peek(); 
    const bottom = this.size() - 1; 
    if (bottom > top) { 
     this._swap(top, bottom); 
    } 
    this._heap.pop(); 
    this._siftDown(); 
    return poppedValue; 
    } 
    replace(value) { 
    const replacedValue = this.peek(); 
    this._heap[top] = value; 
    this._siftDown(); 
    return replacedValue; 
    } 
    _greater(i, j) { 
    return this._comparator(this._heap[i], this._heap[j]); 
    } 
    _swap(i, j) { 
    [this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]]; 
    } 
    _siftUp() { 
    let node = this.size() - 1; 
    while (node > top && this._greater(node, parent(node))) { 
     this._swap(node, parent(node)); 
     node = parent(node); 
    } 
    } 
    _siftDown() { 
    let node = top; 
    while (
     (left(node) < this.size() && this._greater(left(node), node)) || 
     (right(node) < this.size() && this._greater(right(node), node)) 
    ) { 
     let maxChild = (right(node) < this.size() && this._greater(right(node), left(node))) ? right(node) : left(node); 
     this._swap(node, maxChild); 
     node = maxChild; 
    } 
    } 
} 

---

उदाहरण:

{const top=0,parent=c=>(c+1>>>1)-1,left=c=>(c<<1)+1,right=c=>c+1<<1;class PriorityQueue{constructor(c=(d,e)=>d>e){this._heap=[],this._comparator=c}size(){return this._heap.length}isEmpty(){return 0==this.size()}peek(){return this._heap[top]}push(...c){return c.forEach(d=>{this._heap.push(d),this._siftUp()}),this.size()}pop(){const c=this.peek(),d=this.size()-1;return d>top&&this._swap(top,d),this._heap.pop(),this._siftDown(),c}replace(c){const d=this.peek();return this._heap[top]=c,this._siftDown(),d}_greater(c,d){return this._comparator(this._heap[c],this._heap[d])}_swap(c,d){[this._heap[c],this._heap[d]]=[this._heap[d],this._heap[c]]}_siftUp(){for(let c=this.size()-1;c>top&&this._greater(c,parent(c));)this._swap(c,parent(c)),c=parent(c)}_siftDown(){for(let d,c=top;left(c)<this.size()&&this._greater(left(c),c)||right(c)<this.size()&&this._greater(right(c),c);)d=right(c)<this.size()&&this._greater(right(c),left(c))?right(c):left(c),this._swap(c,d),c=d}}window.PriorityQueue=PriorityQueue} 
 

 
// Default comparison semantics 
 
const queue = new PriorityQueue(); 
 
queue.push(10, 20, 30, 40, 50); 
 
console.log('Top:', queue.peek()); //=> 50 
 
console.log('Size:', queue.size()); //=> 5 
 
console.log('Contents:'); 
 
while (!queue.isEmpty()) { 
 
    console.log(queue.pop()); //=> 40, 30, 20, 10 
 
} 
 

 
// Pairwise comparison semantics 
 
const pairwiseQueue = new PriorityQueue((a, b) => a[1] > b[1]); 
 
pairwiseQueue.push(['low', 0], ['medium', 5], ['high', 10]); 
 
console.log('\nContents:'); 
 
while (!pairwiseQueue.isEmpty()) { 
 
    console.log(pairwiseQueue.pop()[0]); //=> 'high', 'medium', 'low' 
 
}

.as-console-wrapper{min-height:100%}

Answer 2

आपको मानक पुस्तकालयों का उपयोग करना चाहिए जैसे उदा। बंद लाइब्रेरी (goog.structs.PriorityQueue):

https://github.com/google/closure-library/blob/master/closure/goog/structs/heap.js