Cấu trúc dữ liệu Heap
Cấu trúc dữ liệu Heap là gì?
Cấu trúc dữ liệu Heap là một trường hợp đặc biệt của cấu trúc dữ liệu cây nhị phân cân bằng, trong đó khóa của nút gốc được so sánh với các con của nó và được sắp xếp một cách phù hợp. Nếu α có nút con β thì:
key(α) ≥ key(β)
Khi giá trị của nút cha lớn hơn giá trị của nút con, thì thuộc tính này tạo ra một Max Heap. Dựa trên tiêu chí này, một Heap có thể là một trong hai kiểu sau:
Với dữ liệu đầy vào → 35 33 42 10 14 19 27 44 26 31
Min-Heap: ở đây giá trị của nút gốc là nhỏ hơn hoặc bằng các giá trị của các nút con.
Max-Heap: ở đây giá trị của nút gốc là lớn hơn hoặc bằng giá trị của các nút con.
Hai cây ví dụ trên đều được xây dựng dựa trên cùng một dữ liệu đầu vào và cùng thứ tự.
Giải thuật xây dựng Max Heap
Chúng ta sẽ sử dụng cùng ví dụ trên để minh họa cách tạo một Max Heap. Phương thức để xây dựng Min Heap là tương tự.
Chúng ta sẽ suy ra một giải thuật cho Max Heap bằng việc chèn một phần tử tại một thời điểm. Tại bất cứ thời điểm nào, Heap đều phải duy trì (tuân theo) thuộc tính của nó. Trong quá trình chèn, chúng ta cũng giả sử rằng chúng ta đang chèn một nút vào trong HEAPIFIED Tree.
Bước 1: Tạo một nút mới tại vị trí cuối cùng của Heap. Bước 2: Gán giá trị mới cho nút này. Bước 3: So sánh giá trị của nút con với giá trị cha. Bước 4: Nếu giá trị của cha là nhỏ hơn con thì tráo đổi chúng. Bước 5: Lặp lại bước 3 và 4 cho tới khi vẫn duy trì thuộc tính của Heap.
Ghi chú: Trong giải thuật xây dựng Min Heap, giá trị của nút cha sẽ là nhỏ hơn giá trị của các nút con.
Để rõ hơn về giải thuật xây dựng Max Heap, chúng ta hãy nhìn vào hình minh họa động dưới đây.
Giải thuật xóa trong Max Heap
Hoạt động xóa trong Max (hoặc Min) Heap luôn luôn diễn ra tại nút gốc và để xóa giá trị Lớn nhất (hoặc Nhỏ nhất). Bạn theo dõi giải thuật và hình minh họa động dưới đây để hiểu thêm về giải thuật này.
Bước 1: Xóa nút gốc. Bước 2: Di chuyển phần tử cuối cùng có bậc thấp nhất lên nút gốc. Bước 3: So sánh giá trị của nút con này với giá trị của cha. Bước 4: Nếu giá trị của cha là nhỏ hơn của con thì tráo đổi chúng. Bước 5: Lặp lại bước 3 và 4 cho tới khi vẫn duy trì thuộc tính của Heap.
Theo Tutorialspoint
Bài trước: Cây khung (Spanning Tree) trong cấu trúc dữ liệu và giải thuật
Bài tiếp: Khái niệm cơ bản về đệ qui (Recursion)
Bạn nên đọc
-
Cách tính diện tích hình tròn và chu vi hình tròn
-
Công thức tính tỉ số thể tích các khối đa diện
-
Công thức tính đường chéo hình vuông, đường chéo hình chữ nhật
-
Trọng tâm là gì? Công thức tính trọng tâm của tam giác
-
Công thức tính diện tích hình quạt tròn
-
Công thức tính đường cao trong tam giác thường, cân, đều, vuông
Theo Nghị định 147/2024/ND-CP, bạn cần xác thực tài khoản trước khi sử dụng tính năng này. Chúng tôi sẽ gửi mã xác thực qua SMS hoặc Zalo tới số điện thoại mà bạn nhập dưới đây:


Cũ vẫn chất
-
Cách sửa lỗi VCRUNTIME140_1.dll not found, is missing trong Windows
Hôm qua 28 -
Mệnh đề GROUP BY trong SQL Server
Hôm qua -
Pick me là gì? Pick me girl, Pick me boy là gì?
Hôm qua -
Kí tự khoảng trống Liên Quân, ký tự khoảng trống Liên Quân
Hôm qua 19 -
Hướng dẫn tạo một website cho người mới bắt đầu
Hôm qua -
Điều kiện BETWEEN trong SQL Server
Hôm qua -
Cách xóa khoảng trắng và lỗi xuống dòng trong Word
Hôm qua 3 -
Những bài thơ đám cưới, thơ chúc mừng đám cưới cực hay và hài hước
Hôm qua -
Hàm SUMIFS, cách dùng hàm tính tổng nhiều điều kiện trong Excel
Hôm qua 8 -
3 cách hiển thị mật khẩu *** trên trình duyệt vô cùng đơn giản
Hôm qua