CFSDN nhấn mạnh vào giá trị tạo ra nguồn mở và chúng tôi cam kết xây dựng nền tảng chia sẻ tài nguyên để mọi nhân viên CNTT có thể tìm thấy thế giới tuyệt vời của bạn tại đây.

Bài viết trên blog CFSDN này được tác giả sưu tầm và biên soạn để hiểu về heap nhị phân. Nếu các bạn quan tâm đến bài viết này thì nhớ like nhé.

1. Đống nhị phân là gì?

  。

Không cần phải nói “nhị phân” thì các cây chủ yếu được giới thiệu trong chương này đều là cây nhị phân. Vậy "đống" là gì?

Trong cuộc sống hàng ngày chúng ta thường nói “a đống đồ” hay “một đống đồ”.

  。

Một đống thứ.

Khi xếp đồ đạc, tất cả chúng ta đều phải có kinh nghiệm, tức là để đống đồ đạc ổn định hơn, chúng ta sẽ đặt những thứ nặng hơn và lớn hơn ở dưới, và đặt những thứ nhẹ hơn và nhỏ hơn lên trên.

Trải nghiệm này cũng có thể áp dụng được trong cây nhị phân cấu trúc dữ liệu. Chỉ là "nặng" và "lớn" được đánh giá dựa trên kích thước của giá trị nút và được so sánh giữa nút cha và nút con.

Ví dụ: nút có giá trị lớn được sử dụng làm nút con; nút có giá trị nhỏ được sử dụng làm nút cha.

Hãy lấy một ví dụ về cây nhị phân thông thường sau đây, cũng là một cây nhị phân hoàn chỉnh:

Nhìn vào đống nhị phân sau:

đống tối thiểu.

Các đặc điểm của đống nhị phân này là:

• Nó là một cây nhị phân hoàn chỉnh. Trên thực tế, đống nhị phân này được điều chỉnh và chuyển đổi từ cây nhị phân hoàn chỉnh trong hình trên;
• Giá trị của nút cha bất kỳ nhỏ hơn hoặc bằng giá trị của nút con trái và nút con phải;
• Mỗi nhánh được sắp xếp theo thứ tự tăng dần bắt đầu từ nút gốc (chẳng hạn như nhánh 1-2-3-4).

Đống nhị phân như vậy được gọi là min-heap và đỉnh của heap, nút gốc A, là giá trị nhỏ nhất của toàn bộ cây.

Tương ứng với min-heap là max-heap:

• Đống tối đa là một cây nhị phân hoàn chỉnh;
• Giá trị của bất kỳ nút cha nào của nó lớn hơn hoặc bằng giá trị của con trái và con phải;
• Mỗi nhánh được sắp xếp theo thứ tự giảm dần bắt đầu từ nút gốc.

Đỉnh của heap lớn nhất là giá trị lớn nhất của toàn bộ cây.

Chúng ta chuyển đổi cây nhị phân thông thường trong hình trên thành một đống tối đa, như minh họa bên dưới:

Đống tối đa.

2. Hoạt động của heap nhị phân

  。

2.1. Xây dựng một đống nhị phân.

Cho một cây nhị phân hoàn chỉnh, bạn điều chỉnh các nút như thế nào để xây dựng một đống nhị phân Sau đây là cây nhị phân hoàn chỉnh không có thứ tự:

Bây giờ chúng ta muốn xây dựng một đống tối thiểu. Trước tiên, hãy tìm tất cả các nút không có lá (dấu màu xanh lá cây) trong cây nhị phân hoàn chỉnh này:

Những gì chúng ta phải làm là: thực hiện điều chỉnh "chìm" đến vùng heap tối thiểu cho mỗi nút không phải lá.

Điều chỉnh "chìm" của đống tối thiểu là gì?

