Giới thiệu về cấu trúc Heap bao gồm ví dụ minh họa cụ thể

Để hiểu rõ hơn về kiểu dữ liệu ở dạng bộ sưu tập, nội dung bài viết dưới đây FUNiX sẽ giới thiệu về cấu trúc Heap để bạn tham khảo và ứng dụng cho việc lập trình.

>> Khóa học lập trình cơ bản

>> Lập trình hướng đối tượng (bằng Java)

Cấu trúc Heap là một trong những cấu trúc dữ liệu quan trọng và mạnh mẽ trong lĩnh vực khoa học máy tính, đặc biệt trong các thuật toán tìm kiếm, sắp xếp, và các ứng dụng liên quan đến ưu tiên như hàng đợi ưu tiên (priority queue). Với các đặc tính đặc biệt, Heap là một cấu trúc dữ liệu giúp tối ưu hóa hiệu suất của các phép toán tìm kiếm, chèn, và xóa.

Trong bài viết này, chúng ta sẽ đi sâu vào khái niệm về cấu trúc Heap, tìm hiểu các đặc điểm cơ bản, các loại Heap và các ứng dụng của nó, cùng với các ví dụ minh họa cụ thể giúp bạn hiểu rõ hơn về cách thức hoạt động của Heap.

1. Cấu trúc và đặc điểm của Heap

Heap là một loại cây nhị phân đặc biệt, trong đó mỗi nút trong cây có một giá trị thỏa mãn điều kiện sau:

• Max-Heap: Với cây Max-Heap, giá trị của nút cha luôn lớn hơn hoặc bằng giá trị của các nút con. Điều này có nghĩa là nút có giá trị lớn nhất sẽ luôn nằm ở gốc (root) của cây.

• Min-Heap: Trong cây Min-Heap, giá trị của nút cha luôn nhỏ hơn hoặc bằng giá trị của các nút con. Nút có giá trị nhỏ nhất sẽ ở gốc của cây.

Cả Max-Heap và Min-Heap đều là cây nhị phân đầy đủ, tức là tất cả các mức của cây đều được lấp đầy ngoại trừ có thể là mức cuối cùng, và nếu có, các nút ở mức cuối cùng sẽ được lấp đầy từ trái sang phải.

Đặc điểm nổi bật của Heap:

• Tính đầy đủ của cây nhị phân: Cây Heap là một cây nhị phân đầy đủ, có nghĩa là mỗi mức của cây (trừ mức cuối) đều được lấp đầy và các nút ở mức cuối cùng được lấp đầy từ trái qua phải.

• Quy tắc Heap: Các nút trong cây thỏa mãn một trong hai điều kiện: Max-Heap hoặc Min-Heap. Điều này đảm bảo rằng cây luôn giữ được tính chất của Heap và các thao tác chèn, xóa có thể được thực hiện hiệu quả.

• Cấu trúc mảng: Một trong những đặc điểm nổi bật của Heap là có thể được lưu trữ dưới dạng một mảng một chiều. Điều này là do tính chất đầy đủ của cây nhị phân. Các nút cha và nút con có thể được tính toán thông qua chỉ số mảng:

  • Nút cha của chỉ số i: i // 2
  • Nút trái của chỉ số i: 2 * i + 1
  • Nút phải của chỉ số i: 2 * i + 2

2. Cách phép toán trên Heap

Cấu trúc Heap hỗ trợ một số phép toán cơ bản, bao gồm:

2.1. Chèn (Insert)

Quá trình chèn một phần tử vào Heap bắt đầu bằng cách thêm phần tử vào vị trí cuối cùng của cây. Sau đó, phần tử này sẽ được so sánh với cha của nó và di chuyển lên trên (hoặc gọi là “heapify-up” hoặc “sift-up”) cho đến khi tính chất của Heap được đảm bảo.

• Đối với Max-Heap, nếu phần tử mới chèn vào có giá trị lớn hơn cha của nó, chúng ta hoán đổi giá trị giữa chúng. Quá trình này được lặp lại cho đến khi cây vẫn thỏa mãn tính chất Max-Heap.

• Đối với Min-Heap, nếu phần tử mới chèn vào có giá trị nhỏ hơn cha của nó, ta hoán đổi chúng.

2.2. Xóa (Delete)

Phép toán xóa trong Heap thường được thực hiện đối với phần tử ở gốc (root), vì đây là phần tử lớn nhất trong Max-Heap hoặc nhỏ nhất trong Min-Heap.

• Để xóa phần tử gốc, ta thay thế nó bằng phần tử cuối cùng trong cây (phần tử ở vị trí cuối cùng trong mảng), sau đó “heapify-down” để đảm bảo rằng cây vẫn thỏa mãn tính chất Heap.
• Quá trình “heapify-down” này bắt đầu từ gốc và tiếp tục di chuyển xuống dưới cây, hoán đổi phần tử với nút con có giá trị lớn nhất (đối với Max-Heap) hoặc nhỏ nhất (đối với Min-Heap) cho đến khi tính chất Heap được khôi phục.

2.3. Peek

Phép toán này trả về giá trị của phần tử gốc mà không xóa nó. Đây là một thao tác rất nhanh và chỉ yêu cầu truy cập phần tử đầu tiên của mảng.

