TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Hàng đợi ưu tiên - Nguyễn Mạnh Hiển (HKI năm 2020-2021)

Bài giảng "Cấu trúc dữ liệu và giải thuật: Hàng đợi ưu tiên" cung cấp cho người học các kiến thức: Hàng đợi ưu tiên, cài đặt hàng đợi ưu tiên, đống nhị phân, cây nhị phân đầy đủ, cài đặt cây nhị phân đầy đủ, . | Hàng đợi ưu tiên Priority Queues Nguyễn Mạnh Hiển hiennm@ Hàng đợi ưu tiên Phần tử nhỏ nhất có độ ưu tiên cao nhất và sẽ được lấy ra đầu tiên. Chèn insert Thời gian O log N Xóa phần tử nhỏ nhất deleteMin Thời gian O log N Cài đặt hàng đợi ưu tiên Dùng danh sách liên kết insert dùng pushFront mất thời gian O 1 . deleteMin quét tìm rồi xóa min mất thời gian O N . Dùng cây nhị phân tìm kiếm insert và deleteMin mất thời gian O log N . Tuy nhiên cây nhị phân tìm kiếm quá phức tạp cho yêu cầu đơn giản hơn của hàng đợi ưu tiên. Đống nhị phân binary heap Là cách cài đặt phổ biến của hàng đợi ưu tiên. insert và deleteMin mất thời gian O log N . Đống nhị phân Gọi tắt là đống. Thỏa mãn 1. Là cây nhị phân đầy đủ. 2. Có tính chất thứ tự đống. Cây nhị phân đầy đủ Là cây nhị phân với tất cả các mức trừ mức dưới cùng đã được lấp đầy các nút từ trái sang phải. Số nút n 20 21 . 2h 1 1 2h h log n Mức 0 có 20 nút Mức 1 có 21 nút Mức 2 có 22 nút Mức h có ít nhất 1 nút h là chiều cao của cây Cài đặt cây nhị phân đầy đủ Lưu trữ các phần tử lần lượt từng mức vào vector v. Cha của v k là v k 2 . Con trái của v k là v 2k . Con phải của v k là v 2k 1 . vector v Tính chất thứ tự đống Với mọi nút X trên đống giá trị của X nhỏ hơn giá trị của các nút con trái và phải của X. Suy ra Phần tử nhỏ nhất trên đống nằm ở gốc. Không có thứ tự nào giữa các nút con của cùng một nút. 0 3 2 4 5 Cây nào là đống Cài đặt hàng đợi ưu tiên trong C template class BinaryHeap public BinaryHeap int capacity 100 Khởi tạo đống rỗng BinaryHeap const vector amp elems Dựng đống const T amp findMin Tìm phần tử nhỏ nhất ở gốc void insert const T amp x Chèn x vào đống void deleteMin Xóa phần tử nhỏ nhất ở gốc private int currentSize Số phần tử hiện có vector array Vector chứa các phần tử void buildHeap Giúp dựng đống trong hàm tạo void percolateDown int hole Giúp xóa min và dựng đống Chèn vào đống insert 14 Chèn vào đống insert x Tạo lỗ trống hole ở vị trí có sẵn tiếp theo trong đống x là giá trị của lỗ trống .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Bài giảng Cấu trúc dữ liệu
• Hàng đợi ưu tiên
• Cài đặt hàng đợi ưu tiên
• Đồng nhị phân
• Cây nhị phân đầy đủ
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp