Heap nhị phân và thuật toán Heapsort -- Binary Heap and Heapsort

Bài này mình sẽ giới thiệu với các bạn cấu trúc dữ liệu Heap nhị phân. Đây là một cấu trúc dữ liệu đơn giản, dễ thực thi (you will see that!) và hiệu quả. Điểm yếu chính của cấu trúc này hầu hết các thao tác hỗ trợ có thời gian $O(\log n)$. Heap thường được dùng để thực thi hàng đợi ưu tiên (priority queue).

Nếu các bạn tìm kiếm Wikipedia, bạn sẽ thấy một bảng so sánh các loại Heap khác nhau. Mỗi loại Heap đều có một đặc điểm riêng và lĩnh vực ứng dụng cụ thể. Một số loại Heap như Fibonacci Heap, Rank-Pairing Heap, Brodal Heap, etc., có thời gian tiệm cận $O(1)$ cho hầu hết các thao tác. Tuy nhiên, điểm yếu của chúng là thực thi rất phức tạp, tốn bộ nhớ (do phải lưu trữ các con trỏ hỗ trơ) và mặc dù tiệm cận là $O(\log n)$ hay $O(1)$, hằng số ẩn sau kí hiệu $O$ là khá lớn. Nếu chúng ta chấp nhận các thao tác trong thời gian $O(\log n)$, heap nhị phân là một cấu trúc hoàn hảo.

Ngữ cảnh ứng dụng của Heap nhị phân thường có dạng như sau: Ta có một tập $n$ các phần tử $A[1,2,\ldots,n]$ trong đó phần tử thứ $i$ có giá trị $A[i]$. Thao tác mà chúng ta quan tâm nhất đối với tập này là tìm và lấy ra một phần tử có giá trị nhỏ nhất (hoặc lớn nhất) của tập hợp. Ngoài ra, chúng ta cũng muốn hỗ trợ các thao tác để thay đổi tập hợp đó. Danh sách một số các thao tác mà chúng ta thường quan tâm như sau:

  1. FindMin: Tìm phần tử có giá trị nhỏ nhất trong tập hợp $A$.
  2. Insert: Thêm một phần tử vào tập hợp $A$.
  3. ExtractMin: Tìm, trả lại và xóa phần tử nhỏ nhất ra khỏi tập hợp
  4. DecreaseKey: Giảm giá trị của một phần tử (cho trước) nào đó trong Heap. Thao tác tăng giá trị khóa ta làm tương tự nên mình không liệt kê vào đây.

Ta sẽ sử dụng cấu trúc Min-Heap để thực hiện các thao tác trên trong thời gian $O(\log n)$:

Theorem 1: Cấu trúc min-Heap nhị phân hỗ trợ các thao tác trên với thời gian $O(1)$ để thực hiện FindMin và thời gian $O(\log n)$ cho các thao tác còn lại.

 

Remark Tại thời điểm này mình vẫn chưa định nghĩa Heap nhị phân trong như thế nào cả. Mình sẽ định nghĩa ở dưới. Trong phần ứng dụng dưới đây, bạn đọc chỉ cần quan tâm đến các thao tác và thời gian thực hiện mỗi thao tác mà cấu trúc này hỗ trợ mà chưa cần quan tâm đến cấu trúc Heap sẽ được tổ chức như thế nào.

Ứng dụng

