Biên soạn: Đỗ Việt Anh (lion_it)
Email: [email protected]
Nguồn: wcipeg.com/wiki
Để đọc và hiểu được bài viết các bạn cần có kiến thức về cấu trúc cây (tree) và cây nhị phân đầy đủ (complete binary tree)
Một cấu trúc Binary Heap thỏa mãn 2 điều kiện sau:
Tính chất 1 - Binary (TC1): Là một cây nhị phân đầy đủ (complete binary tree)
Tính chất 2 - Heap (TC2) Mỗi nút (node) trên cây đều chứa một nhãn lớn hơn hoặc bằng các con của nó (nếu có) và nhỏ hơn hoặc bằng nút cha (trừ nút gốc là và nó là nút lớn nhất).
Một cấu trúc như trên được gọi là max binary heap vì nhãn ở gốc (root), tương tự ta có thể thay đổi TC 2 để có được min binary heap với nhãn ở gốc là nhỏ nhất trong cây.
Binary Heap được dùng để cài đặt priority queue (trong C++, java...) hay dùng để tăng tốc các thuật toán như Dijkstra, Prim..
priority_queue hoặc set, vì vậy việc tự cài đặt lại là không cần thiết.(Các bạn có thể vào visualgo để có thể hình dung cụ thể về các thao tác trên Heap)
Đặt là độ cao của cây. Nút gốc ở độ sâu 0, 2 nút con của gốc ở độ sâu 1, và nút sâu nhất có độ sâu là . Ở độ sâu , cây có tối đa nút, do đó tổng số nút trên cây .
Chọn vị trí để thêm nút:
Vun đống từ dưới lên (bottom-up heapify):
Độ phức tạp:
Ta chỉ có thể xóa phần tử lớn nhất hay góc của Binary Heap ra khỏi cây.
Độ phức tạp:
Trước tiên cần xác định vị trí của nút ta cần thay đổi nhãn
Thay đổi nhãn
Vun đống heap
Độ phức tạp: độ thức tạp của thao tác này bằng độ phức tạp của top-down heapify hoặc bottom-up heapify hay bằng
Một cách đơn giản ta có thể thực hiện phép thêm nút. Nhưng có một kĩ thuật hiệu quả hơn để xây dựng binary heap được gọi là bottom-up construction.
Bottom-up construction: Kỹ thuật này yêu cầu xây dựng một cây nhị phân đầy đủ trước và thực hiện top-down heapify các nút trên cây theo tứ tự giảm dần độ cao của cây (từ các nút lá lên các nút cha và tiếp tục cho đến gốc). Chứng minh kết quả của cách xây dựng là một Binary Heap không phải là khó.
Độ phức tạp:
Tại sao Binary Heap nên là một cây nhị phân đầy đủ TC1 ?
Nếu Heap không phải là một cây nhị phân mà là một cây tam phân, tứ phân, k-phân thì độ phức tạp của các thao tác sẽ thay đổi thế nào ?
TC1 cần thêm điểu kiện tập nhãn phải là một totally ordered set (2 giá trị bất kì trong tập đều có thể so sánh được và có tính chất bắc cầu trong các phép so sánh, ví dụ như tập số thực )