Mỗi lần đọc lại quyển sách Clean Code của tác giả Robert C. Martin, mình lại nhận ra những điều mới để có thể giúp bản thân viết code chuyên nghiệp hơn. Cách đặt tên biến, hàm cũng ảnh hưởng khá nhiều đến độ “clean” của code mà đôi lúc chúng ta lại quên mất hoặc không để ý và khiến cho nó trở thành một đống hỗn độn theo thời gian.
Ở bài viết Priority Queue và những cách cài đặt, mình đã giới thiệu qua cấu trúc Priority Queue, những đặc trưng và cách cài đặt. Tuy nhiên trong một số trường hợp, chúng ta sẽ có nhu cầu cập nhật hoặc xóa phần tử khỏi Queue thông qua một index. Trong bài viết này chúng ta sẽ cùng cải tiến Priority Queue để có thể thực hiện các chức năng trên.
Bài viết Thuật toán Prim: Tìm cây khung nhỏ nhất đã giới thiệu đến các bạn ý tưởng của thuật toán này cũng như từng bước chạy thuật toán. Tiếp theo sẽ là phần hướng dẫn cài đặt thuật toán Prim cho đồ thị vô hướng có trọng số bằng ngôn ngữ Java.
Hôm nay mình xin chia sẻ một số ghi chú về Thuật toán Prim dùng để giải bài toán tìm cây khung nhỏ nhất (Minimum Spanning Tree) cho đồ thị vô hướng có trọng số. Prim cũng là một trong những thuật toán cổ điển để giải bài toán này.
Bàn về độ phức tạp thời gian, mình vẫn thường hay nghe các bạn nói “Một vòng for là $O(N)$, hai vòng for lồng nhau là $O(N^2)$". Thực ra không hẳn là như thế, nó còn phụ thuộc vào số bước thực hiện mỗi lần lặp. Mình cũng sẽ không bàn về phương pháp khoa học để đánh giá thuật toán mà thay vào đó nói về cách để mường tượng xác định độ phức tạp của thuật toán.
Hôm nay chúng ta cùng điểm qua một cấu trúc dữ liệu thuộc dòng họ nhà Queue có một tính chất khá đặc biệt - đẩy vào và lấy ra theo độ ưu tiên - chính là Priority Queue. Nó có rất nhiều ứng dụng, điển hình là trong Thuật toán nén Huffman Coding mà mình từng đề cập. Trong bài này chúng ta sẽ đi qua một số cách cài đặt của Priority Queue.
