二元堆積

• enqueue 以及 dequeue 時間複雜度為 O(logN)

• 二元堆積樹為完全二元樹

• 搜尋為 O(N)

• Parent 會大於或等於 Child

// 用陣列實作
export class Entry {
  value: string;
  priority: number;
  constructor(v: string, p: number) {
    this.value = v;
    this.priority = p;
  }
}
 
export class PQ {
  N: number;
  storage: Entry[] = [new Entry('', NaN)]; // 為了方便計算讓其從 1 開始儲存
  constructor() {
    this.N = 0;
  }
 
  less(i: number, j: number) {
    return this.storage[i].priority < this.storage[j].priority;
  }
 
  swap(i: number, j: number) {
    const temp = this.storage[i];
    this.storage[i] = this.storage[j];
    this.storage[j] = temp;
  }
 
  swim(child: number) {
    while (child > 1 && this.less(Math.floor(child / 2), child)) {
      // 父親節點在 child / 2 的商
      this.swap(child, Math.floor(child / 2));
      child = Math.floor(child / 2);
    }
  }
 
  sink(parent: number) {
    while (2 * parent <= this.N) {
      let child = 2 * parent;
      if (child < this.N && this.less(child, child + 1)) {
        child += 1;
      }
 
      if (!this.less(parent, child)) {
        break;
      }
 
      this.swap(child, parent);
      parent = child;
    }
  }
 
  enqueue(v: string, p: number) {
    this.N += 1;
    this.storage.push(new Entry(v, p));
    this.swim(this.N);
  }
 
  dequeue() {
    if (this.N === 0 || this.storage.length === 1) {
      throw new Error('Queue is empty');
    }
 
    const maxEntry = this.storage[1];
    this.storage[1] = this.storage[this.N];
    this.storage.pop();
    this.N -= 1;
    this.sink(1);
    return maxEntry;
  }
}
 

Enqueue

1. 把新元素放到最後一個

2. 從剛剛放入的 Child 開始與其 Parent 比較，遞迴至 Parent 大於 Child

Dequeue

1. 取出樹的 Root

2. 把最後一個 Child 放到 Root

3. 移出最後一個元素

4. 從 Root 開始確認二元樹的優先順序是否正確

5. sink 裡如果右 child 比左 child 大時就要用右 child 是因為如果直接使用左 child 與 parent 做 swap 會有可能遇到 new parent 會比右 child 大