Đối với nút không phải là lá, nếu nút lớn hơn nút nhỏ nhất trong số các nút con của nó thì hoán đổi vị trí của cả hai, nếu không thì không cần hoán đổi. Trên biểu đồ, có vẻ như các nút không phải lá (nghĩa là các nút có giá trị lớn) "chìm" xuống một cấp. Chuyển động là tương đối. Một nút có giá trị lớn "chìm", tương đương với một nút có giá trị nhỏ "nổi".

Cần lưu ý rằng đôi khi chìm một lần là chưa đủ, chúng ta cần chìm nhiều lần để đảm bảo nút chìm xuống đáy (tức là nó không còn lớn hơn nút con của nó).

Tất cả các nút không phải là lá, bắt đầu từ nút cuối cùng, có thể được xây dựng thành một đống tối thiểu bằng cách thực hiện nhiều điều chỉnh giảm heap tối thiểu theo thứ tự từ phải sang trái và từ dưới lên trên.

Ví dụ, đối với một nút không phải lá có giá trị là 4, sau khi chìm xuống cấp 3, nó vẫn lớn hơn các nút con của nó, điều này không được tính là "chìm xuống đáy" và nó cần phải tiếp tục chìm xuống. cấp độ thứ tư. Tại thời điểm này, trên nhánh 2-4-3-1, nút 4 "giá trị lớn" đã chìm xuống đáy.

Đây là lời giải thích từng bước:

1. Đối với nút 7 không phải lá, nhỏ hơn nút con 10 của nó thì không cần phải "chìm".

2. Đối với nút 3 không phải lá, lớn hơn nút 1 lớn hơn trong số các nút con của nó, nút 3 sẽ "chìm" và được trao đổi với nút 1. Rõ ràng nút 3 đã chìm xuống đáy.

3. Đối với nút 6 không phải lá, lớn hơn nút 5 nhỏ hơn trong số các nút con của nó, nút 6 sẽ "chìm" và trao đổi vị trí với nút 5. Rõ ràng nút 6 đã chìm xuống đáy.

4. Đối với nút 4 không phải lá, lớn hơn nút 1 nhỏ nhất trong số các nút con của nó, nút 4 sẽ "chìm" và trao đổi vị trí với nút 1. Rõ ràng nút 4 chưa chìm xuống đáy.

5. Vẫn đối với nút 4, lớn hơn nút 3 nhỏ nhất trong số các nút con của nó, nút 4 sẽ "chìm" và trao đổi vị trí với nút 3. Lúc này, nút 4 được coi là đã chìm xuống đáy.

6. Đối với nút không phải lá 2, lớn hơn nút 1 nhỏ nhất trong số các nút con của nó, nút 2 sẽ "chìm" và trao đổi vị trí với nút 1. Rõ ràng nút 2 đã chìm xuống đáy.

Cho đến nay, chúng ta đã điều chỉnh và chuyển đổi một cây nhị phân hoàn chỉnh không có thứ tự thành một đống nhị phân tối thiểu. Bạn có thể kiểm tra xem tất cả các nút trong heap tối thiểu có thỏa mãn rằng giá trị của nút cha nhỏ hơn giá trị của nút con hay không. Hơn nữa, năm nhánh đều có trật tự.

Các bước để xây dựng vùng heap tối đa là tương tự nhau, nhưng việc điều chỉnh độ chìm của vùng heap tối đa là: nếu một nút nhỏ hơn nút lớn nhất trong số các nút con của nó, thì vị trí của cả hai sẽ được hoán đổi và chúng xuất hiện dưới dạng các nút không có lá ( tức là các nút có giá trị nhỏ) trên biểu đồ nhấp chuột) để "chìm" một cấp. Thông qua nhiều lần điều chỉnh chìm, nút không còn nhỏ hơn nút con của nó.

Hình dưới đây điều chỉnh cây nhị phân hoàn chỉnh không có thứ tự thành một đống tối đa:

2.2. Chèn nút.

Đống nhị phân là một cây nhị phân hoàn chỉnh. Để chèn một nút vào nó, hãy chèn nó vào vị trí tiếp theo của nút cuối cùng của cây nhị phân hoàn chỉnh.

