Ở 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.
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.
Heap được ứng dụng khá nhiều trong các cấu trúc dữ liệu và giải thuật. Nếu bạn đã nghe qua Heap sort thì chắc chắn sẽ làm quen với khái niệm này. Ngoài ra, Heap cũng còn được ứng dụng trong Prority Queue - một cấu trúc dữ liệu hoạt động theo cơ chế vào trước ra trước. Bài viết này sẽ note một số ý chính về Heap.
Cấu trúc Graph (đồ thị) có rất nhiều ứng dụng trong thực tiễn. Bài viết này sẽ note lại tổng quan những điểm chính về việc implement cấu trúc dữ liệu này.
Chúng ta cùng tìm hiểu một cấu trúc dữ liệu cũng khá hữu ích là Danh sách liên kết vòng (Circular Linked List). Nó biểu diễn một cách tự nhiên các cấu trúc dạng tròn như các góc của đa giác, v.v… DSLK vòng có hai dạng thường thấy là dạng vòng đơn và vòng kép.
Nếu bạn đã đọc bài viết về Danh sách liên kết đơn thì có thể thấy việc tổ chức dạng danh sách tiện lợi hơn rất nhiều so với dùng mảng. Tuy nhiên, danh sách liên kết đơn vẫn có nhược điểm là chỉ có thể duyệt từ đầu đến cuối. Vì vậy, một số thao tác sẽ rất khó cài đặt trên nó. Danh sách liên kết kép có thể khắc phục nhược điểm này. Hầu hết các thao tác điều giống với danh sách liên kết đơn nhưng mình cũng khuyên các bạn nên đọc bài viết Danh sách liên kết đơn và các thao tác cơ bản trước khi đọc bài viết này. Các thao tác được minh họa bằng C++.
