TAILIEUCHUNG - Cấu trúc dữ liệu : Một số phương pháp sắp xếp part 3

Tiến hành nhiều lần việc loại bỏ phần tử gốc của cây cho đến khi tất cả các phần tử của cây đều là -∞, khi đó xếp các phần tử theo thứ tự loại bỏ trên cây sẽ có dãy đã sắp xếp. Trên đây là ý tưởng của giải thuật sắp xếp cây. 2. Cấu trúc dữ liệu Heap Tuy nhiên, để cài đặt thuật toán này một cách hiệu quả, cần phải tổ chức một cấu trúc lưu trữ dữ liệu có khả năng thể hiện được quan hệ của các phần tử trong cây với n. | Loại bỏ 8 ra khỏi cây và thế vào các chỗ trống giá trị -O để tiện việc cập nhật lại cây Tiến hành nhiều lần việc loại bỏ phần tử gốc của cây cho đến khi tất cả các phần tử của cây đều là - khi đó xếp các phần tử theo thứ tự loại bỏ trên cây sẽ có dãy đã sắp xếp. Trên đây là ý tưởng của giải thuật sắp xếp cây. 2. Cấu trúc dữ liệu Heap Tuy nhiên để cài đặt thuật toán này một cách hiệu quả cần phải tổ chức một cấu trúc lưu trữ dữ liệu có khả năng thể hiện được quan hệ của các phần tử trong cây với n ô nhớ thay vì 2n-1 như trong ví dụ. Khái niệm heap và phương pháp sắp xếp Heapsort do đề xuất đã giải quyết được các khó khăn trên. 11 Định nghĩa Heap Giả sử xét trường hợp sắp xếp tăng dần khi đó Heap được định nghĩa là một dãy các phần tử ap a2 . aq thoả các quan hệ sau với mọi i thuộc p q 1 . ai a2i 2 . ai a2i 1 ai a2i ai a2i 1 là các cặp phần tử liên đới Heap có các tính chất sau Tính chất 1 Nếu ap a2 . aq là một heap thì khi cắt bỏ một số phần tử ở hai đầu của heap dãy con còn lại vẫn là một heap. Tính chất 2 Nếu ap a2 . aq là một heap thì phần tử a1 đầu heap luôn là phần tử lớn nhất trong heap. Tính chất 3 Mọi dãy ap a2 . aq dãy con aj aj 1 . ar tạo thành một heap với j q div 2 1 . Giải thuật Heapsort Giải thuật Heapsort trải qua 2 giai đoạn Giai đoạn 1 Hiệu chỉnh dãy số ban đầu thành heap Giai đoạn 2 Sắp xếp dãy số dựa trên heap Bước 1 Đưa phần tử lớn nhất về vị trí đúng ở cuối dãy r n Hoánvị a1 ar Bước 2 Loại bỏ phần tử lớn nhất ra khỏi heap r r-1 Hiệu chỉnh phần còn lại của dãy từ a1 a2 . ar thành một heap. Bước 3 Nếu r 1 heap còn phần tử Lặp lại Bước 2 Ngược lại Dừng Dựa trên tính chất 3 ta có thể thực hiện giai đoạn 1 bằng cách bắt đầu từ heap mặc nhiên an 2 1 an 2 2 . an sau đó thêm 12 dần các phần tử an 2 an 2-1 . a1 ta sẽ nhân được heap theo mong muốn. Ví dụ Cho dãy số a 12 2 8 5 1 6 4 15 Giai đoạn 1 hiệu chỉnh dãy ban đầu thành heap 1 3 Giai đoạn 2 Sắp xếp dãy số dựa trên heap .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• tài liệu Cấu trúc dữ liệu
• đề cương Cấu trúc dữ liệu
• giáo trình Cấu trúc dữ liệu
• bài giảng 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 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 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
• bài tập 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
• 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