Độ phức tạp các thao tác Heap khoảng (Interval Heap Operations)

Hàng đợi ưu tiên hai đầu (DEPQ) hoặc heap khoảng (interval heap) có các thao tác sau:

isEmpty() - Kiểm tra DEPQ rỗng, trả về true nếu rỗng.

size() - Trả về tổng số phần tử trong DEPQ.

getMin() - Trả về phần tử có ưu tiên thấp nhất (nhỏ nhất).

getMax() - Trả về phần tử có ưu tiên cao nhất (lớn nhất).

put(z) - Chèn phần tử z vào DEPQ.

removeMin() - Xóa và trả về phần tử ưu tiên nhỏ nhất.

removeMax() - Xóa và trả về phần tử ưu tiên lớn nhất.

• isEmpty(), size(), getMin(), getMax() tốn O(1) mỗi thao tác;
• put(z), removeMin(), removeMax() tốn O(log n) mỗi thao tác;
• Khởi tạo interval heap n phần tử tốn O(n) thời gian.