Cấu trúc giải thuật vun đống(Heap Sort)-Nhóm 5 #Đ23HT_CTDL_CHIEU6_BAITAPNHOM

Xin chào cô và các bạn Hôm nay em sẽ đại diện nhóm 5 giới thiệu đến cô và các bạn giải thuật sắc xếp buôn đóng HEADSHOT Nhóm em gồm có 5 đồng viên gồm em Nguyễn Ngọc Thảo Nguyên bạn Ngô Ngọc Yến, Nguyễn Thị Thùy Trang Trường Thủy Huy Tuyên và Phan Thủy Huy Tuyên Về nội dung của slide ngày hôm nay thì gồm phần 1 là ý tưởng phần 2 là nguyên tắc hạt động phần 3 ví dụ phần 4 chương trình phần 5 hướng dụng và phần 6 là đánh giá Nói sơ về giải thuật HEADSHOT thì HEADSHOT là một lực tán sắp xếp sử dụng cấu trúc dữ liệu HEAD để sắp xếp một mãn thứ tự tăng dần hoặc giảm dần giải thuật gồm 2 giai đoạn chính giai đoạn đầu tiên là xây dựng HEAD có nghĩa là HEADPHY biến mãn ban đầu thành một cây nhị phân thỏa mãn tính chất của một mát HEAD với sắp xếp là tăng dần hoặc minHEAD với sắp xếp là giảm dần tiếp theo sắp xếp HEADSHOT lần lượt đưa phần tử lớn nhất hoặc nhỏ nhất về cuối mãn và tiếp tục buôn đóng các phần còn lại vật phần đầu tiên của bài đó là ý tưởng chúng ta có 3 ý chính như sau chia mãn ban đầu thành 2 phần mãn đã sắp xếp ban đầu là mãn rộng và mãn chưa sắp xếp chứa tất cả các phần tử ban đầu đến bước thứ 2 tìm phần tử lớn nhất hoặc nhỏ nhất trong mãn chưa sắp xếp và đưa vào mãn đã sắp xếp và bước cuối cùng chúng ta sẽ sử dụng cấu trúc tử liệu HEAD để thực hiện contexture một cách hiệu quả đến phần thứ 2 nguyên tắc hoạt động chúng ta có 4 nguyên tắc chính như sau nguyên tắc thứ nhất xây dựng HEAD từ mãn ban đầu nguyên tắc thứ 2 lấy phần tử lớn nhất và đưa vào cuối mãn nguyên tắc thứ 3 HAPPY FILE lấy phần còn lại và nguyên tắc cuối cùng lặp lại quá trình đến khi kết thúc và mời cô và các bạn cùng đến với phần số 3 đó là ví dụ minh họa cho mãn đầu vào bước 1 xây dựng HEAD vun cây gốc A3 ta được 1 cây với hứa tử mới 2, 3, 7, 6, 4, 1, 5 như hình bên tiếp theo vun cây gốc A2 ta tiếp tục được 1 cây với hứa tử mới 2, 6, 7, 3, 4, 1, 5 và cuối cùng vun cây gốc A1 ta được 1 cây với hứa tử hoàn chỉnh 7, 6, 5, 3, 4, 1, 2 kết quả 7, 6, 5, 3, 4, 1, 2 đây là 1 mát HEAD bước 2 sắp xếp đổi chỗ phần tử gốc lớn nhất với phần tử cuối vun đóng lại phần tử còn lại lặp lại quá trình này cho đến khi mãn được sắp xếp và đến phần thứ 4 mời cô và các bạn cùng xem qua chương trình mà chúng ta sẽ chạy trên máy về hàng chain HEAD sẽ sắp xếp mãn thành diện cây với đỉnh là giá trị lớn nhất sau đó hàng SWAP sẽ đổi vị trí của giá trị đỉm với giá trị cuối rồi tách giá trị cuối ra khỏi mãn và lặp lại bước 1 với mãn mới là mãn mà khi đã lồi bỏ giá trị lớn nhất đến với phần 5 ứng dụng ngoài giải thuật sắp xếp vun đóng cấu trúc đóng còn được ứng dụng trong nhiều giải thuật khác khi phần lấy ra nhanh chóng các phần tử lớn nhất hoặc nhỏ nhất của một dãy phần tử chẳng hạn trong hàng đừa có ưu tiên trong đó tiêu chuẩn ưu tiên là có khóa lớn nhất hoặc khóa nhỏ nhất có thể tìm thấy điều đó trong giải thuật tiền bộ mã Huffman trong một bản thần số của các ký tự Về phần cuối cùng chúng ta hãy cùng đánh giá về những ưu điểm và nhợt điểm của giải thuật vun đóng Hipshot như sau Về tốc độ thì giải thuật Hipshot sẽ chạy chậm hơn giải thuật Whipshot một chút. Tuy nhiên ưu điểm của Hipshot là độ phức tạp trong trường hợp tệ nhất chỉ là không N-lock. Ngoài ra chúng ta không cần sử dụng thêm bất kỳ một cấu trúc dữ liệu nào khác trong quá trình sắp xếp Vì thế, Hipshot vẫn luôn được ưu chuộng và đánh giá là một thuật toán sắp xếp tốt. Về nhợt điểm của Hipshot thì có lẽ là Hipshot sẽ chạy chậm hơn Whipshot và Whipshot và nó là một thuật toán sắp xếp không ổn định về thời gian Tuy nhiên, cấu trúc dữ liệu Hipshot lại có những dụng to lớn hơn nhiều trong thực tế hơn là chỉ để sắp xếp Vì vậy, hiểu và ứng dụng được Hipshot cũng rất tốt cho các bạn đang học về cấu trúc dữ liệu và giải thuật Về phần giới thiệu của nhóm em Cảm ơn đến cô và các bạn về giải thuật sắp xếp buôn đắm Hipshot đã kết thúc. Cảm ơn cô và các bạn cũng lắng nghe