Ứng dụng nổi bật nhất của cấu trúc Heap nhị phân là trong sắp xếp mà ta gọi là thuật toán Heapsort. Giả sử ta có một mảng các số nguyên $A[1,2,\ldots,n]$ mà ta muốn sắp xếp nó theo chiều tăng dần của giá trị. Ta sẽ xây dựng một min-Heap nhị phân $H$ cho mảng này. $H$ hỗ trợ các thao tác liệt kê ở trên với thời gian trong Theorem 1. Để sắp xếp mảng ta làm theo các bước sau:

  1. Khởi tạo heap $H$ từ mảng $A[1,2,\ldots,n]$. Heap này có thể khởi tạo bằng cách bắt đầu từ một Heap rỗng, sau đó thực hiện chèn (sử dụng Insert) lần lượt từng phần tử vào Heap. Mỗi thao tác chèn mất thời gian $O(\log n)$, theo Theorem 1, do đó, Heap có thể được khởi tạo trong thời gian $O(n \log n)$. Dưới đây, mình sẽ giới thiệu phép khởi tạo khác trực tiếp từ mảng $n$ phần tử trong thời gian $O(n)$ .
  2. Thực hiện lặp trong $n$ bước. Bước thứ $i$ ta lấy phần tử nhỏ nhất ra khỏi Heap $H$ (ExtractMin) và đặt vào vị trí $A[i]$ của mảng. Do phần tử lấy ra trong mỗi bước là phần tử nhỏ nhất trong tập các phần tử còn lại trong Heap, thuật toán sẽ trả lại mảng đã sắp xếp theo chiều tăng dần.

Giả mã của Heapsort:

HeapSort($A[1,2,\ldots, n]$):
    $H \leftarrow $ BuildHeap($A[1,2,\ldots, n]$)
    for $i \leftarrow 1$ to $n$
        $A[i] \leftarrow $ ExtractMin($H$)
    return $A[1,2,\ldots,n]$

 
Code C:

int *H; // the heap
int n = 0; // the number of elements in the current Heap
int mlen = 16; //the initial length of the heap

// Heap is declared outside of this function
int  *heapsort(int *A, int size){
build_heap(A, size);
int i = 0;
for(; i < size; i++){
A[i] = extract_min();
}
return A;
}

Phân tích: Do mỗi thao tác ExtractMin mất thời gian $O(\log n)$, tổng thời gian để sắp xếp mảng là $O(n\log n)$.

Theorem 2: Thuật toán Heapsort sắp xếp mảng $n$ phần tử trong thời gian $O(n \log n)$.

 

Một ứng dụng khác của min-Heap là trong thuật toán Dijsktra tìm đường đi ngắn nhất từ một đỉnh trong đồ thị có trọng số không âm. Mình sẽ blog về thuật toán này sau.

Xây dựng Heap nhị phân

Experimental Thought: Cấu trúc biểu diễn đơn giản nhất là danh sách liên kết. Nếu sử dụng cấu trúc đó, các thao tác FindMin, ExtractMin mất $O(n)$ nhưng Insert, DecreaseKey có thể thực hiện $O(1)$. Nếu sửa đổi một chút bằng cách luôn lưu phần tử nhỏ nhất của tập hợp ở đầu danh sách và luôn chèn phần tử mới vào cuối danh sách, thì ta có thể thực hiện FindMin trong $O(1)$ còn ExtractMin vẫn là $O(n)$ do khi ta xóa phần tử nhỏ nhất khỏi danh sách, ta phải tìm phần tử nhỏ nhất trong số các phần tử còn lại và đưa nó về đầu danh sách. Cách khác là dùng mảng, tuy nhiên cách này cũng không ổn vì cho dù có làm thế nào thì một trong số các thao tác trên cũng là $O(n)$.

Nếu chúng ta muốn các thao tác trong trường hợp tồi nhất là $O(\log n)$, ta phải nghĩ ngay đến cấu trúc cây. Ở đây mình sẽ dùng cấu trúc cây nhị phân (do đó gọi là heap nhị phân). Trước hết để đảm bảo $O(\log n)$, cây của chúng ta phải cân bằng (do đó độ sâu của cây là $O(\log n)$). Ta sẽ lưu phần tử nhỏ nhất tại gốc của cây, do đó FindMin có thời gian $O(1)$. Cũng từ đó ta suy ra khóa của nút gốc nhỏ hơn khóa của hai nút con của nó. Ta sẽ đảm bảo tính chất này cho mọi nút của cây Heap. Như vậy hai tính chất cần thiết của cây Heap là:

  1. Tính chất Heap (Heap Property): Mỗi nút có một giá trị (khóa) nhỏ hơn hoặc bằng giá trị khóa của hai nút con.
  2. Tính cân bằng mạnh (Strong Balance Property): Mức thứ $i$ không phải là mức cao nhất có $2^i$ nút. Ở đây, nút gốc có mức $0$ và mức của một nút là mức của nút cha $+1$. Các nút của mức cao nhất (các nút lá) được đính vào cây theo thứ tự liên tục từ trái sang phải. Ví dụ trong hình dưới đây nếu ta đặt nút $6$ làm nút con phải của $5$ thì các nút lá không còn liên tục theo thứ tự từ trái sang phải nữa.

