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ông thức tính đường cao trong tam giác thường, cân, đều, vuông
-
Công thức tính chu vi hình tam giác
-
Công thức tính diện tích hình lập phương, thể tích khối lập phương
-
Công thức tính diện tích hình Elip
-
Công thức tính thể tích khối tròn xoay và ví dụ minh họa
-
Công thức tính chiều cao hình thang: thường, vuông, cân
Cũ vẫn chất
-
Tổng hợp code Đấu Trường Nhẫn Giả mới nhất
Hôm qua -
Cách xóa vật thể trong ảnh tự động
Hôm qua -
Cách xem những người bạn đã chặn (block) trên Facebook
Hôm qua -
Cách mở và chạy cmd với quyền Admin trên Windows
Hôm qua -
Si tình là gì? Si tình khác lụy tình như thế nào?
Hôm qua -
Cách chèn dấu tích vào trong Word
Hôm qua -
Hướng dẫn tạo sự kiện trên Facebook
Hôm qua -
Code Rise Of Kingdoms mới nhất 10/2024
Hôm qua -
Cách hạn chế bạn bè trên Facebook xem bài đăng của bạn
Hôm qua -
3 cách đơn giản để reset thiết lập BIOS
Hôm qua