Heap

Heap (đống) là một cấu trúc dữ liệu cây có khóa của mỗi nút lớn hơn khóa của mỗi nút con. Trong heap thì khóa lớn nhất luôn nằm ở nút gốc.

Binary Heap

Binary Heap (đống nhị phân) là một cấu trúc dữ liệu Heap sử dụng cây nhị phân. Ngoài ra tất cả các tầng đều đầy đủ (tức đều có 2 nút con), tầng cuối cùng không đầy đủ thì được lấp đầy từ phải qua trái.

Ví dụ sau là một cây biểu diễn đống nhị phân:

    99
   ↙  ↘
  50   90
  ↙↘   ↙↘
20 40 70 10

Biểu diễn dữ liệu

Heap có thể biểu diễn dạng liên kết nhưng thường thì cấu trúc Heap được biểu diễn bằng mảng tương tự như cây nhị phân.

Cây nhị phân biểu diễn bằng mảng thì vị trí i có hai con là 2*i + 1 và 2*i + 2. Và vị trí i có cha là (i-1) / 2 (trừ khóa gốc không có cha). Vị trí i tính từ 0.

Chèn một khóa

Thuật toán chèn một khóa như sau:

• Chèn khóa mới vào tầng cuối cùng của đống
• So sánh khóa mới với khóa của nút cha, nếu nó nhỏ hơn cha, kết thúc.
• Nếu không, đổi chỗ khóa mới và khóa của nút cha, và trở lại bước trước.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

/**
 * @param arr là heap
 * @param length là số lượng phần tử trong heap
 * @param value là khóa cần chèn vào heap
 */
void insertHeap(int* arr, int length, int value) {
  arr[length] = value;
  int child = length;
  int parrent = (child - 1) / 2;
  while (arr[child] > arr[parrent] && child != parrent) {
    swap(arr, child, parrent);
    child = parrent;
    parrent = (child - 1) / 2;
  }
}

Vun đống

Vun đống là liên tục chèn giá trị vào mảng.
Ví dụ sau chèn các số 8, 2, 4, 0, 9, 1, 2, 3, 5, 4 vào đống, sẽ ra đống như sau:

         9
       ↙   ↘
      8     4
    ↙  ↘    ↙↘
   5    4  1  2
  ↙↘   ↙
 0  3 2

Biểu diễn qua mảng là 9 8 4 5 4 1 2 0 3 2.

1
2
3
4
5
6
7
8
9

int main() {
  const int length = 10;
  int arr[] = {8,2,4,0,9,1,2,3,5,4};
  int heap[length];
  for (int i = 0; i < length; i++) {
    insertHeap(heap, i, arr[i]);
  }
  printArr(heap, length); // 9 8 4 5 4 1 2 0 3 2
}

Xóa khóa lớn nhất

Thuật toán xóa khóa lớn nhất như sau:

• Đổi chỗ khóa cần xóa và khóa cuối cùng ở tầng cuối cùng rồi xóa khóa cần xóa khỏi đống. Khởi tạo nút hiện tại là nút gốc.
• So sánh khóa của nút hiện tại và khóa ở các nút con, nếu nó lớn hơn, kết thúc.
• Nếu không, đổi chỗ khóa hiện tại và khóa lớn hơn trong các khóa của nút con. Chuyển vị trí nút hiện tại tới nút con vừa được hoán đổi và trở về bước trước.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * @param arr là heap
 * @param length là số lượng phần tử trong heap
 */
void deleteMaxHeap(int* arr, int length) {
  swap(arr, 0, length - 1);
  length--; // kích cỡ của mảng giảm đi 1
  int parrent = 0;
  int child = 1;
  while ( 
    (child == length - 1 && arr[child] > arr[parrent]) ||
    (child < length - 1 && 
      (arr[child] > arr[parrent] || arr[child + 1] > arr[parrent]))) {
    // kiểm tra xem hai con ai lớn hơn thì lấy
    int child2 = child + 1;
    if (child2 < length && arr[child2] > arr[child]) {
      child = child2;
    }
    swap(arr, child, parrent);
    parrent = child;
    child = parrent * 2 + 1;
  }
}

Sau khi xóa nút gốc thì kết quả sẽ là 8 5 4 3 4 1 2 0 2 hay biểu diễn kiểu liên kết:

         8
       ↙   ↘
      5     4
    ↙  ↘    ↙↘
   3    4  1  2
  ↙↘ 
 0  2