Wydajny sposób na wdrożenie kolejki priorytetowej w JavaScript?

Question

Kolejki priorytetów mają wartość priorytetu i dane dla każdego wpisu.

W ten sposób, dodając nowy element do kolejki, bąbelkuje do powierzchni, jeśli ma wartość wyższego priorytetu niż elementy już w kolekcji.

Po wywołaniu popu otrzymujemy dane dla elementu o najwyższym priorytecie.

Co to jest wydajne wdrożenie takiej kolejki priorytetowej w JavaScript?

Czy ma sens mieć nowy obiekt o nazwie PriorityQueue, tworzyć dwie metody (push i pop), które pobierają dwie parametry (dane, priorytet)? To ma dla mnie sens jako koder, ale nie jestem pewien, jakiej struktury danych użyć w podbrzuszu, która pozwoli na manipulację uporządkowaniem elementów. Czy możemy po prostu przechowywać wszystko w tablicy i przejść przez tablicę za każdym razem, aby pobrać element z maksymalnym priorytetem?

Co to jest dobry sposób na zrobienie tego?

Answer 1

Poniżej jest to, co uważam za naprawdę skuteczny wersja PriorityQueue który wykorzystuje binarną sterty tablicy oparte (gdzie korzeń jest w indeksie 0, a dzieci z węzła o indeksie i są w indeksach 2i + 1 i 2i + 2 , odpowiednio).

Ta realizacja zawiera klasyczne metody kolejek priorytetów jak push, peek, pop i size, a także metod wygody isEmpty i replace (ten ostatni jest bardziej wydajny substytutem pop następuje bezpośrednio push). Wartości nie są zapisywane jako pary [value, priority], ale po prostu jako value s; umożliwia to automatyczne ustalanie priorytetów typów, które mogą być porównywane natywnie przy użyciu operatora >. Niestandardowa funkcja komparatora przekazana do konstruktora PriorityQueue może być użyta do emulowania zachowania semantyki parowania, jak pokazano w przykładzie poniżej.

sterty podstawie Wykonanie:

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

---

przykład:

{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

Powinieneś używać standardowych bibliotek, np. Zamknięcie Library (goog.structs.PriorityQueue):

https://google.github.io/closure-library/api/goog.structs.PriorityQueue.html

Klikając w kodzie źródłowym, będziesz wiedzieć, że jest w rzeczywistości linkami do goog.structs.Heap które można śledzić:

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