Heap khoảng (interval heap) giống như min-max heap nhúng (embedded) mà mỗi nút chứa hai phần tử. Nó được định nghĩa là cây nhị phân hoàn chỉnh (complete binary tree) trong đó:
- Phần tử bên trái nhỏ hơn hoặc bằng phần tử bên phải.
- Cả hai phần tử xác định một khoảng đóng (closed interval).
- Khoảng biểu diễn bởi bất kỳ nút nào trừ gốc là khoảng con (sub-interval) của nút cha.
- Các phần tử bên trái tạo thành min heap.
- Các phần tử bên phải tạo thành max heap.
Tùy thuộc vào số phần tử, hai trường hợp được phép:
- Số phần tử chẵn: Mỗi nút chứa hai phần tử a, b với a ≤ b. Mỗi nút biểu diễn khoảng [a, b].
- Số phần tử lẻ: Mỗi nút trừ nút cuối chứa hai phần tử [a, b]; nút cuối chứa một phần tử, biểu diễn khoảng [a, a] (hoặc [a, b] với a=b).
Interval heap có thể khởi tạo bằng chiến lược giống khởi tạo heap thông thường — làm việc từ đáy heap lên gốc đảm bảo mỗi cây con là interval heap. Với mỗi cây con, trước sắp xếp phần tử ở gốc; sau đó chèn lại điểm trái của gốc cây con này dùng chiến lược reinsert của removeMin, rồi chèn lại điểm phải dùng chiến lược của removeMax.