Data-Structures-Algorithms-Hacktoberfest-2K19/Data Structures/priority queue/priorityQueue.js at 9de8b84b56542ce96d48dd7c7aea715ae4c4a903 · frextrite/Data-Structures-Algorithms-Hacktoberfest-2K19 · 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
(function (exports) {

  var MaxHeap = {
    h: [],

    last: function () {
      return this.h.pop();
    },

    size: function () {
      return this.h.length;
    },

    push: function (e) {
      var i = this.size(),

      parent = Math.ceil(i / 2) - 1;
      this.h[i] = e;
      this.bubbleUp(i);
		},

    bubbleUp: function (i) {
      var parent;

      while (i > 0) {
        parent = Math.ceil(i / 2) - 1;
        if (this.h[parent] < this.h[i]) {
          this.swap(this.h, parent, i);
          i = parent;
        } else {
          return;
        }
      }
    },

    pop: function () {
      var head = this.h[0];

      this.h[0] = this.last();
      this.h.splice(this.size() - 1, 1);
      this.heapify(0);

      return head;
    },

    peek: function () {
      return this.h[0];
    },

    swap: function (a, i , j) {
      var tmp = a[i];

      a[i] = a[j];
      a[j] = tmp;
    },

    sinkDown:  function (i, a) {
      var left = 2 * i + 1,
          right = left + 1,
          largest = i,
          len = a.length;
      a = a || this.h;

      if (left < len && a[left] > a[largest]) {
        largest = left;
      }

      if (right < len && a[right] > a[largest]) {
        largest = right;
      }

      if (largest !== i) {
        this.swap(a, i, largest);
        this.sinkDown(largest, a);
      }
    },

    remove: function (e) {
      var i = -1,
          len = this.size(),
          parent;

      while (++i < len) {
        if (this.h[i] === e) {
          e = this.last();

          if (i !== len - 1) {
            this.h[i] = e;
            parent = this.h[Math.ceil(i / 2 - 1)];
            (parent > e)?  this.sinkDown(i) : this.bubbleUp(i);
          }

          return;
        }
      };
    },

    buildHeap: function (a) {
      var i = Math.floor(a.length / 2);

      while (i-- >= 0) {
        this.sinkDown(i, a);
      }
    },

    create: function (a) {
      var o = Object.create(this);

      if (a && (a instanceof Array)) {
        o.buildHeap(o.h = a);
      }

      return o;
    },

    toSortedArray: function () {
      ///TODO needs to implemented
      return false;
    }
  };

  exports.MaxHeap = MaxHeap;
}(this));