Deap được định nghĩa là một cấu trúc dữ liệu không có phần tử hoặc giá trị khóa nào ở nút gốc. Nó được hình thành bằng cách thực hiện các quy tắc sau -
- Không có phần tử nào ở nút gốc cho biết nút gốc đang trống.
- Cây con bên trái của nút tắt sẽ biểu thị đống tối thiểu.
- Cây con bên phải của deap sẽ biểu thị đống tối đa.
Do đó, tính đúng đắn của câu lệnh sau có thể được cung cấp về mặt toán học bằng cấu trúc deap -
Nếu cây con bên trái và cây con bên phải của các nút nhất định không trống và các nút tương ứng của chúng có thể được biểu diễn bằng ‘a’ và ‘b’ tương ứng, thì -
a.KeyValue <=b.KeyValue