การใช้ Heap Sort โดยใช้ vanilla JavaScript

Heap Sort เป็นอัลกอริธึมการจัดเรียงแบบเปรียบเทียบโดยพื้นฐาน ถือได้ว่าเป็นการจัดเรียงการเลือกที่ได้รับการปรับปรุง เช่นเดียวกับอัลกอริธึมนั้น มันแบ่งอินพุตออกเป็นพื้นที่ที่จัดเรียงแล้วและส่วนที่ไม่ได้จัดเรียง และย่อส่วนที่ไม่เรียงลำดับแบบโต้ตอบด้วยการแยกองค์ประกอบเป้าหมาย (ใหญ่ที่สุดหรือเล็กที่สุด) แล้วย้ายไปยังส่วนที่จัดเรียง ภูมิภาค

ตัวอย่าง

รหัสสำหรับสิ่งนี้จะเป็น −

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;

ผลลัพธ์

และผลลัพธ์ในคอนโซลจะเป็น −

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