简介

堆的本质是一种特殊的树形数据结构，使用完全二叉树来实现

  • 堆可以进行很多分类，但是平时使用的基本都是二叉堆

二叉堆又可以划分为最大堆和最小堆

最大堆和最小堆：

  • 最小堆：堆中每一个节点都小于等于（<=）它的子节点
  • 最大堆：堆中每一个节点都大于等于（>=）它的子节点

如果有一个集合，获取其中的最大值或者最小值

  • 数组/链表：获取最大或最小值是 O(n)级别的
    • 可以进行排序，但是我们只是获取最大值或者最小值而已
    • 排序本身就会消耗性能；
  • 哈希表：不需要考虑了；
  • 二叉搜索树：获取最大或最小值是 O(logn)级别的
    • 但是二叉搜索树操作较为复杂，并且还要维护树的平衡时才是 O(logn)级别
    • 这个时候需要一种数据结构来解决这个问题，就是堆结构

性质

堆结构通常是用来解决 Top K 问题的

Top K 问题是指在一组数据中，找出最前面的 K 个最大/最小的元素；

  • 常用的解决方案有使用排序算法、快速选择算法、堆结构等

二叉堆用树形结构表示出来是一颗完全二叉树

通常在实现的时候我们底层会使用数组来实现

每个节点在数组中对应的索引 i（index）有如下的规律：

  • 如果 i = 0 ，它是根节点；
  • 父节点的公式：floor( (i – 1) / 2 )
  • 左子节点：2i + 1
  • 右子节点：2i + 2

完全二叉树 使用数组来实现不会浪费内存

封装

基本封装

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
import IHeap from "./IHeap";

class Heap<T> implements IHeap<T> {
  private data: T[] = [];
  private length: number = 0;

  // 工具方法
  swap(i: number, j: number) {
    // let temp = this.data[i];
    // this.data[i] = this.data[j];
    // this.data[j] = temp;
    [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
  }

  insert(value: T): void {}

  // 删除最大/最小
  extract(): void {}

  peek(): T {
    return this.data[0];
  }
  size(): number {
    return this.data.length;
  }
  isEmpty(): boolean {
    return this.data.length === 0;
  }
  buildHeap(list: unknown[]): void {}
}

const heap = new Heap();

insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private heapify_up() {
  let index = this.length - 1;
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2);
    // 上滤判断值的位置
    if (this.data[index] <= this.data[parentIndex]) break;
    this.swap(index, parentIndex);
    index = parentIndex;
  }
}
insert(value: T): void {
  // 添加数据到data
  this.data.push(value);
  this.length++;
  this.heapify_up();
}

extract

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
private heapify_down() {
    let index = 0;

    while (2 * index + 1 < this.length) {
      // 判断左右子节点谁大
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = leftChildIndex + 1;
      let largeIndex = leftChildIndex;
      if (
        rightChildIndex < this.length &&
        this.data[rightChildIndex] > this.data[leftChildIndex]
      )
        largeIndex = rightChildIndex;
      // 判断首位是否大于左右子节点中较大的一个
      if (this.data[index] >= this.data[largeIndex]) break;

      this.swap(index, largeIndex);
      index = largeIndex;
    }
  }
  extract(): T | null {
    if (this.length === 0) return null;
    if (this.length === 1) {
      this.length--;
      return this.data.pop()!;
    }
    // 提取首位元素，注意不要shift()
    const topValue = this.data[0];

    // 末尾元素提到首位
    this.data[0] = this.data.pop()!;

    this.heapify_down();
    this.length--;
    return topValue;
  }

buildHeap

原地建堆” （In-place heap construction.）是指建立堆的过程中，不使用额外的内存空间，直接在原有数组上进行操作。

1
2
3
4
5
6
7
8
9
buildHeap(list: T[]) {
    this.data = list;
    this.length = list.length;

    let start = Math.floor((this.length - 1) / 2);
    for (let i = start; i >= 0; i--) {
      this.heapify_down(i);
    }
  }

最终实现（最大堆）

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
import IHeap from "./IHeap";
class Heap<T> implements IHeap<T> {
  private data: T[] = [];
  private length: number = 0;

  constructor(arr: T[] = []) {
    this.buildHeap(arr);
  }
  // 工具方法
  swap(i: number, j: number) {
    // let temp = this.data[i];
    // this.data[i] = this.data[j];
    // this.data[j] = temp;
    [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
  }
  private heapify_up() {
    let index = this.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      // 上滤判断值的位置
      if (this.data[index] <= this.data[parentIndex]) break;
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }
  //插入
  insert(value: T): void {
    // 添加数据到data
    this.data.push(value);
    this.length++;
    this.heapify_up();
  }
  private heapify_down(start: number = 0) {
    let index = start;

    while (2 * index + 1 < this.length) {
      // 判断左右子节点谁大
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = leftChildIndex + 1;
      let largeIndex = leftChildIndex;
      if (
        rightChildIndex < this.length &&
        this.data[rightChildIndex] > this.data[leftChildIndex]
      )
        largeIndex = rightChildIndex;
      // 判断首位是否大于左右子节点中较大的一个
      if (this.data[index] >= this.data[largeIndex]) break;

      this.swap(index, largeIndex);
      index = largeIndex;
    }
  }
  // 删除
  extract(): T | null {
    if (this.length === 0) return null;
    if (this.length === 1) {
      this.length--;
      return this.data.pop()!;
    }
    // 提取首位元素，注意不要shift()
    const topValue = this.data[0];

    // 末尾元素提到首位
    this.data[0] = this.data.pop()!;

    this.heapify_down();
    this.length--;
    return topValue;
  }
  traverse() {
    console.log(this.data.join("-"));
  }
  peek(): T {
    return this.data[0];
  }
  size(): number {
    return this.data.length;
  }
  isEmpty(): boolean {
    return this.data.length === 0;
  }
  buildHeap(list: T[]): void {
    this.data = list;
    this.length = list.length;
    let start = Math.floor((this.length - 1) / 2);
    for (let i = start; i >= 0; i--) {
      this.heapify_down(i);
    }
  }
}

const heap = new Heap();

heap.insert(19);
heap.insert(100);
heap.insert(36);
heap.insert(17);
heap.insert(3);
heap.insert(25);
heap.insert(1);
heap.insert(2);
heap.insert(7);

heap.traverse();
console.log(heap.extract());
console.log(heap.extract());
heap.traverse();
const arr = [2, 7, 1, 25, 3, 17, 36, 19, 100];
heap.buildHeap(arr);
console.log(arr);