Cấu trúc dữ liệu đống
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 của nút gốc được so sánh với các nút con của nó và được sắp xếp cho phù hợp. Nếuα có nút con β sau đó -
phím (α) ≥ phím (β)
Vì giá trị của cha lớn hơn giá trị của con, thuộc tính này tạo ra 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 nút con của nó.
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 nút con của nó.
Cả hai cây đều đượ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 đống tối đa
Chúng ta sẽ sử dụng cùng một ví dụ để chứng minh cách tạo Max Heap. Thủ tục tạo Min Heap cũng tương tự nhưng chúng ta chọn giá trị min thay vì giá trị max.
Chúng tôi sẽ tìm ra một thuật toán cho đống 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 nó. 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 xếp sẵn.
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.
Note - Trong thuật toán xây dựng Min Heap, chúng ta mong muốn giá trị của nút cha nhỏ hơn giá trị của nút con.
Hãy hiểu cách xây dựng Max Heap bằng một minh họa động. 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 đó.
Thuật toán xóa đống tối đa
Hãy để chúng tôi suy ra một thuật toán để xóa khỏi đống tối đa. Xóa trong đống Max (hoặc Min) luôn xảy ra ở gốc để loại bỏ giá trị Tối đa (hoặc nhỏ nhất).
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.