Algorithm/Heaps.js at master · seonjakim/Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/** Heaps
 * reference : https://www.youtube.com/watch?v=dM_JHpfFITs&ab_channel=freeCodeCamp.org
 * left child: i * 2;
 * right child: i * 2 + 1;
 * parent: i / 2;
 */

 let MinHeap = function() {
   let heap = [null];

   this.insert = function(num) {
     heap.push(num);
     if (heap.length > 2) {
       let idx = heap.length - 1;
       while (heap[idx] < heap[Math.floor(idx / 2)]) {
          if (idx >= 1)
            [heap[Math.floor(idx / 2)], heap[idx]] = [heap[idx], heap[Math.floor(idx / 2)]];
          if (Math.floor(idx / 2) > 1)
            idx = Math.floor(idx / 2);
          else
            break ;
       }
     }
   }

   this.remove = function() {
     let smallest = heap[1];
     if (heap.length > 2) {
       heap[1] = heap[heap.length - 1];
       heap.splice(heap.length - 1);
       if (heap.length == 3) {
         if (heap[1] > heap[2])
            [heap[1], heap[2]] = [heap[2], heap[1]];
         return smallest;
       }
       let i = 1;
       let left = 2 * i;
       let right = 2 * i + 1;
       while (heap[i] >= heap[left]|| heap[i] >= heap[right]) {
         if (heap[left] < heap[right]) {
           [heap[i], heap[left]] = [heap[left], heap[i]];
           i = 2 * i;
         } else {
           [heap[i], heap[right]] = [ehap[right], heap[i]];
           i = 2 * i + 1;
         }
         left = 2 * i;
         rigt = 2 * i + 1;
         if (heap[left] == undefined || heap[right] == undefined)
            break ;
       }
     } else if (heap.length == 2) {
       heap.splice(1, 1);
     } else {
       return null;
     }
     return smallest;
   }

   this.sort = function() {
     let result = new Array();
     while (heap.length > 1) {
       result.push(this.remove());
     }
     return result;
   }
 }

 console.log(MinHeap().insert(2));