- Đang đẩy xuống
- Đang so sánh
- Vừa hoán đổi
- Đã đúng chỗ
Sắp xếp vun đống
Sắp xếp vun đống đọc danh sách như một cây nhị phân và sắp lại thành đống cực đại, trong đó mỗi nút cha đều không nhỏ hơn các nút con. Khi đó giá trị lớn nhất nằm ở đỉnh. Hoán đổi nó về cuối, nơi nó ở lại, sửa lại đống, rồi lặp lại. Ứng dụng vẽ đống thành cây phía trên các cột, để bạn theo dõi từng giá trị khi nó được đẩy xuống. Nhấn Phát để xem quá trình sắp xếp, hoặc Bước và Lùi để đi từng phép so sánh. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Cây phía trên các cột hiển thị cùng các giá trị dưới dạng đống. Các ô đếm số phép so sánh, hoán đổi và số giá trị đã lấy ra khỏi đống. Chọn số cột, thứ tự ban đầu, hoặc tự nhập các số. Khi bảng được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.
Cách nó hoạt động
- Chọn số cột và thứ tự ban đầu: ngẫu nhiên, gần như đã sắp xếp, đảo ngược, hoặc ít giá trị khác nhau. Hoặc tự nhập các số.
- Nhấn Phát, hoặc dùng Bước và Lùi để đi từng phép so sánh. Kéo thanh trượt bước để nhảy đến bất kỳ đâu trong quá trình sắp xếp.
- Theo dõi cây: trước tiên mỗi nút cha được đẩy xuống cho đến khi dựng xong đống, sau đó gốc được hoán đổi về cuối và đống ngắn đi một.
Sắp xếp vun đống hoạt động thế nào
Đọc danh sách như một cây: giá trị ở vị trí i có các con ở vị trí 2i + 1 và 2i + 2. Dựng đống cực đại bằng cách đẩy xuống từng nút cha, bắt đầu từ nút cha cuối cùng: chừng nào một giá trị còn nhỏ hơn nút con lớn hơn của nó, hai giá trị hoán đổi. Khi gốc giữ giá trị lớn nhất, hoán đổi nó với giá trị cuối của đống. Giá trị đó giờ đã cố định, đống ngắn đi một, và gốc mới được đẩy xuống để khôi phục đống. Lặp lại cho đến khi đống rỗng.
Luôn là n log n, tại chỗ
Cây có khoảng log₂ n tầng, nên mỗi lần đẩy xuống cần tối đa khoảng 2 log₂ n phép so sánh, còn dựng đống cần ít hơn 2n. Vì vậy trường hợp xấu nhất của sắp xếp vun đống là khoảng 2n log₂ n phép so sánh, không cần bộ đệm: với 40 giá trị, tối đa 352. Khác với sắp xếp nhanh, nó không có dữ liệu đầu vào xấu, và khác với sắp xếp trộn, nó không cần thêm bộ nhớ. Trong thực tế nó thường chậm hơn cả hai, vì nó nhảy qua lại trong danh sách, và nó không ổn định.
Câu hỏi thường gặp
Sắp xếp vun đống hoạt động thế nào?
Nó biến danh sách thành đống cực đại, một cây lưu trong danh sách, trong đó mỗi nút cha đều không nhỏ hơn các nút con. Sau đó nó liên tục hoán đổi giá trị lớn nhất, ở gốc, về cuối đống và đẩy gốc mới xuống để sửa lại đống.
Đống là gì?
Một cây nhị phân hoàn chỉnh lưu trong danh sách mà không cần con trỏ: các con của vị trí i là vị trí 2i + 1 và 2i + 2. Trong đống cực đại, mỗi nút cha đều không nhỏ hơn các nút con, nên giá trị lớn nhất luôn ở gốc, vị trí 0.
Vì sao dựng đống nhanh?
Hầu hết giá trị nằm gần đáy cây và chỉ có thể đẩy xuống một hai tầng. Cộng công việc ở mọi tầng lại, toàn bộ quá trình dựng đống cần ít hơn 2n phép so sánh, chứ không phải n log n.
Sắp xếp vun đống có ổn định không?
Không. Việc hoán đổi gốc về cuối di chuyển các giá trị đi rất xa, nên các giá trị bằng nhau có thể đổi thứ tự.
Các số của tôi có bị gửi đi đâu không?
Không. Việc sắp xếp chạy trong trình duyệt của bạn, và cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Tới trình chỉnh sửa