Ví dụ: nếu nút 11 được chèn vào vùng heap tối đa sau, thì nút đó phải được chèn vào vị trí tiếp theo của nút 4 cuối cùng. Khi một nút 11 mới được chèn vào vùng heap tối đa, nó không còn là vùng heap tối đa nữa vì nút 11 phá hủy cấu trúc của vùng heap ban đầu. Vì vậy, chúng ta nên coi nó như một cây nhị phân hoàn chỉnh mới, sau đó điều chỉnh cây nhị phân hoàn chỉnh mới để xây dựng lại vùng heap tối đa. (Xem phần trên để biết quá trình điều chỉnh).

quá trình chèn.

2.3. Xóa các nút.

Thao tác xóa ngược lại với thao tác chèn, nó xóa phần tử ở vị trí đầu tiên, nghĩa là xóa phần trên cùng của heap.

Hãy lấy việc xóa 11 vùng heap lớn nhất trong hình trên làm ví dụ.

Khi top 11 của heap bị xóa, cấu trúc ban đầu của heap nhị phân bị phá hủy và nó thậm chí không phải là cây nhị phân (nó trở thành hai):

Để duy trì dạng cây nhị phân hoàn chỉnh, chúng ta thêm nút 7 cuối cùng vào nút gốc để thay thế nút gốc 11 đã bị xóa. Bằng cách này, chúng ta có được một cây nhị phân hoàn chỉnh mới (không phải một đống nhị phân) và sau đó chúng ta có thể xây dựng lại vùng heap tối đa dựa trên cây nhị phân hoàn chỉnh mới này.

Quá trình xóa.

3. Cấu trúc lưu trữ của heap nhị phân

  。

Cấu trúc lưu trữ của heap nhị phân là lưu trữ tuần tự, vì heap nhị phân là một cây nhị phân hoàn chỉnh. Trong bài viết [Lưu trữ cây nhị phân], chúng tôi đã nói rằng cây nhị phân hoàn chỉnh phù hợp để triển khai bằng cấu trúc lưu trữ tuần tự.

Hình bên dưới là vùng heap tối đa. Ô màu đỏ là số nút, tương ứng với chỉ số một-một của mảng.

  。

Lưu trữ tuần tự các đống nhị phân.

Cấu trúc lưu trữ chuỗi có thể cho chúng ta thấy rõ ràng và sinh động mối quan hệ giữa nút cha và nút con trái và phải trong heap nhị phân. Nhưng không có con trỏ trong mảng, chỉ có chỉ số mảng. Làm thế nào để thể hiện mối quan hệ giữa cha mẹ và con cái?

Trong thực tế, đối với một cây nhị phân hoàn chỉnh, chỉ số mảng là đủ.

Bây giờ giả sử rằng chỉ mục mảng của nút cha trong vùng nhớ nhị phân là parent_index, chỉ mục mảng của nút con bên trái là left_child_index và chỉ mục mảng của nút con bên phải là right_child_index, khi đó giữa chúng có mối quan hệ sau:

(一)left_child_index = 2 × parent_index + 1 。

(二)right_child_index = 2 × parent_index + 2 。

(三)chỉ số cha mẹ = (chỉ số con trái - 1) ÷ 2 。

(四)parent_index = (right_child_index - 2) ÷ 2 。

(五)chỉ số con phải = chỉ số con trái + 1 。

Ví dụ: chỉ số dưới của nút 3 là 3, chỉ số dưới của nút con bên trái 2 là 2 × 3 + 1 = 7 và chỉ số dưới của nút con bên phải 1 của nó là 2 × 3 + 2 = 8,

Chỉ số con của nút 3 là 3, và là con bên trái, chỉ số cha của nó là (3 - 1) 2 = 1; chỉ số con của nút 7 là 4, và là con bên phải, chỉ số cha của nó là (4 - 2) ) 2 = 1,

Giả sử chỉ số mảng của một nút là child_index. Bạn không biết nút đó là con trái hay con phải. Bạn cần chỉ số dưới của nút cha.

