Cây nhị phân hoàn chỉnh thỏa mãn tính chất heap gọi là Binary Heap.
Hai loại:
- Min Heap: nút con ≥ nút cha. Gốc nhỏ nhất.
- Max Heap: nút con ≤ nút cha. Gốc lớn nhất.
Biểu diễn mảng (chỉ số từ 0):
- Gốc: index 0
- Con trái:
2*i + 1 - Con phải:
2*i + 2 - Cha:
(i-1)/2
Ví dụ Min Heap
Cây: 1 gốc, con 4,7; cháu 6,9,10,8
Mảng: [1, 4, 7, 6, 9, 10, 8]
Ví dụ Max Heap
Cây: 11 gốc, con 8,9; cháu 6,4,5,1
Mảng: [11, 8, 9, 6, 4, 5, 1]