Heap Sort JS

Heap Sort sử dụng Max Heap để sắp xếp mảng tăng dần: Các bước: Xây dựng Max Heap từ mảng đầu vào. Lặp lại: Hoán đổi phần tử đầu (arr[0], lớn nhất) với phần tử cuối chưa được sắp xếp. Giảm kích thước heap (loại bỏ phần tử đã xếp). Heapify lại cây từ gốc để duy trì tính chất max-heap. Kết thúc khi heap còn 1 phần tử.

O(n log n)

Medium confidence

Last analyzed Oct 2, 2025

Authored by test 2*Oct 2, 2025

Code

JSSnippet preview

1function heapSort(arr) {
2  const n = arr.length;
3
4  // Xây dựng Max Heap
5  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
6    heapify(arr, n, i);
7  }
8
9  // Trích xuất phần tử lớn nhất và heapify lại
10  for (let i = n - 1; i > 0; i--) {
11    [arr[0], arr[i]] = [arr[i], arr[0]]; // Đưa max về cuối mảng
12    heapify(arr, i, 0); // Heapify lại heap rút gọn
13  }
14
15  return arr;
16}
17
18function heapify(arr, n, i) {
19  let largest = i;
20  const left = 2 * i + 1;
21  const right = 2 * i + 2;
22
23  // Nếu con trái lớn hơn node gốc
24  if (left < n && arr[left] > arr[largest]) {
25    largest = left;
26  }
27
28  // Nếu con phải lớn hơn node lớn nhất hiện tại
29  if (right < n && arr[right] > arr[largest]) {
30    largest = right;
31  }
32
33  // Nếu node lớn nhất không phải gốc, hoán đổi và đệ quy
34  if (largest !== i) {
35    [arr[i], arr[largest]] = [arr[largest], arr[i]];
36    heapify(arr, n, largest);
37  }
38}

Loading snippet preview...

Complexity explanation

Divide-and-conquer pattern combined with iteration/recursion.

Signals detected

Nested loops depth 3
Divide-and-conquer pattern
Recursive call