(六)parent_index = (child_index - 1) ÷ 2 。

Ví dụ: bạn không biết nút 5 (chỉ số 5) và nút 6 (chỉ số 6) là con trái hay nút con phải thì chỉ số cha của nút 5 và nút 6 lần lượt là (5 - 1) . , (6 - 1) 2 = 2. (Lưu ý rằng số học số nguyên được sử dụng trong các ngôn ngữ lập trình nên kết quả không phải là số thập phân).

Ở đây, chúng tôi sử dụng cấu trúc để triển khai vùng heap nhị phân:

1. #define MAXSIZE 20 // Dung lượng lưu trữ tối đa của mảng 
2.  
3. Kiểu định nghĩa cấu trúc { 
4.     số nguyên mảng[MAXSIZE] // lưu trữ mảng 
5.     số nguyên length; // Độ dài heap hiện tại (số nút) 
6. } Đống nhị phân; 

Trước khi thực hiện các thao tác thực tế, bạn cần khởi tạo heap nhị phân, tức là gán giá trị cho mảng và độ dài heap:

1. /** 
2.  * @description: Khởi tạo heap nhị phân 
3.  * @param {BinaryHeap} *đống nhị phân 
4.  * @tham số {số nguyên} *mảng là địa chỉ đầu tiên của mảng. Mảng là một cây nhị phân hoàn chỉnh không có thứ tự. 
5.  * @tham số {số nguyên} độ dài mảng arr_length 
6.  * @trở lại {*} không có 
7.  */ 
8. void init_heap(BinaryHeap *heap, số nguyên *mảng, số nguyên chiều dài mảng) 
9. { 
10.     // sao chép mảng vào heap 
11.     memcpy(heap->mảng, mảng, chiều dài_mảng * sizeof(số nguyên)); 
12.     //Đặt chiều dài heap 
13.     heap->chiều dài = chiều dài_mảng; 
14. } 

4. Triển khai cụ thể heap nhị phân

  。

4.1. Điều chỉnh và xây dựng.

Ở đây chúng ta lấy việc xây dựng một đống tối thiểu làm ví dụ.

Để xây dựng một đống tối thiểu, tất cả các nút không phải là lá phải được điều chỉnh. Cơ sở điều chỉnh là so sánh kích thước của các nút không phải lá và nút con của chúng.

Chúng tôi đồng ý rằng cha mẹ là nút không có lá và parent_index là chỉ số dưới của nó. child là phần tử con nhỏ hơn của nó và child_index là chỉ mục của nó.

mặc định con bắt đầu xác định con bên trái thì chỉ số dưới của con bên phải là child_index + 1. Khi con bên trái nhỏ hơn hoặc bằng con bên phải thì không cần thay đổi; khi con bên trái lớn hơn con bên phải thì phải cập nhật child_index để con đó xác định được con bên phải.

Hãy lấy nút không phải lá có giá trị 4 trong hình bên dưới làm ví dụ để mô tả cách triển khai mã.

Đầu tiên so sánh con trái và con phải của cha, nếu con bên trái nhỏ hơn thì con bên trái là con và không cần cập nhật child_index.

Cha mẹ và con ở vị trí tương ứng. Nếu cha mẹ lớn hơn con, vị trí có thể được hoán đổi. Trước khi trao đổi hãy lưu lại giá trị của cha, tức là parent_value = 4:

Hoán đổi vị trí: Đầu tiên gán giá trị của con cho cha mẹ, để đạt được hiệu ứng của giá trị nổi 1:

Sau đó cập nhật parent_index và child_index, cả hai đều giảm xuống một cấp:

Sau đó gán giá trị đã lưu trước đó cho cha mẹ hiện tại, từ đó đạt được hiệu quả làm chìm giá trị 4:

Một sự điều chỉnh đã hoàn tất, nhưng đối với giá trị 4 thì vẫn chưa kết thúc vì giá trị 4 vẫn chưa chìm xuống đáy.

