CAI

# 堆（Heap）

有时候需要按照优先级来管理一些数据的特殊队列，而不是按照队列的元素进入的先后顺序访问数据。

这种特殊队列描述为： 优先队列(Priority Queue)

例如：CPU 任务进程按照优先级进行判断那些进程优先执行。网络 QOS 按照预定义的一些优先级控制流量输入输出等等。。

# 不同实现优先队列的数据结构对比

数据结构 插入 删除 删除后调整位置
数组 O(1) O(n) O(n)
链表 O(1) O(n) O(1)
有序数组 O(n)或者 O(log2 n) O(n) O(1)
有序链表 O(n) O(1) O(1)
二叉搜索树 取决树的高度 取决树的高度 -

  • 数组

    1. 插入：总是在数组尾部插入。效率约等于 O(1)
    2. 删除：查找最大或早小关键字，效率约等于 O(n)；
    3. 删除元素，需要进行元素移动，效率约等于 O(n);

  • 链表

    1. 插入：总是在链表头部插入，效率约等于 O(1)
    2. 删除：查找最大或早小关键字，效率约等于 O(n)；
    3. 删除节点，元素不需要移动，改变指针即可： O(1)

  • 有序数组：

    1. 插入： 找到合适位置，效率约等于 O(n)或者 O(log2 n)
    2. 插入操作需要将元素移动并插入，效率约等于 O(n)
    3. 删除： 删除最后一个元素，效率约等于 O(1)

  • 有序链表：

    1. 插入：找到合适位置，效率约等于 O(n)
    2. 插入找到合适位置后需要进行元素操作，效率约等于 O(1)
    3. 删除： 第一个元素或者最后一个元素，效率约等于 O(1)

  • 二叉搜索树：

    1. 搜索树插入跟树的高度有关，效率约等于 O(log2 n)
    2. 删除： 最大值在最右边，最小值在最左边，跟树的高度有关。效率约等于 O(log2 n)
    3. 问题： 如果每次都删除最大值，或者最小值。二叉搜索树会发生倾斜。这样效率不再是一样。

# Heap 实现

思路

可以安排一种二叉树结构，最大值(最大堆：MaxHeap)或者最小值（最小堆：MinHeap）总是在树根上。

需要删除时候，只要删除树根即可！

但是需要将二叉树数据分配均匀， 可以用完全二叉树来构造堆。

任何节点值都比左右子树值大！

操作概念

shiftUP 上推操作：一个正常的堆，任何父元素优先级都大于左右子树，如果插入了一个新的元素，会导致这种平衡打破。新元素位于最后一位，这是需要一次跟父元素对比优先级，进行位置交换，直到满足堆的条件为止。这种情况新元素一直向上对比操作就称为 shiftUP

shiftDOWN： 与 shiftUP 同理，新元素位于第一个元素，一次向下进行匹配对比，直到满足堆的条件为止。

# 最大堆实现

通过完全二叉树构建，数据容器为数组。

# 最大堆操作集

  1. 创建空的最大堆
  2. 判断是否已满
  3. 插入元素到最大堆
  4. 判断最大堆是否为空
  5. 返回最大堆中最大元素

# 最大堆基本结构及创建

class Heap {
  constructor(MaxSize = 10) {
    this.data = [];
    this.size = 0;
    this.capacity = MAXSIZE;
    // 哨兵用于判断
    this.data[0] = Number.MAX_VALUE;
  }
}

# 最大堆的插入

完全二叉树插入最后一位，同时需要进行调整以满足最大堆的要求。将最新插入值与父树值对比，最大值作为父树的值。依次向上判断，直到第一位为止。

  • shiftDOWN 操作：
isFull() {
  return this.size === this.capacity;
}

insert(data) {
  if (this.isFull()) {
    console.log("heap is full!");
    return;
  }

  let i = ++this.size;
  // 依次判断根节点是否小于插入值，如果小，则替换位置。
  for (; this.data[Math.floor(i / 2)] < data; i = Math.floor(i / 2)) {
    this.data[i] = this.data[Math.floor(i / 2)];
  }
  this.data[i] = data;
}

# 最大堆的删除

删除永远都是删除整个完全二叉树的树根，即第一位。删除后需要找一位替代者，将最后一位值替代树根值，然后向下调整比较，最大值作为树根的值。

  • shiftDOWN 操作
isEmpty() {
  return this.size === 0;
}
deleteMax() {
  if (this.isEmpty()) {
    console.log("heap is empty!");
    return;
  }
  // 删除最大值，第一位
  const MAXITEM = this.data[1];

  // 获取最后一个元素值，将最后一个元素移动到第一位替代删除掉的值。
  this.data[1] = this.data[this.size--];

  // 释放内存空间
  this.data.pop();
  // 记录最后一个元素值最新的索引号。
  let lastIndex = 1;

  // 存储最新与元素比较索引值。
  let child = 1;
  for (; lastIndex * 2 <= this.size; lastIndex = child) {
    // 左子树为2n，右子树为2n+1
    child = lastIndex * 2;

    // 获取最新判断值
    const tmp = this.data[lastIndex];

    // 获取左右子树最大值，只对比最大值进行调整。
    if (this.data[child] < this.data[child + 1]) child++;

    // 如果调整值小于子树，则将子树提升至父树位置。
    if (tmp < this.data[child]) {
      this.data[lastIndex] = this.data[child];
      this.data[child] = tmp;
    }
  }
  return MAXITEM;
}

