Biểu diễn mảng của đống nhị phân

Cây nhị phân hoàn chỉnh tuân theo các thuộc tính của thứ tự đống được gọi là đống nhị phân .

Dựa trên thứ tự của đống nhị phân, nó có thể có hai loại -

đống tối thiểu là đống trong đó giá trị của nút lớn hơn hoặc bằng giá trị của nút cha của nó. Nút gốc của min heap là nút nhỏ nhất.

đống tối đa là đống trong đó giá trị của nút nhỏ hơn hoặc bằng giá trị của nút cha của nó. Nút gốc của max heap là nút lớn nhất.

Các giá trị của đống nhị phân thường được biểu diễn dưới dạng mảng . Biểu diễn mảng của đống nhị phân dưới dạng -

• Chỉ mục của phần tử gốc là 0.

• Nếu i là chỉ số của nút trong mảng. Sau đó, các nút khác có liên quan đến nút được lập chỉ mục trong mảng là -

  • Con trái:(2 * i) +1

  • Con bên phải:(2 * i) +2

  • Con cái:(i-1) / 2

Sử dụng các quy tắc biểu diễn mảng ở trên, chúng ta có thể biểu diễn một đống trong mảng -

Bây giờ, các loại đống dựa trên thứ tự có thể được thảo luận ở đây

• Khối lượng tối thiểu - Nút gốc có giá trị nhỏ nhất. Giá trị của nút lớn hơn giá trị của nút mẹ.

Ví dụ -

Biểu diễn mảng -

• Khối lượng tối đa - Nút gốc có nút cực đại. Giá trị của nút nhỏ hơn giá trị của nút mẹ.

Ví dụ -

Biểu diễn mảng -