Heap min-max đối xứng (Symmetric Min-Max Heap - SMMH) được định nghĩa là cây nhị phân hoàn chỉnh (complete binary tree) trong đó mỗi nút trừ gốc có đúng một phần tử. Gốc của SMMH rỗng và tổng số nút trong SMMH là m + 1, với m là số phần tử.
Gọi y là nút bất kỳ của SMMH. Gọi elements(y) là các phần tử trong cây con gốc y nhưng trừ phần tử (nếu có) trong y. Giả sử elements(y) ≠ ∅. y thỏa mãn các tính chất sau:
- Con trái của y có phần tử nhỏ nhất trong elements(y).
- Con phải của y (nếu có) có phần tử lớn nhất trong elements(y).
Hình 1 minh họa SMMH với 12 phần tử.
Khi y là nút chứa 81, elements(y) = {7, 15, 31, 41}; con trái y có phần tử nhỏ nhất 6 trong elements(y) (sửa: 7); con phải y có phần tử lớn nhất 41 trong elements(y). Ta có thể kiểm tra mọi nút y của SMMH thỏa mãn các tính chất nêu.
Vì SMMH là cây nhị phân hoàn chỉnh, nó được lưu trữ như cấu trúc dữ liệu ngầm (implicit data structure) dùng ánh xạ tiêu chuẩn của cây nhị phân hoàn chỉnh vào mảng. Khi m = 1, phần tử nhỏ nhất và lớn nhất giống nhau và nằm trong con trái của gốc SMMH.
Khi m > 1, phần tử nhỏ nhất ở con trái gốc, lớn nhất ở con phải gốc. Do đó getMin và getMax tốn O(1).
Dễ thấy một cây nhị phân hoàn chỉnh m+1 nút với gốc rỗng và một phần tử mỗi nút khác là SMMH iff các điều kiện sau đúng:
A1 − Với mọi nút y có anh em phải (right sibling), phần tử trong y nhỏ hơn hoặc bằng phần tử trong anh em phải của y.
A2 − Với mọi nút y có ông/bà (grandparent), phần tử trong con trái của ông/bà nhỏ hơn hoặc bằng phần tử trong y.
A3 − Với mọi nút y có ông/bà, phần tử trong con phải của ông/bà lớn hơn hoặc bằng phần tử trong y.
Chú ý nếu tính chất A1 thỏa mãn tại y, thì tối đa một trong A2 và A3 có thể vi phạm tại y. Dùng tính chất A1 đến A3 ta đạt được thuật toán đơn giản để chèn và xóa phần tử. Các thuật toán này là biến đổi đơn giản của thuật toán tương ứng cho min và max heap. Độ phức tạp O(log m).
Ở đây, chỉ định thao tác chèn. Giả sử ta muốn chèn 3 vào SMMH Hình 1. Vì SMMH là cây nhị phân hoàn chỉnh, ta phải thêm nút mới vào vị trí như Hình 2; nút mới nhãn B.
Trong ví dụ, B là nút rỗng. Bây giờ 3 được chèn tại nút B.