So sánh con bên trái và con bên phải của cha mẹ lúc này thấy con bên phải nhỏ hơn con bên phải con là cây con bên phải và child_index cần cập nhật để con bên phải xác định được con bên phải:

Bây giờ bạn có thể hoán đổi vị trí và gán giá trị của con cho cha mẹ, tối đa giá trị là 3:

Sau đó, cập nhật giá trị của parent_index và child_index, cả hai đều giảm xuống một cấp:

Gán giá trị cho cha mẹ, đạt giá trị chìm là 4:

  。

Lúc này, child_index đã vượt quá độ dài của heap nhị phân, tức là giá trị 4 đã chạm đáy.

Mã điều chỉnh như sau:

1. /** 
2.  * @description: Thực hiện điều chỉnh độ chìm đáy cho nút không có lá 
3.  * @param {BinaryHeap} *đống nhị phân đống (không có thứ tự) 
4.  * @tham số {số nguyên} parent_index một nút không có lá 
5.  * @trở lại {*} không có 
6.  */ 
7. void điều chỉnh_cho_min_heap(BinaryHeap *heap, số nguyên parent_index) 
8. { 
9.     // value lưu giá trị của các nút không có lá 
10.     số nguyên giá trị = heap->array[parent_index]; 
11.     // child_index xác định con bên trái 
12.     số nguyên chỉ số_con = chỉ số_cha mẹ * 2 + 1; 
13.     //Chỉ số của nút cuối cùng 
14.     số nguyên last_child_index = heap->length - 1; 
15.  
16.     // Nút cha mẹ có ít nhất một nút con 
17.     trong khi (child_index <= last_child_index) { 
18.         // Nếu nút cha mẹ có con trái và con phải 
19.         nếu (child_index < last_child_index) { 
20.             // So sánh con bên trái và con bên phải nhỏ hơn. Nếu con bên phải nhỏ hơn. 
21.             nếu (heap->mảng[child_index] > heap->mảng[child_index + 1]) { 
22.                 //Sau đó child_index xác định đúng con 
23.                 chỉ số con = chỉ số con + 1; 
24.             } 
25.         } 
26.         // Nếu giá trị của cha lớn hơn giá trị của con 
27.         nếu (giá trị > heap->mảng[child_index]) { 
28.             heap->array[parent_index] = heap->array[child_index] // Các nút nhỏ nổi lên 
29.             parent_index = child_index; // Cập nhật chỉ mục cha 
30.             child_index = parent_index * 2 + 1; // Cập nhật chỉ mục con 
31.         } khác { // Không có thao tác nào, nhảy ra khỏi vòng lặp 
32.             phá vỡ; 
33.         } 
34.         // Nút lớn chìm 
35.         heap->array[parent_index] = giá trị; 
36.     } 
37. } 

Mã xây dựng như sau:

1. /** 
2.  * @description: Xây dựng một đống tối thiểu 
3.  * @param {BinaryHeap} *đống nhị phân đống (không có thứ tự) 
4.  * @trở lại {*} không có 
5.  */ 
6. void create_min_heap(BinaryHeap *heap) 
7. { 
8.     // Điều chỉnh từng nút không có lá 
9.     vì (số nguyên i = (đống->chiều dài - 2) / 2; i >= 0; i--) { 
10.         điều chỉnh_cho_đống_tối_thiểu(đống, i); 
11.     } 
12. } 

4.2. Chèn nút.

Chỉ cần chèn nút mới vào vùng nhị phân ở vị trí tiếp theo của nút cuối cùng, sau đó xây dựng lại vùng nhị phân.

Lấy heap tối thiểu làm ví dụ, mã như sau:

