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 .
