Live Note

Remain optimistic

6.006 - 3

about the heap

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
class Heap {
  constructor(arr) {
    this.data = arr.reduce((arr, elem) => {
      arr.push(elem)
      return arr
    }, [])
    this.size = this.data.length
  }

  isEmpty() {
    return this.size === 0
  }

  build_max_heap() {
    if (this.size <= 1) return

    for (let i = Math.floor(this.size / 2); i >= 0; i--) {
      // start from the n / 2 because of the elem after n / 2 are all leaves
      this.max_heapify(i)
    }
  }

  sort() {
    let result = []

    while (!this.isEmpty()) {
      result.push(this.data.shift()) // pop the max
      this.size--
      this.build_max_heap() // rebuild the heap
    }

    this.data = result
    this.size = result.length
  }

  add(value) {
    this.data.push(value)
    this.size++

    this.build_max_heap()
  }

  max_heapify(current) {
    let left = 2 * current, // get the left child
      right = 2 * current + 1, // get the right child
      largest = current // get the max node

    if (left < this.size && this.data[left] > this.data[largest]) largest = left // left child is max
    if (right < this.size && this.data[right] > this.data[largest])
      largest = right // right child is max

    if (largest !== current) {
      // if the max node is not the current node
      ;[this.data[largest], this.data[current]] = [
        this.data[current],
        this.data[largest],
      ] // swap the value
      this.max_heapify(largest) // recursive to check the modify child heap if is max heapify
    }
  }

  print() {
    let str = ""
    this.data.map((i) => (str += i + " "))
    console.log(str)
  }
}

let heap = new Heap([1, 2, 3, 6, 4, 5, 9, 8, 11, 14])
heap.build_max_heap()
heap.print()

heap.sort()
heap.print()

heap.add(30)
heap.add(12)
heap.print()

heap.sort()
heap.print()

result:

1
2
3
4
14 11 5 9 4 1 6 8 3 2
14 11 9 8 6 5 4 3 2 1
30 14 12 8 6 11 4 3 2 1 5 9
30 14 12 11 9 8 6 5 4 3 2 1