Một heap tối thiểu-tối đa được định nghĩa là một cây nhị phân hoàn chỉnh chứa các mức tối thiểu (hoặc chẵn) và tối đa (hoặc lẻ) xen kẽ. Các cấp độ chẵn được biểu thị như ví dụ 0, 2, 4, v.v. và các cấp độ lẻ được biểu thị là 1, 3, 5, v.v.
Trong các điểm tiếp theo, chúng tôi xem xét rằng phần tử gốc nằm ở cấp đầu tiên, tức là, 0.
Ví dụ về Min-max heap
Các tính năng của Min-max heap
- Mỗi nút trong heap tối thiểu được liên kết với một phần tử dữ liệu (thường được gọi là khóa) có giá trị được triển khai để tính toán thứ tự của nút trong heap tối thiểu.
- Phần tử gốc là phần tử tối thiểu trong heap tối thiểu.
- Một trong hai phần tử ở cấp thứ hai, là mức tối đa (hoặc lẻ), là phần tử tối đa trong đống tối thiểu-max
- Gọi y là bất kỳ nút nào trong heap tối thiểu.
- Nếu y ở cấp độ nhỏ nhất (hoặc chẵn) thì y.key là khóa nhỏ nhất trong số tất cả các khóa trong cây con có gốc y.
- Nếu y ở mức tối đa (hoặc lẻ), thì y.key là khoá cao nhất trong số tất cả các khoá trong cây con có gốc y.
- Một nút ở mức tối thiểu (tối đa) được biểu thị là nút tối thiểu (tối đa).
Một đống tối thiểu được định nghĩa là ngược lại với đống tối thiểu; trong một đống như vậy, giá trị cao nhất được lưu trữ tại gốc và giá trị nhỏ nhất được lưu trữ tại một trong các giá trị con của gốc.