1
p = 0, l = 1, r = 2
2
p = 1, l = 3, r = 4
3
p = 2, l = 5, r = 6
4
p = 3, l = 7, r = 8
5

6
// 当前案例一共只有9个节点，如果节点更多的话，我们还可以继续总结
7
p = 4, l = 9, r = 10
8
p = 5, l = 11, r = 12

1
p = (l - 1) / 2 
2
p = (r - 2) / 2

1
// 必定等于整数
2
p = (l - 1) / 2  = Math.floor((l - 1) / 2)
3
p = (r - 2) / 2 = Math.floor((r - 1) / 2)

p = Math.floor((i - 1) / 2)

100
class BinaryHeap {
200
  constructor(compare, array) {
300
    this.compare = compare
400
    if (array) {
500
      this.heap = array
600
      this.size = this.heap.length
700
      this.buildHeap()
800
    } else {
900
      this.heap = []
100
      this.size = 0
110
    }
120
  }
130
  // 判断是否为空
140
  isEmpty() {
150
    return this.size == 0
160
  }
170
  // 通过子节点下标，获取节点的父亲节点
180
  parentIndex(i) {
190
    return Math.floor((i - 1) / 2)
200
  }
210
  parent(i) {
220
    return this.heap[this.parentIndex(i)]
230
  }
240
  leftIndex(i) {
250
    return 2 * i + 1
260
  }
270
  // 通过父节点下标，获取父节点的左边子节点
280
  left(i) {
290
    return this.heap[this.leftIndex(i)]
300
  }
310
  rightIndex(i) {
320
    return 2 * i + 2
330
  }
340
  // 通过父节点下标，获取父节点的右边子节点
350
  right(i) {
360
    return this.heap[this.rightIndex(i)]
370
  }
380

390
  // 节点交换
400
  swap(i, j) {
410
    const temp = this.heap[i]
420
    this.heap[i] = this.heap[j]
430
    this.heap[j] = temp
440
  }
450

460
  // 插入节点
470
  push(node) {
480
    if (this.size == 0) {
490
      this.size ++
500
      this.heap[0] = node
510
      return
520
    }
530
    this.size ++
540
    let i = this.size - 1
550
    this.heap[i] = node
560
    while(i != 0 && this.compare(this.heap[i], this.parent(i))) {
570
      this.swap(i, this.parentIndex(i))
580
      i = this.parentIndex(i)
590
    }
600
  }
610

620
  // 无论是删除元素，或者说构建二叉堆，都需要重新排序，封装统一的方法来支持排序过程，
630
  // 叶子节点不会调用此方法
640
  // 向下调整
650
  heapify(i) {
660
    // 找到最小的元素
670
    const l = this.leftIndex(i)
680
    const r = this.rightIndex(i)
690
    const pv = this.heap[i],
700
          lv = this.heap[l],
710
          rv = this.heap[r]
720

730
    let small = i
740
    if (l < this.size && this.compare(lv, pv)) {
750
      small = l
760
    }
770
    if (r < this.size && this.compare(rv, this.heap[small])) {
780
      small = r
790
    }
800

810
    if (small != i) {
820
      this.swap(i, small)
830
      this.heapify(small)
840
    }
850
  }
860

870
  // 删除堆顶元素
880
  pop() {
890
    if (this.size <= 0) {
900
      return null
910
    }
920
    if (this.size == 1) {
930
      let node = this.heap[this.size - 1]
940
      this.size --
950
      this.heap.length = this.size
960
      return node
970
    }
980
    const root = this.heap[0]
990
    this.heap[0] = this.heap[this.size - 1]
100
    this.size --
101
    this.heap.length = this.size
102
    this.heapify(0)
103
    return root
104
  }
105

106
  // 获取堆顶元素
107
  top() {
108
    return this.heap[0]
109
  }
110

111
  // 构建堆，从最后一个非叶子节点开始遍历构建
112
  buildHeap() {
113
    for (let i = this.parentIndex(this.size - 1); i >= 0; i--) {
114
      this.heapify(i)
115
    }
116
  }
117
}
118

119
function compare(a, b) {
120
  return a < b;
121
}
122

123
var heap = new BinaryHeap(compare);
124
heap.push(1);
125
heap.push(2);
126
heap.push(3);
127
heap.push(4);
128
heap.push(5);
129
console.log(heap.heap) // [1, 2, 3, 4, 5]
130
heap.pop()
131
console.log(heap.heap) // [2, 4, 3, 5]
132

133
var array = [150, 80, 40, 30, 10, 70, 110, 100, 20, 90, 60, 50, 120, 140, 130]; 
134
var h = new BinaryHeap(compare, array);
135
console.log(h.heap) // [10, 20, 40, 30, 60, 50, 110, 100, 150, 90, 80, 70, 120, 140, 130]

1
function compare(a, b) {
2
  // 小顶堆
3
  return a < b;
4
}
5

6
function compare(a, b) {
7
  // 大顶堆
8
  return a > b;
9
}

10
  push(node) {
20
    if (this.size == 0) {
30
      this.size ++
40
      this.heap[0] = node
50
      return
60
    } 
70
    this.size ++
80
    let i = this.size - 1
90
    this.heap[i] = node
10
    while(i != 0 && this.compare(this.heap[i], this.parent(i))) {
11
      this.swap(i, this.parentIndex(i))
12
      i = this.parentIndex(i)
13
    }
14
  }

1
const array = [
2
  {name: 'Jake', id: 29}, 
3
  {name: 'Toms', id: 22},
4
  {name: 'Jone', id: 40},
5
  ...
6
]

1
function compare(a, b) {
2
  // 小顶堆
3
  return a.id < b.id;
4
}
5

6
function compare(a, b) {
7
  // 大顶堆
8
  return a.id > b.id;
9
}

1
var array = [150, 80, 40, 30, 10, 70, 110, 100, 20, 90, 60, 50, 120, 140, 130]; 
2

3
// 由小到大排序
4
var _a = array.sort((a, b) => a - b)
5
console.log(_a)   // [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150]
6

7
// 由大到小排序
8
var _b = array.sort((a, b) => b - a)
9
console.log(_b)  // [150, 140, 130, 120, 110, 100, 90, 80, 70, 60, 50, 40, 30, 20, 10]

10
const persons = [
20
  { name: 'Jake', id: 29 },
30
  { name: 'Toms', id: 22 },
40
  { name: 'Jone', id: 40 },
50
  { name: 'Alex', id: 3 },
60
]
70

80
const p1 = persons.sort((a, b) => a.id - b.id)
90
console.log(p1) // 结果为按照 id，从小打大排序
10

11
// 因为引用类型的关系，下面的代码请分开执行，否则眼睛看到的打印结果将会是最后一次的排序结果
12

13
const p2 = persons.sort((a, b) => b.id - a.id)
14
console.log(p2)  // 结果为按照 id，从大到小排序