2.4. Heapify

Heapify là quá trình biến một cây nhị phân bất kỳ thành một Heap. Quá trình này có thể được thực hiện từ dưới lên trên hoặc từ trên xuống dưới. Đối với mỗi nút, ta so sánh với các nút con và hoán đổi chúng nếu cần thiết cho đến khi cây thỏa mãn tính chất Heap.

>>> Xem thêm: Giới thiệu về thuật toán Heap sort và ví dụ minh họa

3. Ví dụ minh họa về cấu trúc Heap

Ví dụ về cấu trúc Heap: Ta có một Heap chứa 7 node và giá trị các node nhựa sau: {6, 4, 5, 3, 2, 0, 1}.

Theo đó, bạn có thể dùng một mảng để chứa giá trị các node của một Heap theo cách được mô tả trong hình sau:

Heap có hai loại chính, bao gồm:

3.1. Max-Heap

Trong Max-Heap, mỗi nút có giá trị lớn hơn hoặc bằng giá trị của các nút con. Phần tử lớn nhất luôn ở gốc của cây. Max-Heap thường được sử dụng trong các thuật toán như tìm kiếm phần tử lớn nhất hoặc sắp xếp giảm dần (heap sort).

Ví dụ về Max-Heap:

Ở đây, 10 là phần tử lớn nhất, và tất cả các nút cha đều lớn hơn hoặc bằng các nút con của nó.

3.2. Min-Heap

Trong Min-Heap, mỗi nút có giá trị nhỏ hơn hoặc bằng giá trị của các nút con. Phần tử nhỏ nhất luôn ở gốc của cây. Min-Heap thường được sử dụng trong các thuật toán như tìm kiếm phần tử nhỏ nhất hoặc sắp xếp tăng dần (heap sort).

Ví dụ về Min-Heap:

Ở đây, 1 là phần tử nhỏ nhất, và tất cả các nút cha đều nhỏ hơn hoặc bằng các nút con của nó.

4. Ứng dụng của Heap

Heap được sử dụng trong nhiều thuật toán và ứng dụng trong khoa học máy tính. Một số ứng dụng phổ biến của Heap bao gồm:

4.1. Thuật toán sắp xếp Heap Sort

Heap Sort là một thuật toán sắp xếp sử dụng cấu trúc Heap để sắp xếp các phần tử. Thuật toán này hoạt động bằng cách xây dựng một Max-Heap từ mảng đầu vào, sau đó liên tục xóa phần tử gốc (phần tử lớn nhất) và tái cấu trúc Heap cho đến khi mảng được sắp xếp.

Quá trình sắp xếp Heap Sort có độ phức tạp thời gian là O(n log n), giúp sắp xếp hiệu quả hơn so với các thuật toán sắp xếp truyền thống như Selection Sort hay Insertion Sort.

4.2. Hàng đợi ưu tiên (Priority Queue)

Hàng đợi ưu tiên là một cấu trúc dữ liệu mà các phần tử được truy xuất theo thứ tự ưu tiên chứ không phải theo thứ tự vào. Heap thường được sử dụng để triển khai hàng đợi ưu tiên, với Max-Heap dùng cho việc truy xuất phần tử có giá trị cao nhất và Min-Heap dùng cho phần tử có giá trị thấp nhất.

4.3. Thuật toán Dijkstra

Trong thuật toán Dijkstra để tìm đường đi ngắn nhất, Heap được sử dụng để truy xuất điểm đến có khoảng cách ngắn nhất trong mỗi bước của thuật toán, giúp giảm thiểu thời gian tính toán.

5. Ví dụ minh họa về Heap

Giả sử ta có một mảng các phần tử sau: [4, 10, 3, 5, 1]. Chúng ta sẽ xây dựng một Max-Heap từ mảng này.

1. Bước 1: Bắt đầu từ phần tử cuối cùng không phải lá (vị trí 1, có giá trị 10), ta kiểm tra và đảm bảo rằng cây thỏa mãn tính chất Max-Heap.
2. Bước 2: Chúng ta tiếp tục kiểm tra các nút cha ở các vị trí trước đó cho đến khi toàn bộ mảng trở thành một Max-Heap.

Sau khi thực hiện quá trình Heapify, ta có cây Max-Heap sau:

6. Kết luận

Heap là một cấu trúc dữ liệu rất mạnh mẽ và hiệu quả, đặc biệt trong các ứng dụng yêu cầu truy xuất phần tử lớn nhất hoặc nhỏ nhất một cách nhanh chóng. Với tính chất của cây nhị phân đầy đủ và các phép toán như chèn, xóa, và tìm kiếm gốc có độ phức tạp thấp, Heap được sử dụng rộng rãi trong các thuật toán như sắp xếp (Heap Sort), hàng đợi ưu tiên, và các bài toán tìm kiếm đường đi ngắn nhất. Sự hiểu biết về Heap là một phần quan trọng trong việc xây dựng các thuật toán và giải quyết các bài toán tối ưu trong khoa học máy tính.

Tìm hiểu khóa học công nghệ thông tin tại FUNiX

Nguyễn Cúc