Heap

Max Heap

typescripttypescript

1        60
2       /  \
3      50   40
4     / \   / \
5    30 20 15 10

Định nghĩa

Max heap là một dạng cấu trúc dữ liệu cây nhị phân hoàn chỉnh, trong đó giá tị của mỗi nút cha luôn lớn hơn hoặc bằng giá trị của các nút con.

Đặc điểm chính của max heap bao gồm

Tính chất max heap: Giá trị root node là lớn nhất trong tree. Tương tự, giá trị của bất kỳ parent_node nào cũng lớn hơn hoặc bằng giá trị của các child_node trực tiếp của nó

Cây nhị phân hoàn chỉnh: Max heap luôn là một cây nhị phân đầy đủ, nghĩa là tất cả các mức đều được lắp đầu ngoại trừ mức cuối cùng, và các nút ở mức cuối cùng được lấp từ trái sang phải

Approach xây dựng Max Heap

Quá trình xây dựng Max-heap từ một mảng dữ liệu bao gồm của bước sau:

Bắt đầu từ node không phải leaf cuối cùng (vị trí n/2)

Áp dụng thuật toán “Heapify” để đảm bảo tính chất max heap

So sánh giá trị của parent_node với các child_node

Nếu giá trị parent_node < Max(child_node), hoán đổi chúng

Lặp lại quá trình này cho đến khi toàn bộ cây thỏa mãn tính chất Max Heap

Time & Space complexity

Build Max Heap: O(n) - do áp dụng Heapify từ dưới lên

Chèn hoặc xóa phần tử: O(logn), vì chỉ cần điều chỉnh lại cây trên đường đi từ một node đến root.

Min Heap

typescripttypescript

1        10
2       /  \
3      15   20
4     / \   / \
5    30 40 50 60

Định nghĩa

Là một dạng cấu trúc dữ liệu cây nhị phân hoàn chỉnh, trong đó giá trị của mỗi parent_node ≤ child_node.

Min-heap có một số đặc điểm chính như sau:

Tính chất min Heap

Giá trị của root_node là nhỏ nhất trong toàn bộ cây

Giá trị của bất kỳ parent_node nào cũng ≤ child_node trực tiếp của nó

Cây nhị phân hoàn chỉnh

Min heap luôn là một cây nhị phân đầy đủ, nghĩa là tất cả các tầng đều được lấp đầy ngoại trừ tầng cuối cùng, và các nút ở tầng cuối được lấp từ trái qua phải

Approach building Min Heap

Quá trình xây dựng Min Heap từ một mảng dữ liệu bao gồm:

Bắt đầu từ node không phải là leaf node (vị trí n/2)

Áp dụng thuật toán “Heapify” để đảm bảo tính chất Min Heap tại mỗi node:

So sánh giá trị parent_node với các child_node

Nếu giá trị root_node > Min(child_node) hoán đổi chúng

Lặp lại quá trình này cho đến khi toàn bộ cây thỏa mãn tính chất MinHeap

Time and space complexity

Xây dựng Min Heap: O(n) - Do áp dụng “Heapify” từ dưới lên

Chèn hoặc xóa phần tử: O(logn), vì chỉ cần điều chỉnh lại cây trên đường đi từ một node đến root

Loading content...

Max Heap

Min Heap

Related Posts

Related Posts

Max Heap

Min Heap

Heap

Max Heap

Min Heap

Related Posts

Trie

Tree

Merge Sort

Prim

Selection Sort

Tree

Linked List

Binary Search

Knapsack 0/1 Problem

Insertion sort

JS/TS

Notes - Queue (Hàng đợi) - FIFO

Graph

Binary Search Tree

Prefix sum

Related Posts

Trie

Tree

Merge Sort

Prim

Selection Sort

Tree

Linked List

Binary Search

Knapsack 0/1 Problem

Insertion sort

JS/TS

Notes - Queue (Hàng đợi) - FIFO

Graph

Binary Search Tree

Prefix sum

Max Heap

Min Heap