堆结构

认识堆结构

堆是也是一种非常常见的数据结构，但是相对于前面的数据结构来说，要稍微难理解一点

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

• 堆可以进行很多分类，但是平时使用的基本都是二叉堆
• 二叉堆又可以划分为最大堆和最小堆

最大堆和最小堆：

• 最小堆: 堆中每一个节点都小于等于 (<=) 它的子节点
• 最大堆: 堆中每一个节点都大于等于 (>=) 它的子节点

堆结构意义

但是这个堆东西有什么意义呢？

• 对于每一个新的数据结构，我们都需要搞清楚为什么需要它，这是我们能够记住并且把握它的关键
• 它到底帮助我们解决了什么问题？

如果有一个集合，我们希望获取其中的最大值或者最小值，有哪些方案呢？

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

堆结构规律

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

• Top k 问题是指在一组数据中，找出最前面的 K 个最大/最小的元素
• 常用的解决方案有使用排序算法、快速选择算法、堆结构等

但是我们还是不知道具体长什么样子，以及它是如何实现出来的：

• 二叉堆用树形结构表示出来是 一颗完全二叉树
• 通常在实现的时候我们底层会 使用数组来实现

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

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

实现堆结构

堆结构设计

常见的属性：

• data：存储堆中的元素，通常使用数组来实现
• size：堆中当前元素的数量

常见的方法：

• insert(value)：在堆中插入一个新元素
• extract/delete()：从堆中删除最大/最小元素
• peek()：返回堆中最大/最小元素
• isEmpty()：判断堆是否为空
• build_heap(list)：通过一个列表类构造堆

可视化数据结构网站

• https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
• https://visualgo.net/zh
• http://btv.melezinek.cz

封装堆结构

堆结构里面包含了两个属性：data 和 size

• data 是一个泛型数组，存储堆中的元素
• size 是当前堆中元素的数量

再封装 swap 方法用于交换两个元素的位置

class Heap<T> {
  private data: T[] = []
  private length: number = 0
  private swap(i: number, j: number) {
    const temp = this.data[i]
    this.data[i] = this.data[j]
    this.data[j] = temp
  }
  peek(): T | undefined {
    return this.data[0]
  }
  size() {
    return this.length
  }
  isEmpty() {
    return this.length === 0
  }
}

堆结构新增元素

如果你想实现一个最大堆，那么可以从实现 insert 方法开始

• 因为每次插入元素后，需要对堆进行重构，以维护最大堆的性质
• 这种策略叫做上滤 (percolate up，percolate /ˈpɜːrkəleɪt/ 是过滤的意思)

class Heap<T> {
  insert(value: T) {
    // 1.将元素放到数组的尾部
    this.data.push(value)
    this.length++
    // 2.维护最大堆的特性：上滤操作
    this.percolateUp()
  }
  private percolateUp() {
    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
    }
  }
}

堆结构删除元素

删除操作也需要考虑在删除元素后的操作：

• 因为每次删除元素后，需要对堆进行重构，以维护最大堆的性质
• 这种向下替换元素的策略叫作下滤 (percolate down)

class Heap<T> {
  extract(): T | undefined {
    // 1.判断元素个数为0或1的情况
    if (this.length === 0) return undefined
    if (this.length === 1) {
      this.length--
      return this.data.pop()!
    }
    // 2.提取并且需要返回的最大值
    const topValue = this.data[0]
    this.data[0] = this.data.pop()!
    this.length--
    // 3.维护最大堆的特性：下滤操作
    this.percolateDown()
    return topValue
  }
  private percolateDown() {
    // 1.定义索引位置
    let index = 0
    while (2 * index + 1 < this.length) {
      // 2.找到左右子节点
      let leftChildIndex = 2 * index + 1
      let rightChildIndex = leftChildIndex + 1
      // 3.找到左右子节点较大的值
      let largeIndex = leftChildIndex
      if (
        rightChildIndex < this.length &&
        this.data[rightChildIndex] > this.data[leftChildIndex]
      ) {
        largeIndex = rightChildIndex
      }
      // 4.较大的值和index位置进行比较
      if (this.data[index] >= this.data[largeIndex]) {
        break
      }
      // 5.交换位置
      this.swap(index, largeIndex)
      index = largeIndex
    }
  }
}

原地建堆

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

class Heap<T> {
  constructor(arr: T[] = []) {
    if (arr.length === 0) return
    this.buildHeap(arr)
  }
  buildHeap(arr: T[]) {
    // 1.使用arr的值：数组长度
    this.data = arr
    this.length = arr.length
    // 2.从第一个非叶子节点，开始进行下滤操作
    const start = Math.floor((this.length - 1) / 2)
    for (let i = start; i >= 0; i--) {
      this.percolateDown(i)
    }
  }
}

Heap完整代码

class Heap<T> {
  private data: T[] = []
  private length: number = 0
  private isMax: boolean
  constructor(arr: T[] = [], isMax = true) {
    this.isMax = isMax
    if (arr.length === 0) return
    this.buildHeap(arr)
  }
  private swap(i: number, j: number) {
    const temp = this.data[i]
    this.data[i] = this.data[j]
    this.data[j] = temp
  }
  private compare(i: number, j: number) {
    if (this.isMax) {
      return this.data[i] >= this.data[j]
    } else {
      return this.data[i] <= this.data[j]
    }
  }
  insert(value: T) {
    // 1.将元素放到数组的尾部
    this.data.push(value)
    this.length++
    // 2.维护最大堆的特性（最后位置的元素需要进行上滤操作）
    this.percolateUp()
  }
  private percolateUp() {
    let index = this.length - 1
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2)
      if (this.compare(parentIndex, index)) {
        break
      }
      this.swap(index, parentIndex)
      index = parentIndex
    }
  }
  extract(): T | undefined {
    // 1.判断元素个数为0或1的情况
    if (this.length === 0) return undefined
    if (this.length === 1) {
      this.length--
      return this.data.pop()!
    }
    // 2.提取并且需要返回的最大值
    const topValue = this.data[0]
    this.data[0] = this.data.pop()!
    this.length--
    // 3.维护最大堆的特性：下滤操作
    this.percolateDown(0)
    return topValue
  }
  private percolateDown(start: number) {
    // 1.定义索引位置
    let index = start
    while (2 * index + 1 < this.length) {
      // 2.找到左右子节点
      let leftChildIndex = 2 * index + 1
      let rightChildIndex = leftChildIndex + 1
      // 3.找到左右子节点较大的值
      let largeIndex = leftChildIndex
      if (
        rightChildIndex < this.length &&
        this.compare(rightChildIndex, leftChildIndex)
      ) {
        largeIndex = rightChildIndex
      }
      // 4.较大的值和index位置进行比较
      if (this.compare(index,largeIndex)) {
        break
      }
      // 5.交换位置
      this.swap(index, largeIndex)
      index = largeIndex
    }
  }
  peek(): T | undefined {
    return this.data[0]
  }
  size() {
    return this.length
  }
  isEmpty() {
    return this.length === 0
  }
  buildHeap(arr: T[]) {
    // 1.使用arr的值：数组长度
    this.data = arr
    this.length = arr.length
    // 2.从第一个非叶子节点，开始进行下滤操作
    const start = Math.floor((this.length - 1) / 2)
    for (let i = start; i >= 0; i--) {
      this.percolateDown(i)
    }
  }
}