Cộng đồng chia sẻ tri thức Lib24.vn

Cấu trúc dữ liệu Heap

Gửi bởi: Võ Thị Hường 13 tháng 2 2020 lúc 14:15:21


Mục lục
* * * * *

Heap là một trường hợp đặc biệt của cấu trúc dữ liệu cây nhị phân cân bằng trong đó khóa nút gốc được so sánh với các phần tử con của nó và được sắp xếp tương ứng. Nếu α có nút con β thì -

phím (α) ≥ phím (β)

Vì giá trị của cha mẹ lớn hơn giá trị của con, thuộc tính này tạo Max Heap . Dựa trên tiêu chí này, một đống có thể có hai loại -

For Input → 35 33 42 10 14 19 27 44 26 31

Min-Heap - Trường hợp giá trị của nút gốc nhỏ hơn hoặc bằng một trong hai con của nó.

Cấu trúc dữ liệu Heap

Max-Heap - Trường hợp giá trị của nút gốc lớn hơn hoặc bằng một trong hai con của nó.

Cấu trúc dữ liệu Heap

Cả hai cây được xây dựng bằng cách sử dụng cùng một đầu vào và thứ tự đến.

Thuật toán xây dựng Heap Max

Chúng ta sẽ sử dụng cùng một ví dụ để chứng minh Max Heap được tạo như thế nào. Quy trình tạo Min Heap tương tự nhưng chúng tôi sử dụng các giá trị tối thiểu thay vì giá trị tối đa.

Chúng ta sẽ rút ra một thuật toán cho heap tối đa bằng cách chèn một phần tử tại một thời điểm. Tại bất kỳ thời điểm nào, heap phải duy trì tài sản của mình. Trong khi chèn, chúng tôi cũng giả định rằng chúng tôi đang chèn một nút trong một cây đã được heapified.

Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

Lưu ý - Trong thuật toán xây dựng Min Heap, chúng tôi hy vọng giá trị của nút cha sẽ nhỏ hơn giá trị của nút con.

Chúng ta hãy hiểu Max Heap xây dựng bằng một minh họa hoạt hình. Chúng tôi xem xét cùng một mẫu đầu vào mà chúng tôi đã sử dụng trước đó.

Cấu trúc dữ liệu Heap

Thuật toán xóa heap tối đa

Hãy để chúng tôi rút ra một thuật toán để xóa từ heap tối đa. Xóa trong Heap tối đa (hoặc tối thiểu) luôn xảy ra ở gốc để xóa giá trị Tối đa (hoặc tối thiểu).

Step 1 − Remove root node.
Step 2 − Move the last element of last level to root.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.
Cấu trúc dữ liệu Heap

Được cập nhật: hôm kia lúc 23:53:51 | Lượt xem: 893