Ví du tập các giá trị $\{8,6,4,5,2,2,9,7,3\}$ có cấu trúc Heap biểu diễn minh họa trong hình dưới đây:

heap-example

Từ tính chất Heap, bằng quy nạp, ta có thể chứng minh được:

Fact 1: Với mỗi nút $u$ trong min-Heap thì giá trị khóa của $u$ là giá trị khóa nhỏ nhất của cây con gốc tại $u$

 
Gọi độ sâu (depth) của một nút là số cạnh trên đường đi từ nút gốc đến nút đó. Gọi độ sâu của cây là số cạnh đi từ gốc đến một nút lá tại mức cao nhất của cây đó. Từ tính cân bằng mạnh, ta suy ra:

Fact 2: Độ sâu của cây Heap là $\lfloor \log(n) \rfloor$, trong đó $n$ là số nút của cây.

 
Biểu diễn Heap: mặc dù ta nói cây Heap nhưng thực ra ta có thể biểu diễn "cây" đó bằng một mảng $H[1,2,\ldots,n]$. Ta sẽ biểu diễn các nút của cây Heap như sau:

  1. Gốc của cây là phần từ đẩu tiên của mảng, i.e, là phần tử $H[1]$. Do đó, phần tử $H[1]$ sẽ có giá trị nhỏ nhất.
  2. Phần tử thứ $i$ của mảng sẽ biểu diễn một nút có khóa $H[i]$. Con trái của nút đó sẽ là nút có khóa $H[2*i]$ và con phải của nút đó sẽ là có khóa $H[2*i + 1]$. Từ đó suy ra, cha của nút $i$ sẽ là $i/2$ nếu $i$ chẵn và là $(i-1)/2$ nếu $i$ lẻ.

Ví dụ mảng tương ứng với cây Heap ở hình trên được minh họa trong hình dưới đây. Các mũi tên màu đỏ gạch là các mũi tên nối từ nút cha tới một nút con.

heap-array

Trong thực tế cài đặt, nếu số lượng phần tử chèn vào vượt quá kích thước của mảng, ta phải cấp phát lại bộ nhớ cho mảng. Chiến lược cấp phát bộ nhớ có thể áp dụng là gấp đôi kích thước của mảng mỗi lần ta phải cấp phát bộ nhớ (giống ArrayList trong Java). Trong trường hợp chúng ta biết được kích thước tối đa của mảng trong mọi thời điểm thì bài toán sẽ đơn giản hơn nhiều.

Insert

Để chèn một khóa $K$ vào Heap, ta sẽ tìm nút lá cuối cùng của cây, là nút lá cuối cùng theo thứ tự từ trái sang phải. Gọi nút là đó là $u$. Để đảm bảo tính cân bằng mạnh, ta sẽ chèn $K$ vào nút anh em (sibling) gần nhất bên phải của $u$. Nếu cây nhị phân là cân bằng, ta sẽ chèn $K$ vào mức tiếp theo, ngoài cùng bên trái. Thao tác này được minh họa trong hình (a) và (b) của hình dưới đây.

