การนำ Heap Sort มาใช้ด้วย vanilla JavaScript

Heap Sort คืออัลกอริทึมการเรียงลำดับแบบเปรียบเทียบ (comparison-based) สามารถมองได้ว่าเป็น selection 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 
]