Min Heap

Giới thiệu Min Heap

Ở bài trước chúng ta đã tìm hiểu về khái niệm của heap và các loại heap. Ta có hai loại heap là max heap và min heap. Cách cài đặt và hoạt động của max heap đã được giới thiệu trong bài trước, các bạn có thể tìm đọc ở đây.

Với min heap, giá trị của node cha luôn luôn nhỏ hơn hoặc bằng giá trị của node con. Node gốc của min heap có giá trị nhỏ nhất trong cây.

Cùng xem mô tả của min heap trong hình sau:

 

Hình 1: Min heap

Trong hình trên, mỗi node đều có giá trị nhỏ hơn giá trị các node con của nó, trừ các node lá, vì các node này không có con.

Để cài đặt min heap, ta thực hiện các bước giống như những gì ta đã làm với max heap.

Trước tiên, ta cần xây dựng một hàm để duy trì các đặc tính của min heap, nếu có một số phần tử vi phạm các đặc tính đó, hàm này sẽ có nhiệm vụ điều chỉnh lại.

void min_heap(int A[], int i) {
    int smallest; /* Chỉ số của phần tử nhỏ nhất trong bộ ba: node hiện tại
                         con bên trái, và con bên phải của nó */
    int left = 2 * i; /* Vị trí của con bên trái */
    int right = 2 * i + 1; /* Vị trí của con bên phải */
    if (left <= N and A[left] < A[i]) /* N là số phần tử trong mảng, biến toàn cục */
        smallest = left;
    else
        smallest = i;
    if (right <= N and A[right] < A[smallest])
        smallest = right;
    if (smallest != i) {
        swap(A[i], A[smallest]); /* Thực hiện đổi chỗ hai phần tử nếu 
                                              giá trị của node cha lớn hơn node con */
        min_heap(A, smallest); /* Gọi đệ quy node tại vị trí mới */
    }
}

Độ phức tạp thời gian: O(logN)

Ta cùng xem xét ví dụ sau:

Giả sử ta có các phần tử của heap dược lưu trong mảng A {4, 5, 1, 6, 7, 3, 2}. Như bạn có thể thấy trong hình phía dưới, node gốc của heap đã vi phạm các đăc tính của min heap, nó có giá trị lớn hơn giá trị của node con, do vậy ta sẽ áp dụng hàm min_heap() để thiết lập lại các đặc tính này.

 

Hình 2: Ví dụ về hoạt động của hàm min_heap

Bước 1: Node gốc có giá trị lớn hơn 1 (giá trị node con của nó), ta thực hiện hàm min_heap() để đổi chỗ 4 với 1. Vị trí mới của 4 là 3.

Bước 2: Tại vị trí số 3 (vị trí mới của 4), do 4 lớn hơn giá trị node con của nó nên ta gọi đệ quy hàm min_heap() ở đây để đổi chỗ 4 cho node con có giá trị là 2 (2 là node con có giá trị nhỏ nhất trong các con của 4).

Bước 3: 4 lúc này là node lá nên hàm min_heap() không làm thay đổi thứ tự của nó. Các node khác cũng đã tuân theo đặc tính của min heap nên ta thu được min heap tại bước này.

Áp dụng hàm min_heap() tại một điểm duy nhất không đảm bảo ta sẽ thu được min heap sau một lần chạy. Ta cần thực hiện hàm min_heap tại tất cả các điểm trong cây.

Tuy vậy, cũng giống như max heap, hàm min_heap không có tác dụng ở các node lá vì các node này không có con. Nên ta sẽ thực hiện hàm min_heap tại các node con lại. Việc này được hoàn thành bởi sử dụng hàm sau:

void run_minheap(int A[]) { /* Áp dụng hàm min_heap cho tất cả các node
                                               trừ node lá */
    for (int i = N / 2; i >= 1; i--) {
        min_heap(A, i);
    }
}

Độ phức tạp: O(N), độ phức tạp được tính toán tương tự với hàm xây dựng max heap.

