Uncategorized

Giới thiệu về Heap, max heap

Đã đăng trên bởi Vimentor

Giới thiệu về Heap

Heap là loại cấu trúc dữ liệu dạng cây, và tất cả các node trong cây đó được sắp xếp theo một thứ tự nhất định, có thể là theo chiều tăng dần hoặc giảm dần.

Giả sử ta có A là node cha của B, tuân theo định nghĩa về heap, nếu giá trị của node A lớn hơn giá trị của node B thì quan hệ này cũng được áp dụng cho toàn bộ cây. Có nghĩa là giá trị của node B sẽ lớn hơn giá trị của node con của nó và cứ như vậy, thứ tự này được áp dụng cho toàn bộ cây.

Số con tối đa của một node trong heap phụ thuộc vào từng loại heap. Trong thực tế ta có nhiều loại heap nhưng loại được dùng phổ biến nhất là heap nhị phân.

Nếu heap nhị phân là một cây nhị phân hoàn thiện với N node. Thì chiều cao của nó sẽ là nhỏ nhất trong các cây nhị phân có N node và ta có chiều cao của nó là:

 (H = log _{2}(N+1) -1)

Để tìm hiểu rõ hơn, các bạn có thể tìm đọc lại bài học về cây nhị phân ở đây.

Hình 1: Heap nhị phân hoàn thiện

Có thể thấy rằng trong hình trên các node trong cây đều có giá trị tuân theo một quy luật, đó là giá trị của node cha luôn luôn lớn hơn giá trị của node con.

Giả sử ta có một heap có 7 node và giá trị các node là: {6, 4, 5, 3, 2, 0, 1}.

Ta 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:

Ta có thể thấy nếu ta lưu một phần tử của heap ở vị trí có chỉ số i trong mảng A thì:

Node cha của nó sẽ được lưu ở vị trí có chỉ số là i/2, trừ khi node đó là root, vì root không có cha.

Node con bên trái của nó sẽ được lưu ở vị trí có chỉ số là i*2, node con bên phải được lưu ở vị trí i*2 + 1.

Node root luôn được lưu ở vị trí có chỉ số là 1.

Các node trong heap có thể được sắp xếp theo thứ tự tăng dần hoặc giảm dần nên ta có hai loại heap, đo là max heap và min heap.

Sau đây chúng ta cùng đi vào tìm hiểu chi tiết cách thức cài đặt và hoạt động của từng loại heap.

Max Heap

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

Cài đặt max heap

Giả sử rằng ta có một heap và các phần tử của chúng được lưu trong mảng A. Chúng ta có thể dùng mảng để lưu các node của heap, do vậy ta cũng có thể chuyển đổi ngược lại từ một mảng thành heap.

Ta có thể chuyển đổi một mảng thành max heap hoặc min heap. Sau đây ta cùng xét các bước để chuyển một mảng (có các phần tử dữ liệu được sắp xếp theo một thứ tự bất kỳ) thành max heap.

  • Lấy một phần tử từ mảng.
  • Kiểm tra xem con bên trái của nó có phải max heap không.
  • Kiểm tra xem con bên phải của nó có phải max heap không.
  • Kiểm tra xem chính node đó có phải max heap không.

Để thực hiện được các bước trên, ta có thể viết một hàm để duy trì những thuộc tính của max heap.

 void max_heap (int A[ ], int i)
    {
        int largest;
        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 */
              largest = left;
        else
             largest = i;
        if(right <= N and A[right] > A[largest] )
            largest = right;
        if(largest != i )
        {
            swap (A[i] , A[largest]);
            max_heap (A, largest);
        } 
     }

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

Ta cùng mô phỏng hoạt động của hàm trên bằng ví dụ dưới đây:

Giả sử ta có một cây nhị phân như sau, cây này chưa phải là max heap.

Hình 2: Cây nhị phân hoàn thiện

Trong hình trên, ta thấy node gốc đã vi phạm các đặc tính của max heap bởi vì nó có giá trị nhỏ hơn giá trị node con của nó.

Hinh 3: Mô phỏng hoạt động của hàm max_heap

Bởi vì 8 lớn hơn 4, nên 8 được đổi chỗ với 4, lúc này hàm max_heap được thực hiện lại tại node có giá trị bằng 4 tại vị trí mới của nó.

Ở bước 2, vì 6 lớn hơn 4 nên node có gì trị bằng 4 được đổi cho cho node có giá trị bằng 6. Kết thúc bước 2 node có giá trị bằng 4 giờ là node lá, không có con nên hàm max_heap không được thực hiện trên node này, ta thu được max heap như mong đợi.

