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 Diện tích hình vuông, tính Chu vi hình vuông
-
Công thức tính thể tích hình chóp cụt, diện tích xung quanh và toàn phần của hình chóp cụt
-
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 diện tích hình quạt tròn
-
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 diện tích xung quanh hình nón cụt, diện tích toàn phần hình nón cụt, thể tích hình nón cụt
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
-
Tổng hợp các cách bật Bluetooth trên Windows 10/8/7
Hôm qua -
Cách sử dụng mail merge trong Word để trộn văn bản
Hôm qua -
Cách vô hiệu hóa Facebook nhưng vẫn dùng Messenger
Hôm qua -
Fake IP, phần mềm đổi IP, lướt web ẩn danh tốt nhất
Hôm qua -
Dãn hay giãn đúng chính tả? Co dãn hay Co giãn, Thư dãn hay Thư giãn mới đúng?
Hôm qua -
3 cách cố định hình ảnh trong Word, khóa di chuyển để không làm ảnh hưởng bố cục
Hôm qua -
Những câu nói hay về tình anh em xã hội, stt về tình anh em kết nghĩa càng đọc càng thấm
Hôm qua -
Cách hiện đuôi file, xem phần mở rộng file trên Windows 11/10/7/8
Hôm qua -
Một số cách sửa lỗi Start Menu trên Windows 10 ngừng hoạt động
Hôm qua 5 -
6 phần mềm chỉnh sửa ảnh miễn phí tốt nhất trên máy tính
Hôm qua 3