TAILIEUCHUNG - Giáo trình giải thuật của Nguyễn Văn Linh part 6

HEAPSORT Ðịnh nghĩa Heap Cây sắp thứ tự bộ phận hay còn gọi là heap là cây nhị phân mà giá trị tại mỗi nút (khác nút lá) đều không lớn hơn giá trị của các con của nó. Ta có nhận xét rằng nút gốc a[1] của cây sắp thứ tự bộ phận có giá trị nhỏ nhất. | Giải thuật Sắp xếp HEAPSORT Định nghĩa Heap Cây sắp thứ tự bộ phận hay còn gọi là heap là cây nhị phân mà giá trị tại mỗi nút khác nút lá đều không lớn hơn giá trị của các con của nó. Ta có nhận xét rằng nút gốc a 1 của cây sắp thứ tự bộ phận có giá trị nhỏ nhất. Ví dụ 2-5 Cây sau là một heap. Nguyên Văn Linh Trang 31 Sưu tầm bởi Giải thuật Sắp xếp Ý tưởng 1 Xem mảng ban đầu là một cây nhị phân. Mỗi nút trên cây lưu trữ một phần tử mảng trong đó a 1 là nút gốc và mỗi nút không là nút lá a i có con trái là a 2i và con phải là a 2i 1 . Với cách tổ chức này thì cây nhị phân thu được sẽ có các nút trong là các nút a 1 . a n DIV 2 . Tất cả các nút trong đều có 2 con ngoại trừ nút a n DIV 2 có thể chỉ có một con trái trong trường hợp n là một số chẵn . 2 Sắp xếp cây ban đầu thành một heap căn cứ vào giá trị khoá của các nút. 3 Hoán đổi a 1 cho cho phần tử cuối cùng. 4 Sắp lại cây sau khi đã bỏ đi phần tử cuối cùng để nó trở thành một heap mới. Lặp lại quá trình 3 và 4 cho tới khi cây chỉ còn một nút ta sẽ được mảng sắp theo thứ tự giảm. Thiết kế và cài đặt giải thuật Thủ tục PushDown Thủ tục PushDown nhận vào 2 tham số first và last để đẩy nút first xuống. Giả sử a first . a last đã đúng vị trí giá trị khoá tại mỗi nút nhỏ hơn hoặc bằng giá trị khoá tại các nút con của nó ngoại trừ a first . PushDown dùng để đẩy phần tử a first xuống đúng vị trí của nó trong cây và có thể gây ra việc đẩy xuống các phần tử khác . Xét a first có các khả năng có thể xẩy ra Nếu a firrst chỉ có một con trái và nếu khoá của nó lớn hơn khoá của con trái a first .key a 2 first .key thì hoán đổi a first cho con trái của nó và kết thúc. Nếu a first có khoá lớn hơn con trái của nó a first .key a 2 first .key và khoá của con trái không lớn hơn khoá của con phải a 2 first .key a 2 first 1 .key thì hoán đổi a first cho con trái a 2 first của nó việc này có thể gây ra tình trạng con trái sẽ không đúng vị trí nên phải xem xét lại con trái để có thể đẩy .

• Kỹ thuật lập trình
• Kỹ thuật lập trình
• giải thuật
• hướng dẫn giải thuật
• cấu trúc dữ liệu
• lập trìnhKỹ thuật lập trình
• giải thuật
• hướng dẫn giải thuật
• cấu trúc dữ liệu
• lập trình
• kỹ thuật máy tính C
• kỹ thuật lập trình C
• giáo trình kỹ thuật lập trình C
• bài tập kỹ thuật lập trình C
• tài liệu kỹ thuật lập trình C
• chuyên ngành kỹ thuật lập trình
• Bài tập kỹ thuật lập trình
• Tài liệu kỹ thuật lập trình
• Bài giảng kỹ thuật lập trình
• Ưng dụng kỹ thuật lập trình
• Ngôn ngữ C
• kỹ thuật máy tính
• môn kỹ thuật lập trình
• ôn tập kỹ thuật lập trình
• cách học kỹ thuật lập trình
• kiến thức kỹ thuật lập trình
• học môn kỹ thuật lập trình
• Đề thi Kỹ thuật lập trình cơ bản
• Câu hỏi Kỹ thuật lập trình cơ bản
• Luyện thi Kỹ thuật lập trình cơ bản
• Ôn thi Kỹ thuật lập trình cơ bản
• Bài thi Kỹ thuật lập trình cơ bản
• Tài liệu Kỹ thuật lập trình cơ bản
• giáo trình kỹ thuật lập trình
• thủ thuật lập trình
• lập trình căn bản
• kỹ thuật phần mềm
• chương trình lập trình
• giáo trình lập trình
• lập trình hướng đối tượng
• tài liệu lập trình
• chuyên ngành lập trình
• tổng quan về lập trình
• Tổng quan về kỹ thuật lập trình
• Lập trình tốt
• Nguyên tắc lập trình
• Ngôn ngữ lập trình
• ngôn ngữ C++
• Kỹ thuật lập trình căn bản
• Kỹ thuật lập trình nâng cao
• Lập trình C căn bản
• Lập trình C nâng cao