Heap min-max (min-max heap) được định nghĩa là cây nhị phân hoàn chỉnh (complete binary tree) chứa các cấp chẵn (min/even) và lẻ (max/odd) xen kẽ. Các cấp chẵn ví dụ 0, 2, 4..., cấp lẻ 1, 3, 5...
Ta xét gốc cây ở cấp đầu tiên, tức là 0.
Ví dụ Min-max heap
Đặc điểm Heap Min-max
- Mỗi nút trong min-max heap có thành viên dữ liệu (thường gọi key) giá trị dùng để xác định thứ tự nút trong heap.
- Phần tử gốc là phần tử nhỏ nhất trong min-max heap.
- Một trong hai phần tử ở cấp hai (là cấp max/lẻ) là phần tử lớn nhất trong min-max heap.
- Gọi y là nút bất kỳ trong min-max heap.
- Nếu y ở cấp min (chẵn), thì y.key là khóa nhỏ nhất trong tất cả khóa của cây con gốc y.
- Nếu y ở cấp max (lẻ), thì y.key là khóa lớn nhất trong tất cả khóa của cây con gốc y.
- Nút ở cấp min (max) được gọi là nút min (max).
Heap max-min được định nghĩa ngược lại min-max heap; trong heap đó, giá trị lớn nhất lưu ở gốc, và giá trị nhỏ nhất lưu ở một trong các con của gốc.