Vấn đề còn lại là đảm bảo tính chất Heap. Nếu nút mới chèn vào có khóa nhỏ hơn nút cha nó, ta phải thay thế chỗ của nó với cha nó. Sau khi đổi chỗ, khóa của nút này vẫn có thể nhỏ hơn khóa của nút cha mới. Do đó, ta tiếp tục gọi đệ quy cho đến khi nào khóa của nó nhỏ hơn khóa của nút cha mới thì dừng lại. Ta gọi thủ tục đẩy một nút lên là thao tác vun đống ngược lên trên (Up-Heapify). Thao tác đó được minh họa trong hình (c), (d), (e) của hình dưới đây:

heap-insert

Với biểu diễn mảng, nút lá cuối cùng của cây chính là $H[n]$ và do đó, anh em gần nhất bên phải của nó là $H[n+1]$.

Giả mã:

Insert(Heap $H$, Key $K$):
    $n \leftarrow$ length of the heap $H$
    $H[n+1] \leftarrow K$
    $n \leftarrow n+1$
    UpHeapify$(n+1)$

 

UpHeapify( $u$):
    $v \leftarrow $ Parent( $u$)
    if $v \not= 0$ and $H[u] $ < $ H[v] $         $\ll u$ is not the root $\gg$
        swap $H[u] \leftrightarrow H[v]$
        UpHeapify($v$)

 

Parent( $u$):
    if $u$ is even
        return $u/2$
    else
        return $(u-1)/2$

 
Code C:

void insert(int x){
if(n == mlen){ // if the heap is full, double the size of the heap
H = (int *)realloc(H,2*mlen*sizeof(int));
mlen = 2*mlen;
}
H[n] = x;
n++;
up_heapify(n-1);
}

void up_heapify(int u){
int v = parent(u);
if(v != -1 &amp;&amp; H[u] &lt; H[v]){ // u is not the root of the heap
int tmp = H[u];
H[u] = H[v];
H[v] = tmp;
up_heapify(v);
}
}

// Note that array in C is indexed from 0
// Two children of a node u are 2u+1 and 2u+2, the smaller one is the left child

int parent(int u){
return ((u&amp;1)==0 ? ((u-2)&gt;&gt; 1) : (u-1) &gt;&gt; 1);
}

Phân tích: Thủ tục vun đống ngược lên trên có thời gian $O(\log n)$ vì theo Fact 2, cây Heap có độ sâu $\lfloor \log n\rfloor$. Do đó, ta có thể chèn một nút vào trong Heap trong thời gian $O(\log n)$.

DecreaseKey

Khi giảm giá trị khóa của một nút mà ta gọi là $u$, giá trị mới của $u$ có thể nhỏ hơn giá trị khóa của nút cha của nó (tại sao ta không cần quan tâm đến các nút con của nó). Do đó, ta sẽ sử dụng thủ tục vun đống ngược lên trên Up-Heapify để đảm bảo tính cân bằng. Thao tác này mất thời gian $O(\log n)$ do chiều cao của cây là $\lfloor \log n\rfloor$. Hình minh họa:
heap-decrease-key

Giả mã như sau:

DecreaseKey(Heap $H$, $u$, Key $K$):
    $H[u] \leftarrow K$
    UpHeapify$(u)$

 
Code C:


void decrease_key(int u, int k){
if(H[u] &lt; k){
printf("new key is bigger than the old key\n");
return;
} else {
H[u] = k;
up_heapify(u);
}
}

ExtractMin

Thủ tục này phức tạp hơn cả vì ta cần phải xóa phần tử nhỏ nhất ra khỏi Heap và cùng một lúc đảm bảo các tính chất của Heap. Chú ý phần tử nhỏ nhất là gốc của cây Heap. Do đó, để đảm bảo tính cân bằng mạnh, đầu tiên ta sẽ đưa nút lá cuối cùng lên làm gốc, thế chỗ cho nút có khóa nhỏ nhất.

