JavaScriptAlgorithms/Tree/IndexHeap.html at master · biaodigit/JavaScriptAlgorithms · 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
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>索引堆</title>
</head>
<body>
<script src="../Sort/SortTestHelper.js"></script>
<script>
    // 索引堆
    class IndexMaxHeap {
        constructor(arr, capatity) {
            this.data = [];
            this.indexes = [];
            this.reverse = [];
            this.count = 0;
            for (let i = 0; i < arr.length; i++) {
                this.insert(i, arr[i])
            }

        }

        insert(i, node) {
            this.data[++i] = node;
            this.indexes[++this.count] = i;
            this.reverse[i] = this.count;
            this.shiftUp(this.count);

        }

        shiftUp(k) {
            while (k > 1 && this.data[this.indexes[k]] > this.data[this.indexes[k >> 1]]) {
                this.swapIndex(k, k >> 1)
                k = k >> 1
            }
        }

        shiftDown(k) {
            while (2 * k <= this.count) {
                let j = 2 * k;
                if (j + 1 <= this.count - 1 && this.data[this.indexes[j + 1]] > this.data[this.indexes[j]]) {
                    j += 1;
                }
                if (this.data[this.indexes[k]] >= this.data[this.indexes[j]]) return;

                this.swapIndex(k, j)
                k = j;
            }
            console.log(this.data)
        }

        getItem(i) {
            return this.data[i + 1]
        }

        extractMax() {
            let res = this.data[this.indexes[1]];
            this.swapIndex(1, this.count);
            this.reverse[this.indexes[this.count]] = 0;
            this.count--;
            this.shiftDown(1);
            return res
        }

        extractMaxIndex() {
            let res = this.indexes[1];
            this.swapIndex(1, this.count)
            this.reverse[this.indexes[this.count]] = 0;
            this.count--;
            this.shiftDown(1);
            return res
        }

        change(i, newItem) {
            this.data[++i] = newItem;
            let j = this.reverse[i];
            this.shiftUp(j);
            this.shiftDown(j);
        }

        swapIndex(i, j) {
            [this.indexes[i], this.indexes[j]] = [this.indexes[j], this.indexes[i]];

            this.reverse[this.indexes[i]] = i;
            this.reverse[this.indexes[j]] = j;
        }
    }

    let arr = [32, 153, 100, -50, -10, 6, 5, 1356, 20, 160, 2, 1432, 4, 50, 14, 102, -30, 3, 45, 1312, 1, -1, -3]
    let heap = new IndexMaxHeap(arr, arr.length)
    console.log(heap)
</script>
</body>
</html>