JavaScript数据结构与算法（十一）二叉堆

MartinHan 发布于2019-08-26 10:58 / 3008人阅读

摘要：二叉堆数据结构是一种特殊的二叉树，他能高效快速的找出最大值和最小值，常应用于优先队列和著名的堆排序算法中。

二叉堆数据结构是一种特殊的二叉树，他能高效、快速的找出最大值和最小值，常应用于优先队列和著名的堆排序算法中。

二叉堆

二叉堆有以下两个特性：

是一颗完全二叉树，表示数的每一层都有左侧和右侧子节点（除最后一层的叶节点），并且最后一层的叶节点尽可能是左侧子节点

二叉堆不是最小堆就是最大堆，所有节点都大于等于（最大堆）或者小于等于（最小堆）每个他的子节点。

创建最小堆类

class MinHeap {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    this.heap = [];
  }
}

二叉堆的数组表示

    static getLeftIndex(index) {
    return (2 * index) + 1;
  }

  static getRightIndex(index) {
    return (2 * index) + 2;
  }

  static getParentIndex(index) {
    if (index === 0) {
      return undefined;
    }
    return Math.floor((index - 1) / 2);
  }

  size() {
    return this.heap.length;
  }

  isEmpty() {
    return this.size() <= 0;
  }

  clear() {
    this.heap = [];
  }

查找二叉堆最小值或者最大值

 findMinimum() {
    return this.isEmpty() ? undefined : this.heap[0];
  }

交换函数实现

function swap(array, a, b) {
  /* const temp = array[a];
  array[a] = array[b];
  array[b] = temp; */
  [array[a], array[b]] = [array[b], array[a]];
}

向堆中插入新值

insert(value) {
    if (value != null) {
      const index = this.heap.length;
      this.heap.push(value);
      this.siftUp(index);
      return true;
    }
    return false;
  };
//上移操作
siftUp(index) {
    let parent = this.getParentIndex(index);
    while (
      index > 0
      && this.compareFn(this.heap[parent], this.heap[index]) === Compare.BIGGER_THAN
    ) {
      swap(this.heap, parent, index);
      index = parent;
      parent = this.getParentIndex(index);
    }
  }

二叉堆中导出最大值或最小值

extract() {
    if (this.isEmpty()) {
      return undefined;
    }
    if (this.size() === 1) {
      return this.heap.shift();
    }
    const removedValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.siftDown(0);
    return removedValue;
  };
//下移操作
 siftDown(index) {
    let element = index;
    const left = MinHeap.getLeftIndex(index);
    const right = this.getRightIndex(index);
    const size = this.size();
    if (
      left < size
      && this.compareFn(this.heap[element], this.heap[left]) === Compare.BIGGER_THAN
    ) {
      element = left;
    }
    if (
      right < size
      && this.compareFn(this.heap[element], this.heap[right]) === Compare.BIGGER_THAN
    ) {
      element = right;
    }
    if (index !== element) {
      swap(this.heap, index, element);
      this.siftDown(element);
    }
  }

创建最大堆类

class MaxHeap extends MinHeap {
  constructor(compareFn = defaultCompare) {
    super(compareFn);
    this.compareFn = compareFn;
    this.compareFn = reverseCompare(compareFn);
  }
}

其他操作跟最小堆类一样，这里就不多加赘述。

堆排序算法

heapify(array) {
    if (array) {
      this.heap = array;
    }
    const maxIndex = Math.floor(this.size() / 2) - 1;
    for (let i = 0; i <= maxIndex; i++) {
      this.siftDown(i);
    }
    return this.heap;
  };
 getAsArray() {
    return this.heap;
  };
//构建最大堆函数
function buildMaxHeap(array, compareFn) {
    for (let i = Math.floor(array.length / 2);i >= 0; i -= 1){
      heapify(array, i, array.length, compareFn);
      return array;
    }
  }
//堆排序算法实现
function heapSort(array, compareFn = defaultCompare) {
  let heapSize = array.length;
  //用数组创建一个最大堆用作源数据
  buildMaxHeap(array, compareFn);
  while(heapSize > 1){
    //创建最大堆后，最大的值会被存储在堆的第一个位置，我们将它替换为堆的最后一个值，将堆的大小-1
    swap(array, 0, --heapSize);
    //将堆的根节点下移并重复步骤2直到堆的大小为1
    heapify(array, 0, heapSize, compareFn);
  }
  return array;
}

云服务器 GPU云服务器二叉堆二叉树算法最优二叉树算法图算法与数据结构

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/106917.html

数据结构与算法学习笔记 - 优先队列、二叉堆、左式堆

摘要：模型优先队列是允许至少下列两种操作的数据结构以及找出返回并删除优先队列中最小的元素。左式堆也是二叉树，左式堆和二叉堆的唯一区别是左式堆不是理想平衡，而实际上趋向于非常不平衡。事实上，沿左式堆的右路径是该堆中的最短路径。 6.1 模型优先队列是允许至少下列两种操作的数据结构：insert 以及 deleteMin（找出、返回并删除优先队列中最小的元素）。 insert 操作等价于 en...

SunZhaopeng 2019-08-14 14:05 评论0 收藏0
算法笔记-二叉堆

摘要：二叉堆的概念二叉堆是一种特殊的二叉树。二叉堆分为两种最大堆和最小堆，最大堆的父节点一定大于其子节点根节点最大，最小堆的父节点小于其子节点根节点最小。这是我对二叉堆的理解，如有不对，欢迎指正，我会立即修改，谢谢。二叉堆的概念二叉堆是一种特殊的二叉树。二叉树是每个节点只有两个子节点的树（应该都懂吧）。二叉堆分为两种：最大堆和最小堆，最大堆的父节点一定大于其子...

MrZONT 2019-08-15 18:09 评论0 收藏0
Python数据结构——二叉堆的实现

摘要：二叉堆的有趣之处在于，其逻辑结构上像二叉树，却是用非嵌套的列表来实现。二叉堆结构性质为了更好地实现堆，我们采用二叉树。图完全二叉树有意思的是我们用单个列表就能实现完全树。下列所示的代码是完全二叉堆的实现。优先队列的二叉堆实现在前面的章节里我们学习了先进先出（FIFO）的数据结构：队列（Queue）。队列有一种变体叫做优先队列（Priority Queue）。优先队列的出队（Dequ...

stackfing 2019-07-24 18:19 评论0 收藏0
PHP面试：说下什么是堆和堆排序？

摘要：一个常见的例子就是优先队列，还有排序算法之一的堆排序。另外我们还将学习堆排序，并将使用实现堆。堆排序在堆排序中，我们需要用给定的值构建一个一个堆。伪代码如下从上面的伪代码可以看到，堆排序的第一步就是构建一个堆。堆是什么？堆是基于树抽象数据类型的一种特殊的数据结构，用于许多算法和数据结构中。一个常见的例子就是优先队列，还有排序算法之一的堆排序。这篇文章我们将讨论堆的属性、不同类型的堆...

twohappy 2019-07-01 10:32 评论0 收藏0