# 最大堆的建立

给出 N 个元素，按照最大堆要求进行存放在数组中。例如，排序可以通过建立最大堆方式实现。

  • 方法一：通过插入操作，将元素一个个插入到新的堆中，进行建立操作。时间复杂度为 O(NlogN)

  • 方法二：在线性时间复杂度下建立堆；将 n 个元素按输入顺序存放，先满足完全二叉树的结构特性，然后调整各节点的位置，以满足堆的有序特性。

  • shiftDOWN 操作

make(data) {
  if (!Array.isArray(data)) return;
  // 初始化
  this.data = [...this.data, ...data];
  this.size += data.length;

  for (let i = this.size; i > 1; i--) {
    let childIndex;
    let parentIndex = Math.floor(i / 2);
    for (; parentIndex * 2 <= this.size; parentIndex = childIndex) {
      const tmp = this.data[parentIndex];
      childIndex = parentIndex * 2;
      if (this.data[childIndex] < this.data[childIndex + 1]) childIndex++;
      if (tmp < this.data[childIndex]) {
        this.data[parentIndex] = this.data[childIndex];
        this.data[childIndex] = tmp;
      }
    }
  }
}

# 示例代码

/**
 * 堆操作
 *
 * compare: Function 比较操作，可以用于最大堆或最小堆等建立
 *
 * data: T[] 堆初始化数据
 */
class Heap<T> {
  private size: number = 0;
  constructor(private data: T[], private compare: (a: T, b: T) => boolean) {
    this.size = this.data.length;
  }

  /**
   * 返回堆大小
   */
  public getSize(): number {
    return this.size;
  }

  /**
   * 判断堆是否为空
   */
  public isEmpty(): boolean {
    return this.size === 0;
  }

  /**
   * 添加新元素
   * @param value 添加的元素
   */
  public add(value: T) {
    this.data.push(value);
    this.size++;
    // 增加元素进行shiftUP 操作
    this._shiftUP(this.getSize() - 1);
  }

  /**
   * 查找优先级最高元素
   */
  public findMax(): T | undefined {
    if (this.getSize() === 0) return;
    return this.data[0];
  }

  /**
   * 队首进行出队（优先级最高）
   */
  public extractMax(): T {
    // 获取队首
    let ret = this.findMax();
    // 交换队尾和队首
    this._swap(0, this.getSize() - 1);
    // 移除队尾，交换后的队尾元素
    this.data.pop();
    this.size--;
    // 新队首进行shiftDOWN调整
    this._siftDOWN(0);
    return ret;
  }

  toString() {
    console.log(this.data);
  }

  /**
   * 交换两个元素位置
   * @param i 元素索引
   * @param j 元素索引
   */
  private _swap(i: number, j: number) {
    [this.data[i], this.data[j]] = [this.data[j], this.data[i]];
  }

  /**
   * 返回父元素索引值
   * @param index 索引
   */
  private _parent(index: number) {
    return Math.floor((index - 1) / 2);
  }

  /**
   * 返回指定索引左子树的索引值
   * @param index 索引
   */
  private _leftChild(index: number) {
    return 2 * index + 1;
  }

  /**
   * 返回指定索引的右子树索引值
   * @param index 索引
   */
  private _rightChild(index: number) {
    return 2 * index + 2;
  }

  /**
   * 将指定索引的值进行 shiftUP 调整
   * @param k 索引值
   */
  private _shiftUP(k: number) {
    // shiftUP 调整操作
    while (k > 0 && this.compare(this.data[k], this.data[this._parent(k)])) {
      this._swap(k, this._parent(k));
      k = this._parent(k);
    }
  }

  /**
   * 将指定索引的值进行 shiftDOWN 调整
   * @param k 索引值
   */
  private _siftDOWN(k: number) {
    // shiftDOWN 调整操作
    // 先判断左子树，然后判断右子树，那个优先级高操作哪个子树
    while (this._leftChild(k) < this.size) {
      let j = this._leftChild(k);

      if (
        this._rightChild(k) < this.size &&
        this.compare(this.data[this._rightChild[k]], this.data[j])
      ) {
        j++;
      }

      // 正常无需调整
      if (this.compare(this.data[k], this.data[j])) return;
      // 交换位置
      this._swap(k, j);
      // 继续下一层对比操作
      k = j;
    }
  }
}
上次更新: 9/8/2020, 12:29:29 AM