Như vậy ta đã chứng mình được tính đúng đắn của hàm max_heap.

Tuy nhiên hàm max_heap không đảm bảo sẽ cho ra kết quả đúng đắn khi ta chỉ truyền vào và thực hiện từ một node bất kỳ, mà ta cần áp dụng hàm max_heap cho tất cả các node trong cây.

Nhưng có một chú ý ở đây là hàm max_heap không cần áp dụng với các node lá, vì các node này không có con.

Giả sử ta có một cây nhị phân với 7 phần tử như sau: {8, 7, 6, 3, 2, 4, 5}.

Bạn có thể thấy các các node lá với giá trị 3, 2, 4, 5 được đánh chỉ số N/2 + 1, N/2 + 2, N/2 + 3, N/2 + 4 (với N = 7).

Do vậy ta chỉ cần áp dụng hàm max_heap() cho các phần tử còn lại được đánh chỉ số từ 1 tới N/2.

Do mỗi node lá là một thành phần của heap nên ta áp dụng hàm max_heap theo hướng từ dưới lên, để ta có thể bao quát được toàn bộ cây.

void run_maxheap (int A[ ])
{
    for(int i = N/2 ; i >= 1 ; i-- )
    {
        max_heap (A, i) ;
    }
}

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

Độ phức tạp của hàm max_heap() là logN, vòng for chạy từ N/2 về 1 có độ phức tạp là N/2. Nhưng trên thực tế độ phức tạp của hàm run_maxheap() là tuyến tính.

Ví dụ:

Giả sử ta có 7 phần tử được lưu trong mảng A.

Ở đây ta có N = 7, nên ta sẽ bắt đầu hàm max_heap từ vị trí N/2 = 3 tới 1.

Cùng xem hình vẽ mô tả dưới đây:

Bước 1: Gọi hàm max_heap(A,3), bởi vì 10 lớn hơn 3 nên 3 và 10 sẽ hoán đổi vị trí. Sau khi hoán đổi ta có A[3] = 10, A[7] = 3. Node có giá trị 3 giờ có chỉ số vị trí mới là 7 nên ta gọi hàm max_heap(A,7). Tuy nhiên hàm này không làm thay đổi gì cả, vì 3 lúc này là node lá.

Bước 2: Gọi max_heap(A,2), tại vị trí có chỉ số 2 là node có giá trị bằng 4, 4 được đổi chỗ với 8, do 8 là con của 4 mà lại có giá trị lớn hơn, khi này max_heap(A,5) sẽ được gọi nhưng không có tác động gì, vì 4 giờ là node lá.

Bước 3: Gọi max_heap(A,1), node ở chỉ số 1 trong mảng hiện tại có giá trị là 1 sẽ được đổi chỗ với node có giá trị 10. Vì 10 là con của 1 nhưng lại có giá trị lớn hơn.

Bước 4: Sau khi đổi chỗ 10 và 1 như ở trên bước 3, lúc này chỉ số của 1 là 3, nên ta gọi đệ quy hàm max_heap(A,3). Ở bước này 1 sẽ được đổi chỗ cho 9. 1 là node lá nên ta kết thúc gọi hàm đệ quy.

Bước 5: Ta thu được max heap, và lúc này các phần tử sẽ được sắp xếp như sau:

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

#include <iostream> 
using namespace std;

int N = 7; /* Số phần tử của heap */
void max_heap(int A[], int i) {
    int largest; /* Chỉ số của phần tử lớn 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 */
        largest = left;
    else
        largest = i;
    if (right <= N and A[right] > A[largest])
        largest = right;
    if (largest != i) {
        swap(A[i], A[largest]); /* Thực hiện đổi chỗ hai phần tử nếu 
                                              giá trị của node cha nhỏ hơn node con */
        max_heap(A, largest); /* Gọi đệ quy node tại vị trí mới */
    }
}

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

int main() {
    int A[N+1] = {-1,1,4,3,7,8,9,10}; /* 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_maxheap(A);
    printf("ntGiá trị của mảng sau khi áp dụng hàm max_heapn");
    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 max_heap */
        printf("t%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/maxheap.cpp

Kết luận

Như vậy trong bài này ta đã nắm bắt được những khái niệm về heap và cách thức mà loại cấu trúc dữ liệu này hoạt động.

Để tiếp tục tìm hiểu về loại heap còn lại (min heap) mời các bạn tiếp tục theo dõi trong bài sau.

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *