Đống và hàng đợi ưu tiên
Đống và hàng đợi ưu tiên
Đống là một cái cây nhị phân, nhưng bạn sẽ không tìm thấy một con trỏ nào trong nó. Nó nằm gọn trong một mảng, và toàn bộ hình cây được suy ra từ ba phép tính chỉ số. Bài này vẽ cả hai hình cùng lúc, tô cùng màu, để bạn thấy chúng là một.
Có một loại câu hỏi mà ngăn xếp và hàng đợi không trả lời được: "cho tôi phần tử quan trọng nhất đang chờ". Ngăn xếp trả cái vào sau cùng, hàng đợi trả cái vào đầu tiên, cả hai đều không nhìn vào giá trị. Bộ lập lịch của hệ điều hành cần cái này, thuật toán A* cần cái này ở mỗi vòng lặp, và mọi bài toán "gộp dần các mảnh nhỏ nhất" cũng vậy.
Cấu trúc trả lời câu hỏi đó gọi là hàng đợi ưu tiên, và cách cài đặt phổ biến nhất của nó gọi là đống. Luật của nó ngắn tới mức đọc xong bạn sẽ nghi là thiếu. Với đống nhỏ nhất: mỗi nút không được nhỏ hơn cha của nó. Hết. Không có ràng buộc nào giữa hai anh em, không có ràng buộc nào giữa hai nhánh. Bản đống lớn nhất chỉ là tấm gương của nó, đảo dấu là xong, và sim có nút để bạn đổi qua lại. So với cây tìm kiếm nhị phân, đống hứa ít hơn hẳn.
Đổi lại nó được hai thứ. Thứ nhất, vì luật lỏng nên đống có thể ép mình luôn đầy từ trái sang phải, và một cây đầy như vậy thì mô tả được bằng đúng một mảng, không cần liên kết nào. Thứ hai, chiều cao của nó không phụ thuộc thứ tự dữ liệu đi vào: nó luôn đúng bằng floor(log2 n) + 1, không có ca xấu, không có cái que.
Sim dưới đây vẽ cùng một đống hai lần, một lần thành cây và một lần thành mảng, và tô cùng màu lên cùng một phần tử ở cả hai hình. Nếu bạn thấy bài đang dẫn bạn tới một kết luận, hãy vặn núm cho tới khi kết luận đó sai.
1 · Mảng vào ✎ sửa được
2 · Cùng một thứ, vẽ hai kiểu
2i+1, 2i+2 và floor((i-1)/2).i là ô bạn đang soi, ô ghi cha là cha của nó, ô ghi con là hai con. Chữ đi kèm màu là cố ý: đọc được cả khi bạn không phân biệt được màu.floor(log2(4 + 1)) + 1 = 3. Cha của nó là ô 1 (70), vì floor((4 - 1) / 2) = 1. Con trái ở ô 9 (100) vì 2×4+1, con phải ở ô 10 (110) vì 2×4+2.floor(log2 n) + 1, và log2(15) ≈ 3,913 · Dựng đống, hai cách trên cùng một mảng ✎ sửa được
| trên đúng 15 giá trị này | chèn lần lượt | dồn đống từ dưới lên |
|---|---|---|
| số bước | 15 | 7 |
| phép so sánh | 30 | 22 |
| phép đổi chỗ | 20 | 10 |
| đống thu được | 10 70 20 120 90 50 30 150 140 130 100 110 60 80 40 | 10 70 20 120 90 40 30 150 130 100 110 50 140 80 60 |
4 · Chèn và lấy gốc ra ✎ sửa được
5 · Hai cách dựng lớn lên khác bậc ✎ sửa được
Bảng này chạy thật cả hai thuật toán trên mảng dài tới 255 phần tử, chỉ là không vẽ ra vì không đủ chỗ. Cột giảm dần là ca xấu nhất của cách chèn: mỗi giá trị mới đều vượt mọi giá trị đã có nên phải leo hết chiều cao. Cột trung bình lấy trên 64 hoán vị sinh bằng bộ sinh có hạt giống, không dùng Math.random, nên tải lại trang vẫn ra đúng con số này.
| n | tầng | mảng giảm dần, phép so sánh | mảng giảm dần, phép đổi chỗ | trung bình 64 hoán vị, phép so sánh | |||
|---|---|---|---|---|---|---|---|
| chèn | dồn | chèn | dồn | chèn | dồn | ||
| 1 | 1 | 0 | 0 | 0 | 0 | 0,0 | 0,0 |
| 3 | 2 | 2 | 2 | 2 | 1 | 2,0 | 2,0 |
| 7 | 3 | 10 | 8 | 10 | 4 | 8,2 | 7,8 |
| 15 | 4 | 34 | 22 | 34 | 11 | 23,4 | 21,1 |
| 31 | 5 | 98 | 52 | 98 | 26 | 56,5 | 49,5 |
| 63 | 6 | 258 | 114 | 258 | 57 | 124,0 | 107,9 |
| 127 | 7 | 642 | 240 | 642 | 120 | 265,6 | 226,3 |
| 255 | 8 | 1538 | 494 | 1538 | 247 | 551,1 | 464,8 |
n = 15, chèn lần lượt tốn 34 phép so sánh và 34 phép đổi chỗ, dồn đống tốn 22 và 11. Với n = 31 thì thành 98 so với 52 phép so sánh, và 98 so với 26 phép đổi chỗ. Tỉ lệ phép đổi chỗ đi từ 3,09 lên 3,77 lần, và cứ tiếp tục nới ra ở các dòng dưới.| n | trần của cách chèn: tổng floor(log2 k) | trần của cách dồn: 2(n − số bit 1 của n) | trần chèn chia trần dồn |
|---|---|---|---|
| 1 | 0 | 0 | 0,00 lần |
| 3 | 2 | 2 | 1,00 lần |
| 7 | 10 | 8 | 1,25 lần |
| 15 | 34 | 22 | 1,55 lần |
| 31 | 98 | 52 | 1,88 lần |
| 63 | 258 | 114 | 2,26 lần |
| 127 | 642 | 240 | 2,67 lần |
| 255 | 1538 | 494 | 3,11 lần |
6 · Sắp xếp bằng đống
Dựng một đống lớn nhất rồi liên tục đổi gốc xuống cuối và thu vùng sống lại một ô. Cái đuôi đã sắp lớn lên ngay trong mảng mà đống đang co lại, nên không có mảng thứ hai nào được cấp phát: đây là ý nghĩa của chữ tại chỗ.
Một phép sắp xếp ổn định là phép giữ nguyên thứ tự cũ của hai bản ghi có khoá bằng nhau. Sắp xếp bằng đống không giữ, và phản ví dụ nhỏ tới mức chỉ cần hai bản ghi.
Ở vị trí 1 hai đầu ra đã khác nhau: đáng ra phải là 50a, nhưng đống trả về 50b. Hai bản ghi khoá bằng nhau đã bị đảo. Bước dựng không hề đụng vào chúng, vì một thế hoà không làm gì cả; chính bước đổi gốc xuống cuối mới lật cặp đó, và bước ấy đổi chỗ vô điều kiện.
7 · Đống không phải cây tìm kiếm
floor(log2 n) + 1 và không bao giờ thoái hoá thành cái que.- Nó đếm phép so sánh và phép đổi chỗ, nó không đo giây. Đống nằm liền một dải trong bộ nhớ nên thường chạy nhanh hơn một cây có con trỏ với cùng số phép, nhưng chuyện đó phải đo mới biết, và trang này không đo.
- Một phép so sánh ở đây là một lần đối chiếu hai chiều. Một bước chìm xuống của nút có hai con tốn hai phép: chọn con tốt hơn, rồi so con đó với nút. Sách đếm kiểu khác sẽ ra con số khác. Một phép đổi chỗ là một lần hoán vị hai ô; code thật thường giữ giá trị đang di chuyển trong thanh ghi và chỉ ghi mỗi ô một lần, tức khoảng một nửa số lần ghi. Đây là quy ước, không phải chân lý.
- Bảng bậc tăng ở mục 5 chỉ nói về số phép trên hai họ mảng cụ thể: mảng giảm dần và các hoán vị sinh bằng hạt giống. Nó không chứng minh cận trên tiệm cận cho mọi dữ liệu. Hai cột trần thì ngược lại: đó là cận trên chứng minh được, và mảng giảm dần chạm đúng trần của cách chèn.
- Ở cỡ nhỏ, khoảng cách trung bình giữa hai cách rất khiêm tốn, và cách chèn thậm chí có thể thắng trên một mảng may mắn. Bảng trên để bạn tự kiểm chứng điều đó thay vì tin lời hứa. Chênh lệch về bậc chỉ hiện rõ ở ca xấu nhất và ở n lớn.
- Sắp xếp bằng đống ở đây dựng đống lớn nhất để đầu ra tăng dần. Dùng đống nhỏ nhất thì đầu ra giảm dần, và mọi con số đếm được y hệt. Đó là hai bản đối xứng gương, không phải hai thuật toán.
Ở trạng thái mở đầu, sim đang nói gì
Mảng vào là 15 giá trị, xếp lộn xộn:
140 110 80 130 100 20 60 150 120 70 90 50 40 30 10
Cách dựng mặc định là dồn đống từ dưới lên, và nó cho ra đống nhỏ nhất này:
10 70 20 120 90 40 30 150 130 100 110 50 140 80 60
Đống có 15 ô, chiều cao 4, và không một con trỏ nào. Toàn bộ bộ nhớ nó dùng là đúng 15 ô mảng đó. Ô đang được soi sẵn là ô 4, giữ giá trị 90: nó nằm ở tầng 3, cha của nó là ô 1, hai con của nó là ô 9 và ô 10. Bạn bấm sang ô khác thì cả hai hình cùng sáng lên ở đúng một chỗ.
Ba phép tính thay cho mọi con trỏ
Đây là ý đắt nhất của bài, và cũng là chỗ hầu hết sinh viên không nối được hai hình ảnh lại với nhau. Trong một cây thường, muốn đi từ nút xuống con thì phải đọc một con trỏ đã lưu sẵn. Trong đống thì không có con trỏ nào để đọc, vì vị trí của mọi nút đã bị ép cứng bởi luật "đầy từ trái sang phải". Ép cứng rồi thì tính ra được:
| muốn đi đâu | công thức | ví dụ với ô 4 |
|---|---|---|
| xuống con trái | 2i + 1 | 2×4+1 = 9 |
| xuống con phải | 2i + 2 | 2×4+2 = 10 |
| lên cha | floor((i - 1) / 2) | floor(3/2) = 1 |
| nút này ở tầng nào | floor(log2(i+1)) + 1 | floor(log2 5)+1 = 3 |
Cổng kiểm số của bài không tin ba công thức này, nó đi ngược lại: với mọi ô từ 1 tới 4096 nó tính cha rồi hỏi ngược "ô đó có phải một trong hai con của cha không", và với mọi ô từ 0 tới 2047 nó tính hai con rồi hỏi ngược "cha của chúng có đúng là ô này không". Hai vòng lặp đó đóng kín trên toàn bộ dải. Tầng của mỗi ô còn được tính một đường thứ ba nữa, bằng cách đếm số lần leo lên cha cho tới khi chạm gốc, một cách nói không nhắc tới logarit, và hai con số phải khớp trên cả 4097 ô.
Ô 0 là gốc, và floor((0-1)/2) ra số âm. Đó không phải lỗi, đó chính là cách code thật biết mình đã lên tới đỉnh và phải dừng.
Chèn thì nổi lên, lấy ra thì chìm xuống
Chỉ có hai thao tác, và cả hai đều là một đường đi thẳng dọc theo một nhánh.
Chèn một giá trị mới: đặt nó vào ô trống kế tiếp ở cuối mảng, rồi so nó với cha. Nếu nó nhỏ hơn cha thì đổi chỗ, rồi so tiếp với cha mới, cứ thế cho tới khi cha không còn lớn hơn nó, hoặc tới khi nó thành gốc.
Trên đống mặc định, gõ 5 rồi bấm chèn: 5 nhỏ hơn mọi giá trị đang có nên nó leo trọn bốn tầng, tốn 4 phép so sánh và 4 phép đổi chỗ, và trở thành gốc mới. Bây giờ gõ 200: nó lớn hơn cha ngay từ lần so đầu tiên nên nằm im tại ô vừa rơi vào, tốn 1 phép so sánh và 0 phép đổi chỗ. Cùng một thao tác, cùng một đống, hai hoá đơn khác hẳn nhau, và cái quyết định là giá trị chứ không phải kích thước.
Lấy phần tử nhỏ nhất ra thì khó hơn một chút, vì cái bị lấy đi là gốc, tức là cái ô mà mọi thứ khác treo vào. Không thể để lại một lỗ ở giữa mảng, vì lỗ đó sẽ phá luật "đầy từ trái sang phải" và ba công thức chỉ số ở trên sẽ sai ngay lập tức. Cách làm là: đổi chỗ gốc với ô cuối, cắt ô cuối ra, rồi cho kẻ vừa bị đẩy lên gốc chìm xuống cho tới khi hai con của nó không còn nhỏ hơn nó.
Bấm lấy ra một lần trên đống mặc định: nó trả về 10, đưa 60 lên gốc, và cho 60 chìm xuống ô 6. Chi phí là 5 phép so sánh và 3 phép đổi chỗ, trong đó một phép đổi chỗ là cú hoán vị gốc với ô cuối.
Một chuyện phải nói rõ vì mọi con số ở đây phụ thuộc vào nó. Một phép so sánh trong bài là một lần đối chiếu hai chiều giữa hai giá trị. Một bước chìm xuống của nút có hai con tốn hai phép so sánh: một để chọn con nào tốt hơn, một để so con đó với chính nút. Nút chỉ có con trái thì bước đó chỉ tốn một. Còn một bước nổi lên thì luôn tốn đúng một. Đây là quy ước, không phải chân lý, và sách đếm kiểu khác sẽ in ra con số khác.
Mốc biên, và cái mà một hàng đợi rỗng phải làm
Bốn ca dưới đây là chỗ code thật hay hỏng nhất, và sim cho bạn bấm thử hết.
- Đống rỗng. Bấm bộ đống rỗng rồi bấm lấy phần tử nhỏ nhất. Nó không nổ, và cũng không âm thầm trả về 0. Nó từ chối, và nói ra lý do. Đây là điểm phân biệt một cài đặt dùng được với một cài đặt sẽ giết bạn lúc 3 giờ sáng: một hàng đợi rỗng là chuyện hết sức bình thường, người gọi phải xử lý được, nên hàm phải báo chứ không được đoán.
- Một phần tử. Lấy ra thành công, trả về đúng giá trị đó, tốn 0 phép so sánh và 0 phép đổi chỗ, và để lại đống rỗng. Không có cú hoán vị nào ở đây, vì không có ô nào khác để hoán vị cùng.
- Mọi giá trị bằng nhau. Bấm bộ toàn phần tử bằng nhau. Cả hai cách dựng đều tốn 14 phép so sánh và 0 phép đổi chỗ. Không đổi chỗ lần nào là vì luật đống đòi "không nhỏ hơn cha", chứ không đòi "lớn hơn hẳn cha", nên một mảng toàn giá trị bằng nhau đã là một đống hợp lệ. Nhưng số phép so sánh vẫn khác 0, vì phải nhìn mới biết là không phải làm gì.
- Chèn rồi lấy ra ngay. Chèn 5 rồi lấy ra thì 5 quay lại ngay, và ở đây đống thu được trùng khít cái cũ tới từng ô. Nhưng đó là vì 5 nhỏ hơn mọi giá trị đang có nên nó chưa kịp làm xáo trộn gì. Đổi sang chèn 15 rồi lấy ra: đống trả về đúng 10, còn mảng thì thành
15 70 20 120 90 40 30 150 130 100 110 50 140 80 60, tức khác cái cũ ở ô 0. Chèn rồi lấy ra không phải phép đồng nhất, vì đường nổi lên và đường chìm xuống đi qua những ô khác nhau.
Hai cách dựng đống, và chúng khác nhau về bậc
Đây là điểm dạy học chính của bài. Bạn có sẵn một mảng và muốn biến nó thành đống. Có hai cách, cả hai đều đúng, và chúng không cùng một bậc.
Cách thứ nhất, chèn lần lượt. Bắt đầu từ đống rỗng và chèn từng giá trị vào, mỗi lần một phép nổi lên. Đơn giản, và bạn được một đống hợp lệ ở mọi thời điểm giữa chừng, không chỉ ở cuối.
Cách thứ hai, dồn đống từ dưới lên, thường gọi theo tên Floyd. Giữ nguyên mảng tại chỗ, chạy ngược từ nút trong cuối cùng về gốc, mỗi nút cho chìm xuống đúng một lần. Chạy ngược là điều làm cho nó đúng: tới lượt ô i thì hai cây con dưới nó đã là đống rồi, nên một phép chìm là đủ.
Với 15 giá trị, cách một có 15 bước còn cách hai chỉ có 7 bước, vì tám ô cuối đều là lá và lá thì không có gì để chìm. Đó là nửa số phần tử được miễn phí ngay từ đầu.
Trên đúng mảng mặc định, sim đo được:
| trên đúng 15 giá trị đó | chèn lần lượt | dồn đống từ dưới lên |
|---|---|---|
| số bước | 15 | 7 |
| phép so sánh | 30 | 22 |
| phép đổi chỗ | 20 | 10 |
Đúng một nửa số phép đổi chỗ. Và có một chi tiết đáng dừng lại: hai cách cho ra hai mảng khác nhau, cả hai đều là đống nhỏ nhất hợp lệ. Đống không phải một đối tượng duy nhất ứng với một tập giá trị. Nó chỉ hứa mỗi ô đứng đúng phía so với cha, và có rất nhiều mảng thoả điều đó.
Cùng một mảng, n gấp đôi, khoảng cách nới ra
Mảng mặc định chỉ là một mảng. Muốn nói về bậc thì phải quét. Bảng tăng trưởng trong sim chạy thật cả hai thuật toán trên mảng giảm dần dài tới 255 phần tử, chỉ là không vẽ ra vì không đủ chỗ. Mảng giảm dần là ca xấu nhất của cách chèn khi dựng đống nhỏ nhất: mỗi giá trị mới đều nhỏ hơn mọi giá trị đã có, nên nó leo thẳng lên gốc, không lần nào được dừng sớm.
| n trên mảng giảm dần | chèn, so sánh | dồn, so sánh | chèn, đổi chỗ | dồn, đổi chỗ |
|---|---|---|---|---|
| 15 | 34 | 22 | 34 | 11 |
| 31 | 98 | 52 | 98 | 26 |
| 63 | 258 | 114 | 258 | 57 |
| 127 | 642 | 240 | 642 | 120 |
| 255 | 1538 | 494 | 1538 | 247 |
Với n = 15 khoảng cách là 12 phép so sánh và 23 phép đổi chỗ. Với n = 31, gấp đôi số phần tử, khoảng cách thành 46 phép so sánh và 72 phép đổi chỗ. Tỉ lệ phép đổi chỗ đi từ 3,09 lên 3,77 lần, và tới dòng 255 thì thành 6,23 lần. Cổng kiểm số khẳng định tỉ lệ ấy tăng ở từng dòng một của bảng, chứ không chỉ tăng giữa hai đầu.
Vì sao nửa số phần tử được miễn phí
Con số không tự nhiên mà có. Cả hai cách đều có một trần chứng minh được, và hai cái trần đó khác bậc.
Trần của cách chèn. Giá trị thứ k rơi vào ô k - 1, mà ô đó nằm ở tầng floor(log2 k) + 1, nên nó leo được nhiều nhất floor(log2 k) bậc. Cộng lại trên cả n giá trị:
trần chèn = floor(log2 1) + floor(log2 2) + ... + floor(log2 n)
Với n = 15 ra 34, với n = 31 ra 98, với n = 255 ra 1538. Đại lượng này lớn cỡ n log n.
Trần của cách dồn. Ô i chìm xuống nhiều nhất bằng chiều cao của chính nó, và mỗi bậc tốn nhiều nhất hai phép so sánh.
Ở đây có một chỗ đổi quy ước phải nói ra, vì con số dưới đây sống chết vì nó. Chiều cao của cả đống đếm bằng số tầng, nên 15 ô cho chiều cao 4. Còn chiều cao của một ô trong đoạn này đếm bằng số bậc nó chìm được, nên một lá cao 0. Hai bài cây trước đếm chiều cao một nút bằng số nút, tức lá cao 1; nếu bê lối đếm ấy vào đây thì tổng sẽ ra 26 chứ không phải 11, và công thức ngay dưới sẽ sai.
Tổng chiều cao của mọi ô trong một cây đầy n nút có một công thức gọn bất ngờ:
tổng chiều cao = n - (số bit 1 trong biểu diễn nhị phân của n)
Với n = 15 thì 15 - 4 = 11. Với n = 31 thì 31 - 5 = 26. Với n = 255 thì 255 - 8 = 247. Con số này luôn nhỏ hơn n, tức là tuyến tính. Lý do trực giác thì đã nằm sẵn trong hình vẽ: một nửa số ô là lá, chiều cao 0, không tốn gì; một phần tư ở tầng kế, chìm được nhiều nhất một bậc; chỉ đúng một ô, cái gốc, mới chìm được trọn chiều cao. Cách chèn thì ngược hẳn, nó bắt một nửa số phần tử phải leo từ tầng đáy, tức tầng đắt nhất.
Tỉ lệ giữa hai cái trần thì tuỳ bạn so khoản nào, nên phải nói rõ. So hai trần phép so sánh, tức 34 với 22 vì mỗi bậc chìm tốn nhiều nhất hai phép so sánh: 1,55 lần ở n = 15, 1,88 ở n = 31, và 3,11 ở n = 255. So hai trần phép đổi chỗ, tức 34 với 11, thì tỉ lệ là 3,09, 3,77 và 6,23, đúng ba con số đã gặp ở bảng trên. Cổng kiểm số làm hai việc với hai cái trần này: nó quét toàn bộ lưới mảng của bài và khẳng định không lần chạy nào vượt trần, rồi nó chỉ ra mảng giảm dần chạm đúng trần của cả hai cách, ở n bằng 3, 7, 15, 31 và 63. Một cận trên không ai chạm tới thì không chứng minh được điều gì cả.
Nói cho công bằng: ở cỡ nhỏ thì chênh lệch rất khiêm tốn
Bảng trên là ca xấu nhất. Trên mảng bình thường thì câu chuyện nhạt hơn nhiều, và bài này không giấu điều đó.
Lấy trung bình trên 64 hoán vị sinh bằng bộ sinh có hạt giống, với n = 15: chèn lần lượt tốn 23,44 phép so sánh, dồn đống tốn 21,06. Chênh chưa tới hai phép rưỡi. Ở n = 255 thì thành 551,13 so với 464,78, tức tỉ lệ chỉ 1,19 lần, trong khi tỉ lệ phép đổi chỗ ở đó là 1,65 lần.
Còn mạnh hơn nữa: trên 400 hạt giống với n = 15, cách chèn thắng cách dồn về số phép so sánh ở 68 lần. Không phải hiếm, mà là một phần sáu.
Vậy câu đúng là gì? Không phải "dồn đống luôn ít phép hơn". Câu đúng là: trần của hai cách khác bậc, một cái tuyến tính và một cái cỡ n log n, và khoảng cách đó chỉ hiện ra rõ ở ca xấu và ở n lớn. Ở n = 15 thì hằng số quyết định nhiều hơn bậc, và đó là bài học chung về bậc tăng chứ không riêng gì đống.
Sắp xếp bằng đống
Nếu lấy phần tử nhỏ nhất ra là rẻ, thì lấy hết ra là một phép sắp xếp. Bản thường dùng lật ngược lại một chút: dựng đống lớn nhất rồi liên tục đổi gốc xuống cuối và thu vùng sống lại một ô, thế là đầu ra tăng dần. Dùng đống nhỏ nhất thì đầu ra giảm dần: vẫn một thuật toán soi gương chứ không phải hai.
Trên mảng mặc định, sim đo được 70 phép so sánh và 46 phép đổi chỗ, chia ra 18 và 5 cho pha dựng đống, 52 và 41 cho pha rút ra.
Chỗ đáng giá nằm ở con số thứ ba: 0 ô nhớ phụ. Cái đuôi đã sắp lớn lên ngay trong mảng mà đống đang co lại, nên không có mảng thứ hai nào được cấp phát. Đây là điểm nó khác sắp xếp trộn, thứ phải xin thêm một vùng đệm lớn theo n. Với dữ liệu vừa đủ chật bộ nhớ thì khác biệt ấy không phải chuyện thẩm mỹ.
Còn một chuyện phải nói cho khỏi hiểu sai chữ "soi gương": đừng chờ tấm gương khít trên cùng một mảng. Chạy đúng thuật toán ấy bằng đống nhỏ nhất trên chính mảng mặc định này tốn 70 phép so sánh và 49 phép đổi chỗ, tức lệch ba phép đổi chỗ so với 70 và 46 ở trên, và trên 200 mảng 15 phần tử xáo ngẫu nhiên thì không mảng nào cho hai hoá đơn bằng nhau. Lý do: đổi loại đống mới chỉ soi gương cái luật, chưa soi gương cái dữ liệu. Đảo dấu cả 15 giá trị rồi chạy bản đống lớn nhất thì mới ra đúng 70 và 49.
Nhưng nó không ổn định
Một phép sắp xếp ổn định giữ nguyên thứ tự cũ của hai bản ghi có khoá bằng nhau. Chuyện này quan trọng khi bạn sắp nhiều lần: sắp theo tên trước, rồi sắp theo lớp, thì trong mỗi lớp tên vẫn còn đúng thứ tự nếu phép sắp thứ hai ổn định.
Sắp xếp bằng đống không giữ, và phản ví dụ nhỏ tới mức gần như không tin được:
vào 50a 50b 30c
đống trả về 30c 50b 50a
ổn định phải ra 30c 50a 50b
Ở vị trí 1 hai đầu ra đã khác nhau. Chú ý là đống không sắp sai: đầu ra vẫn là 30, 50, 50 đúng thứ tự giá trị. Chỉ có thứ tự giữa hai bản ghi bằng nhau là bị lật.
Thủ phạm không phải phép so sánh, vì một thế hoà thì không làm gì cả. Thủ phạm là bước đổi gốc xuống cuối, bước đó hoán vị vô điều kiện. Bằng chứng: chỉ cần đúng hai bản ghi bằng nhau là đủ, 7a 7b đi vào và 7b 7a đi ra, không có phép so sánh nào kịp xảy ra trước đó.
Đống không phải cây tìm kiếm
Người học hay lẫn hai thứ này, vì cả hai đều là cây nhị phân và đều vẽ giống nhau. Cách bóc ra nhanh nhất là duyệt giữa chúng. Trên cây tìm kiếm nhị phân, duyệt giữa luôn cho dãy đã sắp, và đó là tính chất định nghĩa của nó. Trên đống mặc định thì duyệt giữa cho ra:
150 120 130 70 100 90 110 10 50 40 140 20 80 30 60
Không sắp gì cả. Và chi tiết đắt nhất nằm ở chỗ này: giá trị nhỏ nhất là 10, nhưng trong dãy trên nó đứng ở vị trí thứ 7, tức giữa dãy. Trên cây tìm kiếm thì khoá nhỏ nhất luôn là phần tử đầu tiên của dãy duyệt giữa. Gốc của đống nằm giữa dãy duyệt giữa, gốc của cây tìm kiếm nằm đúng chỗ nó phải nằm theo thứ tự. Hai cấu trúc, hai lời hứa khác nhau.
Nói cho chính xác thì mệnh đề đúng là "không bảo đảm ra dãy đã sắp", chứ không phải "không bao giờ". Bấm bộ toàn phần tử bằng nhau mà xem: duyệt giữa của nó là mười lăm số 42, và dãy đó thì không giảm ở đâu cả. Cổng kiểm số khoá cả hai vế, và đo luôn: trên lưới 259 mảng từ 4 phần tử trở lên mà nó quét, đúng 37 đống có duyệt giữa không giảm, và cả 37 đều là mảng toàn giá trị bằng nhau. Trong 222 mảng còn lại, kể cả các mảng tăng dần, không có mảng nào cho ra dãy đã sắp.
Đổi lại, đống có thứ mà cây tìm kiếm không có. Cây tìm kiếm nhớ thứ tự khoá đi vào, nên 15 khoá chèn theo thứ tự đã sắp cho một cái que cao 15 tầng. Đống thì không nhớ gì cả: hình dạng của nó bị ép cứng bởi số phần tử, nên 15 phần tử luôn cho chiều cao 4, dù mảng vào là gì. Cùng công thức floor(log2 n) + 1 mà bài cây tìm kiếm gọi là sàn, ở đây là giá trị duy nhất. Không có gì để cân bằng, vì không có gì lệch được.
Sim này đếm gì và không đếm gì
Nó đếm phép so sánh và phép đổi chỗ, nó không đo giây. Đống nằm liền một dải trong bộ nhớ nên thường chạy nhanh hơn một cây có con trỏ với cùng số phép, vì bộ nhớ đệm của máy nạp sẵn cả dải. Nhưng chuyện đó phải đo mới biết, và trang này không đo.
Một phép đổi chỗ là một lần hoán vị hai ô. Code thật thường giữ giá trị đang di chuyển trong thanh ghi và chỉ ghi mỗi ô một lần, tức khoảng một nửa số lần ghi so với cách đếm ở đây. Lại là một quy ước.
Bảng tăng trưởng nói về số phép trên hai họ mảng cụ thể, mảng giảm dần và các hoán vị sinh bằng hạt giống. Nó không chứng minh cận trên tiệm cận cho mọi dữ liệu. Hai cột trần thì ngược lại: đó là cận trên chứng minh được, và cổng kiểm số vừa khẳng định chúng không bị vượt trên toàn lưới, vừa chỉ ra mảng chạm đúng trần.
Cổng kiểm số canh phép tính, không canh lời khẳng định về thế giới. Nó chứng minh được rằng dựng đống từ mảng giảm dần 31 phần tử tốn 98 phép đổi chỗ theo cách chèn và 26 theo cách dồn. Còn "vì vậy cách dồn tốt hơn trong dự án của bạn" thì nó không chứng minh, vì cái đó còn phụ thuộc dữ liệu của bạn, và bạn phải đo.
Đống là một cái cây sống trong mảng: con của ô i ở 2i+1 và 2i+2, cha ở floor((i-1)/2), và số con trỏ dùng tới là 0. Vì hình dạng bị ép cứng nên chiều cao luôn là floor(log2 n) + 1, không có ca thoái hoá như cây tìm kiếm. Chèn thì nổi lên, lấy gốc ra thì đổi gốc với ô cuối rồi chìm xuống; trên đống mặc định 15 ô, lấy phần tử nhỏ nhất tốn 5 phép so sánh và 3 phép đổi chỗ. Dựng đống có hai cách và chúng khác bậc: trần của cách chèn là floor(log2 1) + ... + floor(log2 n), cỡ n log n; trần của cách dồn là n trừ số bit 1 của n, tức tuyến tính. Trên mảng giảm dần: n = 15 cho 34 so với 11 phép đổi chỗ, n = 31 cho 98 so với 26, và tỉ lệ nới từ 3,09 lên 3,77 rồi 6,23 lần ở n = 255. Nhưng ở cỡ nhỏ và trên mảng ngẫu nhiên thì chênh lệch rất khiêm tốn, cách chèn thắng ở 68 trên 400 hạt giống tại n = 15. Sắp xếp bằng đống tại chỗ (0 ô nhớ phụ, khác sắp xếp trộn) nhưng không ổn định: chỉ hai bản ghi bằng nhau, 7a 7b, là đủ để ra 7b 7a. Và đống không phải cây tìm kiếm: duyệt giữa của nó không bảo đảm ra dãy đã sắp, giá trị nhỏ nhất nằm ở giữa dãy đó chứ không ở đầu.
- 1Một đống nhị phân lưu trong mảng, ô 0 là gốc. Phần tử ở ô 4 có cha và con nằm ở đâu, và nó ở tầng mấy?
- 2Bạn dựng đống nhỏ nhất từ một mảng 31 giá trị GIẢM DẦN, một lần bằng cách chèn lần lượt và một lần bằng cách dồn đống từ dưới lên. So sánh số phép đổi chỗ.
- 3Câu nào đúng về sắp xếp bằng đống và về duyệt giữa một đống?