1. /** 
2.  * @description: Chèn một phần tử vào min-heap 
3.  * @param {BinaryHeap} *con trỏ heap tối thiểu 
4.  * @tham số {số nguyên} phần tử phần tử mới 
5.  * @trở lại {*} không có 
6.  */ 
7. void insert_into_min_heap(BinaryHeap *heap, số nguyên yếu tố) 
8. { 
9.     nếu (heap->length == MAXSIZE) { 
10.         inf("Đống nhị phân đã đầy và không thể chèn thêm được.\n"); 
11.         trở lại; 
12.     } 
13.     heap->array[heap->length] = elem; // chèn 
14.     heap->length++; // Cập nhật độ dài 
15.     create_min_heap(heap); // Xây dựng lại 
16. } 

4.3. Xóa các nút.

Di chuyển (gán) nút cuối cùng lên đầu vùng heap và sau đó xây dựng lại vùng heap nhị phân.

Lấy heap tối thiểu làm ví dụ, mã như sau:

1. /** 
2.  * @description: Xóa phần trên cùng của heap tối thiểu 
3.  * @param {BinaryHeap} *con trỏ heap tối thiểu 
4.  * @tham số {số nguyên} *elem lưu con trỏ biến 
5.  * @trở lại {*} không có 
6.  */ 
7. void delete_from_min_heap(BinaryHeap *heap, số nguyên *yếu tố) 
8. { 
9.     nếu (heap->length == 0) { 
10.         inf("Đống nhị phân trống và không có phần tử nào để xóa.\n"); 
11.         trở lại; 
12.     } 
13.     *elem = heap->mảng[0]; 
14.     heap->array[0] = heap->array[heap->length - 1] // Di chuyển lên đầu heap 
15.     đống->chiều dài--; Cập nhật độ dài 
16.     create_min_heap(heap); //Tái tạo 
17. } 

5. Tóm tắt

  。

Bản chất của việc xây dựng vùng heap tối đa là thả nổi các nút "lớn" của mỗi cây con dưới dạng nút cha và nhấn chìm các nút "nhỏ" dưới dạng nút con.

Bản chất của việc xây dựng vùng nhớ tối thiểu là thả nổi các nút "nhỏ" của mỗi cây con dưới dạng nút cha và nhấn chìm các nút "lớn" dưới dạng nút con.

Bản chất của việc chèn một nút là chèn một nút mới vào cuối đống nhị phân, phá hủy cấu trúc của đống nhị phân ban đầu, sau đó điều chỉnh cây nhị phân hoàn chỉnh mới thu được để xây dựng lại đống nhị phân.

Bản chất của việc xóa một nút là xóa phần trên cùng của heap, phá hủy cấu trúc của cây nhị phân hoàn chỉnh ban đầu, sau đó sử dụng nút cuối cùng để xây dựng lại cây nhị phân hoàn chỉnh, sau đó điều chỉnh cây nhị phân hoàn chỉnh mới thu được để xây dựng lại cây nhị phân. đống.

Tóm lại trong bốn từ: phá vỡ và sau đó xây dựng.

Đối với việc triển khai mã, mấu chốt nằm ở việc điều chỉnh các nút. Khi bạn hiểu điều này, phần còn lại sẽ đơn giản.

Trên đây là nguyên lý và các hoạt động liên quan của heap nhị phân.

Để có mã hoàn chỉnh, vui lòng truy cập GitHub[1] | Gitee[2] để lấy mã.

Tài liệu tham khảo[1]GitHub: https://github.com/xingrenguanxue/Simple-DS-and-Easy-Algo.

[2]Gitee: https://gitee.com/xingrenguanxue/Simple-DS-and-Easy-Algo 。

Địa chỉ gốc: https://mp.weixin.qq.com/s/gGTRTpIqvddJZV0VRNi3-Q.

Cuối cùng, bài viết tìm hiểu những điều về đống nhị phân này kết thúc ở đây. Nếu bạn muốn biết thêm về cách hiểu những điều về đống nhị phân, vui lòng tìm kiếm các bài viết về CFSDN hoặc tiếp tục duyệt các bài viết liên quan. Tôi hy vọng tất cả các bạn sẽ ủng hộ blog của tôi trong tương lai! .