Binary Heaps

Giới thiệu

Binary heaps giống là complete binary tree (là cây nhị phân được điền đầy đủ ở tất cả các mức từ trái sang phải, ngoài trừ có thể mức cuối cùng), nó có một số tính chất sau:

• Max Heap: các node cha luôn lớn hơn node con.
• Min Heap: các node cha nhỏ hơn node con.

Binary Heap có thể được biểu diễn dưới dạng array như sau:

Cách xác index của các node cha và con trong 1 array độ như sau:

• Nếu 1 node nằm index n:
  • Node con bên trái được lưu ở vị trí: 2n + 1
  • Node con bên phải: 2n + 2
• Vị trí của node cha nếu node con nằm ở index n (làm tròn xuống): (n-1)/2

Khởi tạo

class MaxBinaryHeap { values; constructor() { this.values = []; } insert(element) {} bubbleUp() {} extractMax() {} sinkDown() {}
}

Khởi tạo các method

insert

 insert(element) { this.values.push(element); this.bubbleUp(); } bubbleUp() { let idx = this.values?.length - 1; let element = this.values[idx]; while (idx > 0) { const parentIdx = Math.floor((idx - 1) / 2); const parentElement = this.values[parentIdx]; if (element < parentElement) break; this.values[idx] = parentElement; this.values[parentIdx] = element; idx = parentIdx; } }

extractMax

Trả về giá trị gốc (lớn nhất) → Thay giá trị gốc bằng phần tử cuối cùng của Heap → Sắp xếp lại heap cho đúng.

 extractMax() { const max = this.values[0]; const end = this.values.pop(); this.values[0] = end; this.sinkDown(); return max; } sinkDown() { let idx = 0; let element = this.values[idx]; const length = this.values.length; while (true) { element = this.values[idx]; const leftChildIndx = 2 * idx + 1; const rightChildIndx = 2 * idx + 2; const leftChildElement = this.values[leftChildIndx]; const rightChildElement = this.values[rightChildIndx]; let swap = null; if (leftChildIndx < length) { if (leftChildElement > element) { swap = leftChildIndx; } } if (rightChildIndx < length) { if ( (rightChildElement > element && !swap) || (swap && rightChildElement > leftChildElement) ) { swap = rightChildIndx; } } if (!swap) break; this.values[idx] = this.values[swap]; this.values[swap] = element; idx = swap; } }

Độ phức tạp

Priority Queue

Là kiểu dữ liệu giống queue nhưng được sắp xếp dựa vào độ ưu tiên.

Ở đây ta sẽ sử dụng Binary Heap để xây dựng Priority Queue

Khởi tạo

class PriorityQueueNode { value; priority; constructor(value, priority) { this.value = value; this.priority = priority; }
} class PriorityQueue { values: PriorityQueueNode[]; constructor() { this.values = []; } enqueue(value, priority) {} bubbleUp() {} dequeue() {} sinkDown() {}
}

Khởi tạo các method

enqueue

 enqueue(value, priority) { const newNode = new PriorityQueueNode(value, priority); this.values.push(newNode); this.bubbleUp(); } bubbleUp() { let idx = this.values?.length - 1; let element = this.values[idx]; while (idx > 0) { const parentIdx = Math.floor((idx - 1) / 2); const parentElement = this.values[parentIdx]; if (element.priority < parentElement.priority) break; this.values[idx] = parentElement; this.values[parentIdx] = element; idx = parentIdx; } }

dequeue

 dequeue() { const max = this.values[0]; const end = this.values.pop(); this.values[0] = end; this.sinkDown(); return max; } sinkDown() { let idx = 0; let element = this.values[idx]; const length = this.values.length; while (true) { const leftChildIndx = 2 * idx + 1; const rightChildIndx = 2 * idx + 2; element = this.values[idx]; const leftChildElement = this.values[leftChildIndx]; const rightChildElement = this.values[rightChildIndx]; let swap = null; if (leftChildIndx < length) { if (leftChildElement.priority > element.priority) { swap = leftChildIndx; } } if (rightChildIndx < length) { if ( (!swap && rightChildElement.priority > element.priority) || (swap && rightChildElement.priority > leftChildElement.priority) ) { swap = rightChildIndx; } } if (!swap) break; this.values[idx] = this.values[swap]; this.values[swap] = element; idx = swap; } }