'a'

mh-two-thousand-and-two

2024-04-12 44d2c92345cd156a59fc327b3060292a282d2893

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
var Class = require('./Class');
var swap = require('./swap');
var isSorted = require('./isSorted');
exports = Class({
    initialize: function Heap() {
        var cmp =
            arguments.length > 0 && arguments[0] !== undefined
                ? arguments[0]
                : isSorted.defComparator;
        this._cmp = cmp;
        this.clear();
    },
    clear: function() {
        this._data = [];
        this.size = 0;
    },
    add: function(item) {
        this._data.push(item);
        this.size++;
        this._heapifyUp(this.size - 1);
        return this.size;
    },
    poll: function() {
        var data = this._data;
        if (this.size > 0) {
            var item = data[0];
            data[0] = data[this.size - 1];
            this.size--;
            this._heapifyDown(0);
            return item;
        }
    },
    peek: function() {
        if (this.size > 0) {
            return this._data[0];
        }
    },
    _heapifyUp: function(idx) {
        var data = this._data;
        var parent = parentIdx(idx);
        while (idx > 0 && this._cmp(data[parent], data[idx]) > 0) {
            swap(data, parent, idx);
            idx = parent;
            parent = parentIdx(idx);
        }
    },
    _heapifyDown: function(idx) {
        var size = this.size;
        var cmp = this._cmp;
        var data = this._data;
        while (leftChildIdx(idx) < size) {
            var smallerIdx = leftChildIdx(idx);
            var rightChild = rightChildIdx(idx);
            if (
                rightChild < size &&
                cmp(data[rightChildIdx], data[smallerIdx]) < 0
            ) {
                smallerIdx = rightChild;
            }
            if (cmp(data[idx], data[smallerIdx]) < 0) {
                break;
            } else {
                swap(data, idx, smallerIdx);
            }
            idx = smallerIdx;
        }
    }
});
function parentIdx(idx) {
    return Math.floor((idx - 1) / 2);
}
function leftChildIdx(idx) {
    return 2 * idx + 1;
}
function rightChildIdx(idx) {
    return 2 * idx + 2;
}
 
module.exports = exports;