基础数据结构(七):堆结构 Heap(TS版)

简介: 基础数据结构(七):堆结构 Heap(TS版)

原文来自 我的个人博客

1. 认识堆结构

  1. 堆是一种特殊的完全二叉树
  2. 所有的节点都大于等于(大顶堆)小于等于(小顶堆) 他的子节点
  3. js 中通常使用数组表示堆

    1. 左侧子节点的位置 2 * index + 1
    2. 右侧子节点的位置 2 * index + 2
    3. 父节点的位置 (index - 1)/ 2

image.png

2.堆的应用

  1. 堆能快速高效的找出最大值和最小值 O(1)
  2. 找出第 k最大(小)元素

    1. 构建一个最小堆,并将元素依次插入堆中
    2. 当堆的容量超过 K,就删除堆顶
    3. 插入结束后,堆顶就是第 K 个最大元素

3. 堆结构的设计

接下来,让我们对堆结构进行设计,看看需要有哪些属性和方法。

堆结构常见的属性:

  1. data:存储堆结构的元素,通常使用数组来实现
  2. size:堆中当前元素的数量

堆结构常见的方法

  1. insert(value):在堆中插入一个新元素
  2. extract/delete():从堆中删除最大/最小元素
  3. peek():返回堆中的最大/最小元素
  4. isEmpty():判断堆是否为空
  5. buildHeap(list):通过一个列表来构造堆

明确了这些属性和方法之后,让我们来封装一个堆结构吧

4. 堆结构的封装

我们这里以最大堆为例

4.1 基础框架 v1 版

class Heap<T> {
  // 属性
  data: T[] = [];
  private length: number = 0;

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

  insert(value: T) {}

  extract(): T | undefined {
    return undefined;
  }

  peek(): T | undefined {
    return this.data[0];
  }

  size() {
    return this.length;
  }

  isEmpty() {
    return this.length === 0;
  }

  buildHeap(arr: T[]) {}
}

在上面的代码中,我们封装了一个 Heap 类作为堆的结构,在里面定义了一些属性和方法,这些属性和方法都是第三章中讲到的。

4.2 添加 insert 方法 v2 版

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

  1. 因为每次插入元素后,需要对堆进行重构,以维护最大堆的性质
  2. 这种策略叫上滤
// 方法
insert(value: T) {
  // 1. 将元素放到数组的尾部
  this.data.push(value);
  this.length++;

  // 2. 维护最大堆的特性(最后位置的元素需要进行上滤操作)
  this.heapify_up();
}

private heapify_up() {
  let index = this.length - 1;
  let parentIndex = Math.floor((index - 1) / 2);
  while (index > 0) {
    if (this.data[index] <= this.data[parentIndex]) {
      break;
    }

    this.swap(index, parentIndex);

    index = parentIndex;
  }
}

在上面的代码中,我们新定义了一个私有方法 heapify_up,这是一个维护最大堆特性的方法。

4.3 添加 extract 方法 v3 版

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

  1. 因为你每次删除元素后,需要对堆进行重构,以维护最大堆的特性
  2. 这种向下替换元素的策略叫做下滤
private heapify_down(index: number) {
  while (2 * index + 1 < this.length) {
    // 1. 找到左右子节点
    let leftChildIndex = 2 * index + 1;
    let rightChildIndex = leftChildIndex + 1;

    // 2. 找到左右子节点节点较大的值
    let largeIndex = leftChildIndex;
    if (rightChildIndex < this.length && this.data[rightChildIndex] > this.data[leftChildIndex]) {
      largeIndex = rightChildIndex;
    }
    // 3. 较大的值和 index 位置进行比较
    if (this.data[index] >= this.data[largeIndex]) {
      break;
    }
    // 4. 交换位置
    this.swap(index, largeIndex);
    index = largeIndex;
  }
}

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.heapify_down(0);

  return topValue;
}

在上面的代码中定义了一个私有方法 heapify_down,这个方法是用来维护最大堆的特性的(下滤操作)

4.4 添加 buildHeap 方法 v4 版

buildHeap 方法用于原地建堆,即指在建立堆的过程中,不使用额外的内存空间,直接在原有数组还是那个进行操作。

constructor(arr: T[]) {
  this.buildHeap(arr)
}

buildHeap(arr: T[]) {
  this.data = arr;
  this.length = arr.length;

  let start = Math.floor((this.length - 1) / 2);
  for (let i = start; i >= 0; i--) {
    this.heapify_down(i);
  }
}
相关文章
|
17天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
53 1
|
18天前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
18天前
探索顺序结构:栈的实现方式
探索顺序结构:栈的实现方式
|
20天前
|
存储 算法 Java
【用Java学习数据结构系列】用堆实现优先级队列
【用Java学习数据结构系列】用堆实现优先级队列
28 0
|
22天前
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现
|
24天前
【数据结构】大根堆和小根堆
【数据结构】大根堆和小根堆
18 0
|
25天前
|
存储 算法 搜索推荐
数据结构--堆的深度解析
数据结构--堆的深度解析
|
18天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
18天前
初步认识栈和队列
初步认识栈和队列
44 10
|
12天前
数据结构(栈与列队)
数据结构(栈与列队)
14 1