Cấu trúc dữ liệu Heap và ứng dụng

Heap là một trong những cấu trúc dữ liệu đặc biệt quan trọng, nó giúp ta có thể giải được nhiều bài toán trong thời gian cho phép. Độ phức tạp thông thường khi làm việc với Heap là O(logN). CTDL Heap được áp dụng nhiều trong các bài toán tìm đường đi ngắn nhất, tìm phần tử max, min… và trong lập trình thi đấu. Vậy Heap là gì? Cài đặt Heap như thế nào?

Heap là gì?

Heap thực chất là một cây cân bằng thỏa mãn các điều kiện sau

• Một nút có không quá 2 nút con.
• Với Heap Max thì nút gốc là nút lớn nhất, mọi nút con đều không lớn hơn nút cha của nó. Với Heap Min thì ngược lại.

Mặc dù được mô tả như cây nhưng Heap có thể được biểu diễn bằng mảng. Nút con của nút i là 2*i và 2*i+1. Do Heap là cây cân bằng nên độ cao của 1 nút luôn <= logN.

Ứng dụng chủ yếu của Heap là tìm Min, Max trong 1 tập hợp động (có thể thay đổi, thêm, bớt các phần tử) nhưng như vậy đã là quá đủ.

Các thao tác với Heap

Ở đây mình hướng dẫn các bạn với Heap Max còn với Heap Min thì tương tự

Khai báo

Ở ví dụ này, Heap sẽ là mảng một chiều kiểu LongInt, nHeap là số phần tử của mảng.

Const
  maxn = 100000;
Var
  nHeap : LongInt;
  Heap : array[0..maxn] of LongInt;

1. UpHeap

Nếu 1 nút lớn hơn nút cha của nó thì di chuyển nó lên trên:

Procedure UpHeap(i : LongInt);
Begin
  if (i = 1) or (Heap[i] < Heap[i div 2]) then exit; // Nếu i là nút gốc hoặc  nhỏ hơn nút cha thì không làm việc
  swap(Heap[i] , Heap[i div 2]); // Đổi chỗ 2 phần tử trong Heap;
  UpHeap(i div 2); // Tiếp tục di chuyển lên trên
end;

2. DownHeap

Procedure DownHeap(i : LongInt);
  Var
    j : LongInt;
  Begin
    j := i*2;
    if j > nHeap then exit; // Nếu i không có nút con thì không làm việc
    if (j < nHeap) and (Heap[j] < Heap[j+1]) then Inc(j); // Nếu i có 2 nút con thì chọn nút ưu tiên hơn
    if Heap[i] < Heap[j] then // Nếu nút cha nhỏ hơn nút con
      begin
        swap(Heap[i] , Heap[j]); // Đổi chỗ 2 phần tử trong Heap
        DownHeap(j); // Tiếp tục di chuyển xuống dưới
      end;
  end;

3. Push

Đưa 1 phần tử mới vào Heap: Thêm 1 nút vào cuối Heap và tiến hành UpHeap từ đây:

Procedure Push(x : LongInt);
  Begin
    Inc(nHeap); // Tăng số phần tử của Heap
    Heap[nHeap] := x; // Thêm x vào Heap
    UpHeap(nHeap);
  End;

4. Pop

Rút ra 1 phần tử ở vị trí v trong Heap: Gán Heap[v] := Heap[nHeap] rồi tiến hành chỉnh lại Heap:

Function Pop(v : LongInt) : LongInt;
  Begin
    Pop := Heap[v]; // Lấy phần tử ở vị trí v ra khỏi Heap
    Heap[v] := Heap[nHeap]; // Đưa phần tử ở cuối Heap vào vị trí v
    Dec(nHeap); // Giảm số phần tử của Heap đi 1
    {Chỉnh lại Heap}
    UpHeap(v);
    DownHeap(v);
  End;

Nguồn: không rõ