Ví dụ: Xét một mảng với 7 phần tử: {10, 8, 9, 7, 6, 5, 4}. Chúng ta sẽ thực hiện hàm min_heap() từ node có vị trí từ N/2 tới 1.

Ở đây, N/2 = 7/2 = 3. Node ở vị trí thứ 3 có giá trị là 9. Ta sẽ bắt đầu thực hiện hàm min_heap() từ vị trí này. Sự thay đổi trong mỗi bước thực hiện được mô tả ở hình sau:

Hình 3: Các bước thực hiện của hàm min_heap() tại tất cả các điểm

Sau khi chạy min heap ta thu được mảng như sau: {4, 6, 5, 7, 8, 10, 9}.

Bạn có thể nhận thấy, trong min heap và max heap, các node trên cùng một mức (level) không tuân theo một thứ tự sắp xếp nào. Do vậy heap chỉ thực sự hiệu quả và tối ưu khi ta chỉ cần tìm node lớn nhất hoặc nhỏ nhất trong cây.

Mã nguồn hoàn thiện chương trình chạy min heap

#include <iostream> 
using namespace std;

int N = 7; /* Số phần tử của heap */
void min_heap(int A[], int i) {
    int smallest; /* Chỉ số của phần tử nhỏ nhất trong bộ ba: node hiện tại
                         con bên trái, và con bên phải của nó */
    int left = 2 * i; /* Vị trí của con bên trái */
    int right = 2 * i + 1; /* Vị trí của con bên phải */
    if (left <= N and A[left] < A[i]) /* N là số phần tử trong mảng, biến toàn cục */
        smallest = left;
    else
        smallest = i;
    if (right <= N and A[right] < A[smallest])
        smallest = right;
    if (smallest != i) {
        swap(A[i], A[smallest]); /* Thực hiện đổi chỗ hai phần tử nếu 
                                              giá trị của node cha lớn hơn node con */
        min_heap(A, smallest); /* Gọi đệ quy node tại vị trí mới */
    }
}

void run_minheap(int A[]) { /* Áp dụng hàm min_heap cho tất cả các node
                                               trừ node lá */
    for (int i = N / 2; i >= 1; i--) {
        min_heap(A, i);
    }
}

int main() {
    int A[N+1] = {-1,10,8,9,7,6,5,4}; /* Mảng chứa 8 phần tử, với phần tử 
                                                       của heap bắt đầu từ vị trí 1 tới N
                                                       phần tử dầu tiên của mảng chỉ có tác
                                                       dụng làm lấp đầy mảng, giá trị bất kỳ */
    run_minheap(A);
    printf("\n\tGiá trị của mảng sau khi áp dụng hàm min_heap\n");
    printf("\t");
    for (int i = 0; i < N+1; i++) { /* In ra giá trị của mảng sau khi sắp xếp với 
                                                 hàm min_heap */
        printf("%d    ", A[i]);
    }

    return 0;
}

Kết quả chương trình sau khi chạy và kiểm tra tại https://www.onlinegdb.com.

Source code trên gitlab: https://gitlab.com/thevngeek/basic-data-structure/blob/master/minheap.cpp

Các ứng dụng của heap trong thực tế

Heap có thể được sử dụng hiệu quả trong các trường hợp mà ta muốn:

  1. Tìm phần tử lớn nhất hoặc nhỏ nhất trong mảng hoặc trong cây khi mà giá trị các phần tử trong mảng/cây có thể thay đổi.

  2. Sắp xếp các phần tử trong mảng/cây.

  3. Cài đặt hàng đợi ưu tiên (Priority Queue).

Bạn có thể tìm hiểu về các ứng dụng này trong các đường dẫn ở trên. Các ứng dụng này được sử dụng rất nhiều trong thực tế.

Tham khảo

  1. https://www.hackerearth.com/fr/practice/data-structures/trees/heapspriority-queues/tutorial/

  2. https://gitlab.com/thevngeek/basic-data-structure/blob/master/minheap.cpp

 

** Nếu bạn muốn viết các nội dung đặt biệt thì hãy làm theo hướng dẫn sau

Xem thêm 10 bình luận
Viết blog mới của bạn
Báo lỗi trang
Đang tải