- Trong interval heap, phần tử nhỏ nhất là phần tử bên trái của nút gốc. Phần tử này bị loại bỏ và trả về.
- Để lấp vị trí trống bên trái gốc, một phần tử từ nút cuối bị loại bỏ và chèn lại vào nút gốc.
- Phần tử này tiếp theo được so sánh liên tiếp với tất cả phần tử bên trái của các nút con xuống dần và quá trình kết thúc khi mọi điều kiện interval heap được thỏa mãn.
- Trường hợp phần tử bên trái trong nút trở nên lớn hơn bên phải ở bất kỳ giai đoạn nào, hai phần tử được hoán đổi và tiếp tục so sánh.
- Cuối cùng, nút gốc sẽ lại chứa phần tử nhỏ nhất ở bên trái.
Thủ tục này cũng có thể giải thích theo các cách sau:
Xóa phần tử nhỏ nhất được xử lý như sau:
- Khi interval heap rỗng, removeMin thất bại.
- Khi heap chỉ có một phần tử, trả về phần tử đó. Để lại heap rỗng.
- Khi có hơn một phần tử, điểm cuối trái của gốc được trả về. Điểm này bị loại khỏi gốc.
- Nếu gốc là nút cuối của interval heap, không làm gì thêm.
- Khi nút cuối không phải gốc, loại bỏ điểm trái p từ nút cuối. Nếu khiến nút cuối rỗng, nút cuối không còn là phần của heap.
- Điểm p lấy từ nút cuối được chèn lại vào min heap nhúng bằng cách bắt đầu từ gốc.
- Khi đi xuống, có thể cần hoán đổi p hiện tại với điểm phải r của nút đang xét để đảm bảo p ≤ r. Việc chèn lại dùng cùng chiến lược như chèn vào heap thông thường.