Do nút gốc mới này có giá trị có thể lớn hơn nút con của nó, ta sẽ đổi chỗ cho nút con có khóa nhỏ nhất của nó. Sau đó tiếp tục gọi đệ quy vì sau khi đổi chỗ, khóa của nó có thể vẫn lớn hơn khóa của các nút con mới. Ta gọi thủ tục này là vun đống xuôi xuống dưới (Down-Heapify). Do độ cao của cây Heap là $\lfloor \log n \rfloor$, thủ tục này mất thời gian $O(\log n)$. Thao tác đó được minh họa trong hình dưới đây:
extract-min

Giả mã:

ExtractMin(Heap $H$):
    $n \leftarrow$ length of the heap $H$
    $tmp \leftarrow H[1]$
    $H[1] \leftarrow H[n]$
    $n \leftarrow n-1$
    DownHeapify$(1)$
    return $tmp$

 

DownHeapify( $u$):
    $m \leftarrow 2*u$         $\ll m$ is the left child of $u$ $\gg$
    if $m \leq n$         $\ll u$ is not a leaf$\gg$
        if $H[m]$ > $ H[2*u+1]$
            $m \leftarrow 2*u+1$
        if $H[u]$ > $H[m]$
            swap $H[u] \leftrightarrow H[m]$
            DownHeapify($m$)

 
Code C:

int extract_min(){
int tmp  = H[0];
H[0] = H[n-1];
n--;
down_heapify(0);
return tmp;
}

void down_heapify(int u){
int m = 2*u+1;
if(m &lt; n){	// u is not a leaf of the heap
if(2*u+2 &lt; n &amp;&amp; H[m] &gt; H[2*u+2]) m = 2*u+2;
if(H[u] &gt; H[m]){
int tmp = H[u];
H[u] = H[m];
H[m] = tmp;
down_heapify(m);
}
}
}

Xây dựng Heap từ một mảng

Giả sử ta có đầu vào là một mảng $A[1,2,\ldots,n]$, ta muốn xây dựng Heap với khóa là các phần tử của mảng. Ta có thể xây dựng bằng cách bắt đầu từ một Heap rỗng và lần lượt chèn các phần tử vào Heap. Mỗi lần chèn ta mất thời gian $O(\log n)$, do đó, ta có thể xây dựng Heap trong thời gian $O(n \log n)$. Tuy nhiên, ta có thể xây dựng Heap trong thời gian $O(n)$ như sau:

  1. Xếp các phần tử của mảng vào Heap theo một thứ tự bất kì thỏa mãn tính chất cân bằng mạnh. Nếu Heap biểu diễn bằng mảng thì có thể gán $H[i] \leftarrow A[i]$.
  2. Với mỗi nút trong Heap ta sẽ thực hiện vun đống xuôi xuống dưới (Down-Heap) để đảm bảo tính chất Heap. Ta sẽ thực hiện vun đống theo mức, bắt đầu từ các nút lá, rồi dần lên các mức cao hơn.

Thao tác đó được minh họa trong hình sau. Các nút được đánh dấu là các nút ta sẽ thực hiện Down-Heapify.

batch-build-heap
Giả mã:

BuildHeap($A[1,2,\ldots,n]$):
    for $i \leftarrow 1$ to $n$
        $H[i] \leftarrow A[i]$
    for $i \leftarrow n$ down to $1$
        DownHeapify$(i)$

 

Code C:

// Build the heap from an array in O(n) time
void build_heap(int *A, int len){
n = len;
mlen = n+1;
H = (int *)malloc(mlen*(sizeof(int)));
int i = 0;
for(; i &lt; len; i++){
H[i] = A[i];
}
for(i = len-1; i &gt;=0; i--){
down_heapify(i);
}
}

Phân tích: Ta có các nhận xét sau:

  1. Số nút ở mức thức $i$ là $2^i$.
  2. Độ sâu của cây con của một nút ở mức thứ $i$ là $h - i$ trong đó $h = \lfloor \log n\rfloor$.
  3. Thời gian để vun đống nút ở mức thứ $i$ là $O(h-i)$.

Do đó, tổng thời gian của thuật toán là:

$\sum_{i=0}^h O(2^i(h-i)) = O(h \sum_{i=0}^h 2^i - \sum_{i=0}^h 2^i*i) = O(h(2^{h+1}-1) - \sum_{i=0}^h 2^i*i)\qquad (1)$

Đặt $S(h) = \sum_{i=0}^h 2^i*i$, sử dụng đạo hàm 2 vế của đẳng thức $ \sum_{i=0}^h r^i = \frac{r^{h+1}-1}{r-1}$ theo $r$ và thay thế $r = 2$, ta suy ra $S(h) = (h+1)2^{h+1} + 2 - 2^{h+2}$. Do đó, ta có:

$T(n) = O(2^{h+2}) = O(n) \qquad (2)$

Final Remark Cấu trúc Heap nhị phân không bắt buộc quan hệ giữ con trái và con phải của một nút, có nghĩa là con trái có thể lớn hơn con phải và ngược lại. Do đó, ta có thể "tích hợp" thêm quan hệ giữa con phải và con trái. Cấu trúc sử dụng ý tưởng này chính là cây tìm kiếm nhị phân mà mình đã viết ở bài trước.

Code đầy đủ của bài viết: Heap-and-Heapsort.
Tham Khảo

[1] Binary Heap on Wikipedia, https://en.wikipedia.org/wiki/Binary_heap, Accessed 11/01/2016.

Facebook Comments

Tags: , , , ,

  1. Dũng’s avatar

    Mình thắc mắc chỗ DecreaseKey
    Giả sử dãy ban đầu của mình là a[1..n]
    Sau đó mình xây dựng min heap H[1..n] từ mảng a
    Bây giờ mình thay đổi giá trị của phần tử thứ i trong a thì làm cho Heap nó thay đổi như thế nào?
    Ví dụ: a = 4 2 3 1 => H = 1 2 3 4
    Khi này mình thay đổi a[1] = 2
    => Heap sẽ thành H = 1 2 5 2 (chưa hiệu chỉnh)
    Hiệu chỉnh thành => H = 1 2 2 5

    Reply

  2. Hung Le’s avatar

    Hi
    Mình không hiểu ví dụ của bạn lắm. Tại sao thay đổi phần tử a[1] = 2 lại thay đổi được toàn bộ Heap như ví dụ của bạn?

    Về cơ bản, bạn muốn thay đổi một khóa. có thể hiểu là bạn muốn tăng hoặc giảm giá trị của khóa đó. Giảm giá trị khóa và duy trì Heap sau khi giảm mình đã mô tả trong phần DecreaseKey. Nếu bạn muốn tăng giá trị của một khóa, làm tương tự, nhưng bạn sẽ gọi DownHeapify thay vì UpHeapify.

    Hùng

    Reply

  3. Dũng’s avatar

    Về thay đổi giá trị của heap mình đã hiểu.
    - Nhưng giả sử ban đầu mình có mảng a.
    - Sau đó mình xây dựng heap từ mảng a đó => mảng a có n phần tử thì mảng heap cũng có n phần tử thôi
    - Bây giờ bài toán thay đổi giá trị của phần tử trong mảng a, điều đó cũng có nghĩa mình phải cho heap phải thay đổi tương ứng, thì mình sẽ code để heap thay đổi ntn?
    - Ý bạn là thay đổi key trên heap, nhưng thay đổi a[1] = 2 chẳng hạn thì lúc này a[1] ở chỗ nào trong heap để mà thay đổi.

    Reply

    1. Hung Le’s avatar

      Trong trường hợp này, có lẽ bạn cần thêm một mảng nữa, ví dụ pos[1,...,n] để xác định xem phần tử A[i] ở vị trí nào trong Heap. Ví dụ pos[1] = 5 nghĩa là A[1] ở vị trí thứ 5 trong mảng Heap. Khi thực hiện các thao tác của Heap, ngoài các khung cơ bản như trên thì bạn cần phải cập nhật mảng post.

      Hùng

      Reply

Reply to Hung Le Cancel reply

Your email address will not be published. Required fields are marked *