SHARE
TWEET

Untitled

a guest May 19th, 2019 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const swap = (A, i, j) => {
  2.   const temp = A[i];
  3.   A[i] = A[j];
  4.   A[j] = temp;
  5. }
  6.  
  7. const heapify = (A, N, i) => {
  8.   // Find largest among root and children
  9.   let largest = i;
  10.   const left = 2 * i + 1;
  11.   const right = 2 * i + 2;
  12.  
  13.   if (left < N && A[left] > A[largest]) {
  14.     largest = left;
  15.   }
  16.   if (right < N && A[right] > A[largest]) {
  17.     largest = right;
  18.   }
  19.  
  20.   // If root is not largest, swap with largest and continue heapifying
  21.   if(largest !== i) {
  22.     swap(A, i, largest);
  23.     heapify(A, largest, N);
  24.   }
  25. }
  26.  
  27. const buildMaxHeap = (A, N) => {
  28.   for (let i = 0; i <= Math.floor(N/2); i++) {
  29.     heapify(A, N, i)
  30.   }
  31. }
  32.  
  33. const heapSort = (A, N) => {
  34.  
  35.   // Build max heap
  36.   buildMaxHeap(A, N);
  37.   // console.log('list', A);
  38.  
  39.   for (let j = N - 1; j > 0; j--) {
  40.  
  41.     swap(A, 0, j);
  42.     heapify(A, j, 0);
  43.   }
  44.  
  45.   return A;
  46. }
  47.  
  48. const arr = [5, 9, 2, 3];
  49.  
  50. const sorted = heapSort(arr, arr.length);
  51.  
  52. console.log('sorted --->', sorted);
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top