Các đống nhị phân và hàng đợi ưu tiên qua JavaScript
Mặc dù tôi chắc chắn rằng tất cả ta đều có thể đồng ý rằng hàng đợi là điều tuyệt vời nhất kể từ khi bánh mì cắt lát, nhưng ta có thể làm tốt hơn nhiều bằng cách trộn chúng với một loại cây được gọi là đống. Với heaps, ta có thể cấu trúc dữ liệu của bạn thành một hàng đợi thông minh hơn được sắp xếp theo mức độ quan trọng thay vì thứ tự.
Các khái niệm
Không giống như cây tìm kiếm binary , nơi ta so sánh và tổ chức các giá trị của bạn giữa các anh chị em, với đống, ta chỉ làm việc giữa cha mẹ và con cái của họ. Điều này cung cấp cho ta hai khả năng cho heap, max heap và max heap min heap , cho dù bạn đang di chuyển từ giá trị cao nhất đến giá trị thấp nhất hay ngược lại. Vì lý do đơn giản, ta sẽ chỉ tập trung vào đống tối đa, vì quá dễ dàng để chuyển đổi nó thành một đống nhỏ nhất.
Giống như với cây tìm kiếm binary , đống binary chỉ được phép có hai hoặc ít hơn con đối với một phụ huynh. Chúng cũng đặc biệt vì chúng luôn cân bằng vì mỗi nút mới sẽ được thêm vào một mức từ trái sang phải cho đến khi đầy.
Đáng buồn thay, danh sách được liên kết thường không phải là cách tiếp cận tốt nhất cho đống binary , mặc dù thường được khái niệm hóa như một cây với các phần tử con bên trái và bên phải, mặc dù vẫn có thể.
Hầu hết thời gian sẽ tốt hơn nếu xử lý nó dưới dạng một mảng, vì vậy đó là những gì ta sẽ đề cập ở đây. Thứ tự như bạn mong đợi với mọi thứ từ trái sang phải ở một cấp độ trước khi chuyển sang cấp độ tiếp theo.
Bằng cách này, ta tạo ra một mô hình rất nhất quán để tìm kiếm con của một nút. Tất cả các node con bên trái của nút sẽ nằm chính xác ở vị trí cách nút cha 2n + 1 , với n là chỉ số của nút mẹ và tất cả các node con bên phải là 2n + 2 .
Thêm nút
Có vẻ như việc thêm một nút mới sẽ đơn giản như đẩy vào mảng của ta , nhưng phần khó khăn là ta cần so sánh nó với các node cha ở giữa chính nó và nút tối đa, sau đó sắp xếp lại chúng cho phù hợp.
Graphic / Animation nhờ VisuAlgo.net
Sau khi ta đẩy mục mới của bạn lên cuối mảng, ta cần "làm nổi" các giá trị lớn hơn của ta . Đầu tiên, ta cần lấy mục mới ở cuối mảng, ta sẽ chia mục này thành index và mục mới tại index đó.
Mỗi khi ta thêm một mục, ta sẽ sử dụng đảo ngược của phương trình tìm con, (n-1)/2 , để tìm cha mẹ của nó. Nếu nút cha của nó nhỏ hơn nút hiện tại, hãy swap chúng rồi lưu index của nó sẽ là nút current tiếp theo. Điều này sẽ tiếp tục cho đến khi không còn cha mẹ.
Vì nó sẽ dần dần di chuyển index của ta lên từ cuối, miễn là nó lớn hơn 0, hãy tiếp tục swap .
class BH { constructor() { this.values = []; } add(element) { this.values.push(element); let index = this.values.length - 1; const current = this.values[index]; while (index > 0) { let parentIndex = Math.floor((index - 1) / 2); let parent = this.values[parentIndex]; if (parent <= current) { this.values[parentIndex] = current; this.values[index] = parent; index = parentIndex; } else break; } } } const tree = new BH(); tree.add(3); tree.add(4); tree.add(31); tree.add(6); console.log(tree); // [31, 6, 4, 3] Loại bỏ Max
Loại bỏ nút trên cùng phức tạp hơn một chút so với bạn nghĩ. Ta sẽ trả về nút đầu tiên, giá trị tối đa của ta , sau đó lấy nút cuối cùng, cuối mảng của ta và đặt nó làm giá trị tối đa mới.
Ta làm điều đó để ta có thể sử dụng giá trị thấp nhất của bạn làm cơ sở dễ dàng so sánh với các giá trị khác của ta khi ta “chìm xuống” trở lại phần cuối của cây trong khi thực hiện so sánh và swap trong quá trình thực hiện.
Graphic / Animation nhờ VisuAlgo.net
Phần đơn giản là lấy giá trị tối đa hiện tại của ta và bật nó ra trước khi thay thế nó bằng mục cuối cùng, sau đó ta có thể trả lại giá trị tối đa ban đầu của bạn sau khi mọi thứ khác được thực hiện.
Khi ta có một index bắt đầu, ta muốn lấy cả con bên phải và bên trái của nó. Nếu con bên trái là một mục hợp lệ và lớn hơn, thì ta có thể lưu nó dưới dạng swap để chạy swap khi tất cả các so sánh được thực hiện.
Con bên phải phức tạp hơn một chút, ta chỉ muốn một con lớn nhất được swap với cha mẹ. Ta sẽ thêm một yêu cầu riêng rằng rightChild chỉ có thể được đặt làm swap nếu nó chưa được xác định hoặc nó lớn hơn leftChild .
class BH { extractMax() { const max = this.values[0]; const end = this.values.pop(); this.values[0] = end; let index = 0; const length = this.values.length; const current = this.values[0]; while (true) { let leftChildIndex = 2 * index + 1; let rightChildIndex = 2 * index + 2; let leftChild, rightChild; let swap = null; if (leftChildIndex < length) { leftChild = this.values[leftChildIndex]; if (leftChild > current) swap = leftChildIndex; } if (rightChildIndex < length) { rightChild = this.values[rightChildIndex]; if ( (swap === null && rightChild > current) || (swap !== null && rightChild > leftChild) ) swap = rightChildIndex; } if (swap === null) break; this.values[index] = this.values[swap]; this.values[swap] = current; index = swap; } return max; } } const tree = new BH(); tree.add(3); tree.add(4); tree.add(31); tree.add(6); console.log(tree.extractMax()); // 31 Hàng đợi ưu tiên
Với một vài chỉnh sửa nhỏ, ta có thể trộn đống binary với hàng đợi và tạo một loại hàng đợi sắp xếp dữ liệu của ta theo mức độ quan trọng thay vì khi nó được thêm vào.
Ta có thể đạt được điều này đủ đơn giản bằng cách lưu trữ các node thay vì các số đơn lẻ. Mỗi nút sẽ có mức độ ưu tiên (giả sử từ 1-5), mức độ ưu tiên này sẽ được sử dụng để xác định thứ tự. Khi mức độ ưu tiên trên hai nút giống nhau, nút con bên trái, vì nó sẽ được thêm vào trước, sẽ đi trước.
Tất cả ta phải làm là sử dụng của nút priority mỗi khi ta làm một so sánh trong một if tuyên bố.
class Node { constructor(val, priority) { this.val = val; this.priority = priority; } } class PQ { constructor() { this.values = []; } enqueue(val, priority) { let newNode = new Node(val, priority); this.values.push(newNode); let index = this.values.length - 1; const current = this.values[index]; while (index > 0) { let parentIndex = Math.floor((index - 1) / 2); let parent = this.values[parentIndex]; if (parent.priority <= current.priority) { this.values[parentIndex] = current; this.values[index] = parent; index = parentIndex; } else break; } } dequeue() { const max = this.values[0]; const end = this.values.pop(); this.values[0] = end; let index = 0; const length = this.values.length; const current = this.values[0]; while (true) { let leftChildIndex = 2 * index + 1; let rightChildIndex = 2 * index + 2; let leftChild, rightChild; let swap = null; if (leftChildIndex < length) { leftChild = this.values[leftChildIndex]; if (leftChild.priority > current.priority) swap = leftChildIndex; } if (rightChildIndex < length) { rightChild = this.values[rightChildIndex]; if ( (swap === null && rightChild.priority > current.priority) || (swap !== null && rightChild.priority > leftChild.priority) ) swap = rightChildIndex; } if (swap === null) break; this.values[index] = this.values[swap]; this.values[swap] = current; index = swap; } return max; } } const tree = new BH(); tree.enqueue(3, 2); tree.enqueue(4, 5); tree.enqueue(31, 1); tree.enqueue(6, 3); console.log(tree.dequeue()); // 4 console.log(tree.dequeue()); // 6 console.log(tree.dequeue()); // 3 console.log(tree.dequeue()); // 31 Bớt tư tưởng
Cũng giống như cách ta sử dụng hàng đợi tiêu chuẩn cho hàng đợi ưu tiên duyệt cây sẽ rất cần thiết cho việc duyệt đồ thị và cấu trúc phức tạp hơn một cách thông minh.
Việc chuyển đổi một đống tối đa thành một đống tối thiểu cũng đơn giản như thay đổi số đăng nhập lớn hơn thành nhỏ hơn trong tất cả các so sánh của ta .
Các tin liên quan
JavaScript bất biến có thể thay đổi2020-04-02
Hiểu các tham số mặc định trong JavaScript
2020-03-31
Cookie là gì và cách làm việc với chúng bằng JavaScript
2020-03-19
Tham quan nhanh về date-fns, Thư viện ngày JavaScript đơn giản
2020-03-18
Phương thức getOwnPropertyDescriptors trong JavaScript
2020-03-12
Cây tìm kiếm nhị phân thông qua JavaScript
2020-03-03
Tree Traversal qua JavaScript
2020-03-02
Hiểu về Trình tạo trong JavaScript
2020-02-28
Triển khai Thành phần Tab từ Scratch trong Vanilla JavaScript
2020-02-24
Khám phá cây qua JavaScript
2020-02-23
