Triển khai Sắp xếp đống bằng cách sử dụng JavaScript vani

Heap Sort về cơ bản là một thuật toán sắp xếp dựa trên so sánh. Nó có thể được coi là một sắp xếp lựa chọn được cải tiến - giống như thuật toán đó, nó chia đầu vào của nó thành một vùng được sắp xếp và một vùng chưa được sắp xếp, và nó tương tác thu nhỏ vùng không được sắp xếp bằng cách trích xuất phần tử mục tiêu (lớn nhất hoặc nhỏ nhất) và chuyển phần tử đó đến vùng đã sắp xếp vùng.

Ví dụ

Mã cho điều này sẽ là -

const constructHeap = (arr, ind) => {
   let left = 2 * ind + 1;
   let right = 2 * ind + 2;
   let max = ind;
   if (left < len && arr[left] > arr[max]) {
      max = left;
   }
   if (right < len && arr[right] > arr[max]) {
      max = right;
   }
   if (max != ind) {
      swap(arr, ind, max);
      constructHeap(arr, max);
   }
}
function swap(arr, index_A, index_B) {
   let temp = arr[index_A];
   arr[index_A] = arr[index_B];
   arr[index_B] = temp;
}
function heapSort(arr) {
   len = arr.length;
   for (let ind = Math.floor(len / 2); ind >= 0; ind −= 1) {
      constructHeap(arr, ind);
   }
   for (ind = arr.length − 1; ind > 0; ind−−) {
      swap(arr, 0, ind);
      len−−;
      constructHeap(arr, 0);
   }
}
const arr = [3, 0, 2, 5, −1, 4, 1];
heapSort(arr);
console.log(arr);
var len;

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

[
   −1, 0, 1, 2,
   3, 4, 5
]