【从蛋壳到满天飞】JS 数据结构解析和算法实现-堆和优先队列（二）

天堂可还好
470 阅读16分钟

思维导图

前言

【从蛋壳到满天飞】JS 数据结构解析和算法实现，全部文章大概的内容如下： Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜索树)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(优先队列)、SegmentTree(线段树)、Trie(字典树)、UnionFind(并查集)、AVLTree(AVL 平衡树)、RedBlackTree(红黑平衡树)、HashTable(哈希表)

源代码有三个：ES6（单个单个的 class 类型的 js 文件） | JS + HTML（一个 js 配合一个 html）| JAVA (一个一个的工程)

全部源代码已上传 github，点击我吧，光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。

本文章适合 对数据结构想了解并且感兴趣的人群，文章风格一如既往如此，就觉得手机上看起来比较方便，这样显得比较有条理，整理这些笔记加源码，时间跨度也算将近半年时间了，希望对想学习数据结构的人或者正在学习数据结构的人群有帮助。

堆的另外两个操作，Heapify 和 replace

  1. 从理论上讲这两个操作
    1. 可以使用之前堆中的操作来组合实现出来，
    2. 但是这两个操作是比较常用的，
    3. 而且可以通过对他们内部的实现来进行优化，
    4. 所以不要使用组合原操作的方式来实现它。

replace

  1. 取出堆中最大元素之后，再放入一个新的元素。
    1. 这个过程相当于是，堆中元素总数是没有变化的，
    2. 这样的一个操作其实就是 extractMax 和 add，
    3. 但是这会导致两次的O(logn)级别的操作。
    4. 由于整个过程中堆中的元素个数并没有发生改变，
    5. 那么可以直接堆顶的元素替换成新的元素，
    6. 替换成新的元素之后，这个新的元素有可能违背了堆的性质，
    7. 那么直接进行 Sift Down 操作就可以了，
    8. 那么就只是一次O(logn)级别的操作。

heapify

  1. 将任意的一个数组整理成堆的形状
    1. 由于堆是一棵完全二叉树，所以它可以直接用一个数组来表示，
    2. 所以只要合理的交换数组中元素的位置，也可以将它整理成堆的形状，
    3. 你可以先扫描一下当前的数组，
    4. 将当前数组中所有的元素添加进这个堆所对应的对象中，
    5. 其实也就完成了这个工作，
    6. 但是还有一个更加快速的方式，这个过程就叫做 Heapify，
    7. 首先将当前数组看成一棵完全二叉树，
    8. 虽然它目标并不太可能符合堆的性质，
    9. 但是 对于这个完全二叉树，
    10. 可以从最后一个非叶子节点开始进行 Sift Down 这个操作，
    11. 也就是不断的进行下沉操作就可以了，
    12. 从后往前不断的循环进行下沉操作，
    13. 直到所有非叶子节点都符合堆的性质那就 ok 了。
  2. 定位最后一个非叶子节点所处的数组索引
    1. 这是一个很经典的面试题目，在计算机考试中也会有，
    2. 也就是用数组来表示一棵完全二叉树，
    3. 那么它最后一个或者倒数第一个非叶子节点所对应的索引是多少，
    4. 这个问题其实非常简单，只需要拿到最后一个节点的索引，
    5. 然后使用这个索引计算出它的父亲节点，
    6. 如果起始索引是从 0 开始的，
    7. 那就是这个最后一个节点的索引减去一之后再除以二取整即可，
    8. 如果起始索引是从 1 开始的，
    9. 那么就是这个最后一个节点的索引直接除以二再取整就好了。
  3. heapify 原理
    1. 从倒数第一个非叶子节点向前一直遍历，
    2. 遍历出到了第一个非叶子节点(根节点)，
    3. 也就是对每一个节点都进行了下沉操作，
    4. 然后整棵树就变成了最大堆，
    5. 这样一来就将一个普通的数组整理成了一个最大堆的形式，
    6. 从一开始就抛弃了所有的叶子节点，
    7. 那么几乎就抛弃了这棵二叉树中近一半的节点，
    8. 剩下的一半的节点进行了 Sift Down 的操作，
    9. 这比原来直接从一个空堆开始，一个一个添加元素的速度要快一点，
    10. 因为每添加一个元素都会执行一次O(logn)级别的操作。

Heapify 的 算法复杂度

  1. 将 n 个元素逐个插入到一个空堆中，算法复杂度是 O(nlogn)级别。
  2. 如果使用 heapify 的过程，算法复杂度就为 O(n)级别的。
    1. 同样把一个数组整理成堆的过程要比以逐个插入到空堆中要快一些。
    2. 其实使用 heapify 与不使用 heapify 是有一个质的提升，
    3. 这个提升是O(n)与O(nlogn)的区别。
  3. 上浮操作 Sift Up 与下沉操作 Sift Down
    1. 上浮是当前节点值与其父节点进行对比，如果当前节点大于其父节点就进行位置的交换。
    2. 下沉是当前节点值与其左右两孩子节点中最大的值的节点进行对比，
    3. 如果当前节点值比左右孩子节点最大值的那个节点值小，
    4. 那么当前节点就和那个最大值孩子节点交换位置。

代码示例

  1. (class: Myarray, class: MaxHeap, class: PerformanceTest, class: Main)

  2. Myarray

    // 自定义类
class MyArray {
   // 构造函数，传入数组的容量capacity构造Array 默认数组的容量capacity=10
   constructor(capacity = 10) {
      this.data = new Array(capacity);
      this.size = 0;
   }

   // 获取数组中的元素实际个数
   getSize() {
      return this.size;
   }

   // 获取数组的容量
   getCapacity() {
      return this.data.length;
   }

   // 判断数组是否为空
   isEmpty() {
      return this.size === 0;
   }

   // 给数组扩容
   resize(capacity) {
      let newArray = new Array(capacity);
      for (var i = 0; i < this.size; i++) {
         newArray[i] = this.data[i];
      }

      // let index = this.size - 1;
      // while (index > -1) {
      //   newArray[index] = this.data[index];
      //   index --;
      // }

      this.data = newArray;
   }

   // 在指定索引处插入元素
   insert(index, element) {
      // 先判断数组是否已满
      if (this.size == this.getCapacity()) {
         // throw new Error("add error. Array is full.");
         this.resize(this.size * 2);
      }

      // 然后判断索引是否符合要求
      if (index < 0 || index > this.size) {
         throw new Error(
            'insert error. require  index < 0 or index > size.'
         );
      }

      // 最后 将指定索引处腾出来
      // 从指定索引处开始，所有数组元素全部往后移动一位
      // 从后往前移动
      for (let i = this.size - 1; i >= index; i--) {
         this.data[i + 1] = this.data[i];
      }

      // 在指定索引处插入元素
      this.data[index] = element;
      // 维护一下size
      this.size++;
   }

   // 扩展 在数组最前面插入一个元素
   unshift(element) {
      this.insert(0, element);
   }

   // 扩展 在数组最后面插入一个元素
   push(element) {
      this.insert(this.size, element);
   }

   // 其实在数组中添加元素 就相当于在数组最后面插入一个元素
   add(element) {
      if (this.size == this.getCapacity()) {
         // throw new Error("add error. Array is full.");
         this.resize(this.size * 2);
      }

      // size其实指向的是 当前数组最后一个元素的 后一个位置的索引。
      this.data[this.size] = element;
      // 维护size
      this.size++;
   }

   // get
   get(index) {
      // 不能访问没有存放元素的位置
      if (index < 0 || index >= this.size) {
         throw new Error('get error. index < 0 or index >= size.');
      }
      return this.data[index];
   }

   // 扩展： 获取数组中第一个元素
   getFirst() {
      return this.get(0);
   }

   // 扩展： 获取数组中最后一个元素
   getLast() {
      return this.get(this.size - 1);
   }

   // set
   set(index, newElement) {
      // 不能修改没有存放元素的位置
      if (index < 0 || index >= this.size) {
         throw new Error('set error. index < 0 or index >= size.');
      }
      this.data[index] = newElement;
   }

   // contain
   contain(element) {
      for (var i = 0; i < this.size; i++) {
         if (this.data[i] === element) {
            return true;
         }
      }
      return false;
   }

   // find
   find(element) {
      for (var i = 0; i < this.size; i++) {
         if (this.data[i] === element) {
            return i;
         }
      }
      return -1;
   }

   // findAll
   findAll(element) {
      // 创建一个自定义数组来存取这些 元素的索引
      let myarray = new MyArray(this.size);

      for (var i = 0; i < this.size; i++) {
         if (this.data[i] === element) {
            myarray.push(i);
         }
      }

      // 返回这个自定义数组
      return myarray;
   }

   // 删除指定索引处的元素
   remove(index) {
      // 索引合法性验证
      if (index < 0 || index >= this.size) {
         throw new Error('remove error. index < 0 or index >= size.');
      }

      // 暂存即将要被删除的元素
      let element = this.data[index];

      // 后面的元素覆盖前面的元素
      for (let i = index; i < this.size - 1; i++) {
         this.data[i] = this.data[i + 1];
      }

      this.size--;
      this.data[this.size] = null;

      // 如果size 为容量的四分之一时 就可以缩容了
      // 防止复杂度震荡
      if (Math.floor(this.getCapacity() / 4) === this.size) {
         // 缩容一半
         this.resize(Math.floor(this.getCapacity() / 2));
      }

      return element;
   }

   // 扩展：删除数组中第一个元素
   shift() {
      return this.remove(0);
   }

   // 扩展： 删除数组中最后一个元素
   pop() {
      return this.remove(this.size - 1);
   }

   // 扩展： 根据元素来进行删除
   removeElement(element) {
      let index = this.find(element);
      if (index !== -1) {
         this.remove(index);
      }
   }

   // 扩展： 根据元素来删除所有元素
   removeAllElement(element) {
      let index = this.find(element);
      while (index != -1) {
         this.remove(index);
         index = this.find(element);
      }

      // let indexArray = this.findAll(element);
      // let cur, index = 0;
      // for (var i = 0; i < indexArray.getSize(); i++) {
      //   // 每删除一个元素 原数组中就少一个元素，
      //   // 索引数组中的索引值是按照大小顺序排列的，
      //   // 所以 这个cur记录的是 原数组元素索引的偏移量
      //   // 只有这样才能够正确的删除元素。
      //   index = indexArray.get(i) - cur++;
      //   this.remove(index);
      // }
   }

   // 新增： 交换两个索引位置的变量 2018-11-6
   swap(indexA, indexB) {
      if (
         indexA < 0 ||
         indexA >= this.size ||
         indexB < 0 ||
         indexB >= this.size
      )
         throw new Error('Index is Illegal.'); // 索引越界异常

      let temp = this.data[indexA];
      this.data[indexA] = this.data[indexB];
      this.data[indexB] = temp;
   }

   // @Override toString 2018-10-17-jwl
   toString() {
      let arrInfo = `Array: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
      arrInfo += `data = [`;
      for (var i = 0; i < this.size - 1; i++) {
         arrInfo += `${this.data[i]}, `;
      }
      if (!this.isEmpty()) {
         arrInfo += `${this.data[this.size - 1]}`;
      }
      arrInfo += `]`;

      // 在页面上展示
      document.body.innerHTML += `${arrInfo}<br /><br /> `;

      return arrInfo;
   }
}

  3. MaxHeap

    // 自定义二叉堆之最大堆 Heap
class MyMaxHeap {
   constructor(capacity = 10) {
      this.myArray = new MyArray(capacity);
   }

   // 添加操作
   add(element) {
      // 追加元素
      this.myArray.push(element);

      // 将追加的元素上浮到堆中合适的位置
      this.siftUp(this.myArray.getSize() - 1);
   }

   // 堆的上浮操作 -
   siftUp(index) {
      this.nonRecursiveSiftUp(index);
      // this.recursiveSiftUp(index);

      // 无论是递归还是非递归都有一个
      // 元素上浮后结束的条件 当前节点元素值 小于其父节点元素值
      // 和
      // 索引即将越界的终止条件 要上浮的元素索引 小于等于0
   }

   // 堆的上浮操作 递归算法 -
   recursiveSiftUp(index) {
      // 解决最基本的问题， 递归终止条件
      if (index <= 0) return;

      let currentValue = this.myArray.get(index);
      let parentIndex = this.calcParentIndex(index);
      let parentValue = this.myArray.get(parentIndex);

      // 递归写法
      if (this.compare(currentValue, parentValue) > 0) {
         this.swap(index, parentIndex);
         this.recursiveSiftUp(parentIndex);
      }
   }

   // 堆的上浮操作 非递归算法 -
   nonRecursiveSiftUp(index) {
      if (index <= 0) return;

      let currentValue = this.myArray.get(index);
      let parentIndex = this.calcParentIndex(index);
      let parentValue = this.myArray.get(parentIndex);

      while (this.compare(currentValue, parentValue) > 0) {
         // 交换堆中两个元素位置的值
         this.swap(index, parentIndex);

         // 交换了位置之后，元素上浮后的索引变量也要进行相应的变更
         index = parentIndex;
         // 如果索引小于等于0了 那就结束循环
         if (index <= 0) break;
         currentValue = this.myArray.get(index);
         parentIndex = this.calcParentIndex(index);
         parentValue = this.myArray.get(parentIndex);
      }
   }

   // 找到优先级最大的元素 （查找元素）操作
   findMax() {
      if (this.myArray.isEmpty())
         throw new Error('can not findMax when heap is empty.');
      return this.myArray.getFirst();
   }

   // 提取优先级最大的元素（删除元素）操作
   extractMax() {
      // 获取堆顶的元素
      let maxElement = this.findMax();

      // 获取堆底的元素
      let element = this.myArray.getLast();

      // 让堆底的元素替换掉堆顶的元素
      this.myArray.set(0, element);

      // 移除堆底的元素
      this.myArray.pop();

      // 让堆顶的元素开始下沉，从而能够正常满足堆的性质
      this.siftDown(0);

      // 返回堆顶的元素
      return maxElement;
   }

   // 堆的下沉操作 -
   siftDown(index) {
      this.nonRecursiveSiftDown(index);
      // this.recursiveSiftDown(index);
   }

   // 堆的下沉操作 递归算法
   recursiveSiftDown(index) {
      // 递归终止条件
      // 如果当前索引位置的元素没有左孩子就说也没有右孩子，
      // 那么可以直接终止，因为无法下沉
      if (this.calcLeftChildIndex(index) >= this.myArray.getSize()) return;

      let leftChildIndex = this.calcLeftChildIndex(index);
      let leftChildValue = this.myArray.get(leftChildIndex);
      let rightChildIndex = this.calcRightChildIndex(index);
      let rightChildValue = null;

      // let maxIndex = 0;
      // if (rightChildIndex >= this.myArray.getSize())
      //   maxIndex = leftChildIndex;
      // else {
      //   rightChildValue = this.myArray.get(rightChildIndex);
      //   if (this.compare(rightChildValue, leftChildValue) > 0)
      //     maxIndex = rightChildIndex;
      //   else
      //     maxIndex = leftChildIndex;
      // }

      // 这段代码是上面注释代码的优化
      let maxIndex = leftChildIndex;
      if (rightChildIndex < this.myArray.getSize()) {
         rightChildValue = this.myArray.get(rightChildIndex);
         if (this.compare(leftChildValue, rightChildValue) < 0)
            maxIndex = rightChildIndex;
      }

      let maxValue = this.myArray.get(maxIndex);
      let currentValue = this.myArray.get(index);

      if (this.compare(maxValue, currentValue) > 0) {
         // 交换位置
         this.swap(maxIndex, index);
         // 继续下沉
         this.recursiveSiftDown(maxIndex);
      }
   }

   // 堆的下沉操作 非递归算法 -
   nonRecursiveSiftDown(index) {
      // 该索引位置的元素有左右孩子节点才可以下沉，
      // 在完全二叉树中 如果一个节点没有左孩子必然没有右孩子
      while (this.calcLeftChildIndex(index) < this.myArray.getSize()) {
         let leftChildIndex = this.calcLeftChildIndex(index);
         let leftChildValue = this.myArray.get(leftChildIndex);
         let rightChildIndex = this.calcRightChildIndex(index);
         let rightChildValue = null;
         let maxIndex = leftChildIndex;

         if (rightChildIndex < this.myArray.getSize()) {
            rightChildValue = this.myArray.get(rightChildIndex);
            if (this.compare(leftChildValue, rightChildValue) < 0)
               maxIndex = rightChildIndex;
         }

         let maxValue = this.myArray.get(maxIndex);
         let currentValue = this.myArray.get(index);

         if (this.compare(maxValue, currentValue) > 0) {
            this.swap(maxIndex, index);
            index = maxIndex;
            continue;
         } else break;
      }
   }

   // 将堆顶的元素用一个新元素替换出来
   replace(element) {
      let maxElement = this.findMax();

      this.myArray.set(0, element);

      this.siftDown(0);

      return maxElement;
   }

   // 将一个数组变成一个最大堆 -
   heapify(array) {
      // 将数组中的元素添加到自定义动态数组里
      for (const element of array) this.myArray.push(element);

      // 减少一个O(n)的操作，不然性能相对来说会差一些
      // this.myArray.data = array;
      // this.myArray.size = array.length;

      // 这个动态数组满足了一棵完全二叉树的性质
      // 获取 这棵完全二叉树 最后一个非叶子节点的索引
      let index = this.calcParentIndex(this.myArray.getSize() - 1);

      // 从最后一个非叶子节点开始遍历  从后向前遍历 不停的下沉， 这个就是heapify的过程
      // for (let i = index; i >= 0; i --) { this.siftDown(i);}
      while (0 <= index) this.siftDown(index--);
   }

   // 堆中两个元素的位置进行交换
   swap(indexA, indexB) {
      this.myArray.swap(indexA, indexB);
   }

   // 辅助函数 计算出堆中指定索引位置的元素其父节点的索引 -
   calcParentIndex(index) {
      if (index === 0)
         // 索引为0是根节点，根节点没有父亲节点，小于0就更加不可以了
         throw new Error("index is 0. doesn't have parent.");
      return Math.floor((index - 1) / 2);
   }

   // 辅助函数 计算出堆中指定索引位置的元素其左孩子节点的索引 -
   calcLeftChildIndex(index) {
      return index * 2 + 1;
   }

   // 辅助函数 计算出堆中指定索引位置的元素其右孩子节点的索引 -
   calcRightChildIndex(index) {
      return index * 2 + 2;
   }

   // 比较的功能 -
   compare(elementA, elementB) {
      if (elementA === null || elementB === null)
         throw new Error("element is error. element can't compare.");
      if (elementA > elementB) return 1;
      else if (elementA < elementB) return -1;
      else return 0;
   }

   // 获取堆中实际的元素个数
   size() {
      return this.myArray.getSize();
   }

   // 返回堆中元素是否为空的判断值
   isEmpty() {
      return this.myArray.isEmpty();
   }
}

  4. PerformanceTest

    // 性能测试
class PerformanceTest {
   constructor() {}

   // 对比队列
   testQueue(queue, openCount) {
      let startTime = Date.now();

      let random = Math.random;
      for (var i = 0; i < openCount; i++) {
         queue.enqueue(random() * openCount);
      }

      while (!queue.isEmpty()) {
         queue.dequeue();
      }

      let endTime = Date.now();

      return this.calcTime(endTime - startTime);
   }

   // 对比栈
   testStack(stack, openCount) {
      let startTime = Date.now();

      let random = Math.random;
      for (var i = 0; i < openCount; i++) {
         stack.push(random() * openCount);
      }

      while (!stack.isEmpty()) {
         stack.pop();
      }

      let endTime = Date.now();

      return this.calcTime(endTime - startTime);
   }

   // 对比集合
   testSet(set, openCount) {
      let startTime = Date.now();

      let random = Math.random;
      let arr = [];
      let temp = null;

      // 第一遍测试
      for (var i = 0; i < openCount; i++) {
         temp = random();
         // 添加重复元素，从而测试集合去重的能力
         set.add(temp * openCount);
         set.add(temp * openCount);

         arr.push(temp * openCount);
      }

      for (var i = 0; i < openCount; i++) {
         set.remove(arr[i]);
      }

      // 第二遍测试
      for (var i = 0; i < openCount; i++) {
         set.add(arr[i]);
         set.add(arr[i]);
      }

      while (!set.isEmpty()) {
         set.remove(arr[set.getSize() - 1]);
      }

      let endTime = Date.now();

      // 求出两次测试的平均时间
      let avgTime = Math.ceil((endTime - startTime) / 2);

      return this.calcTime(avgTime);
   }

   // 对比映射
   testMap(map, openCount) {
      let startTime = Date.now();

      let array = new MyArray();
      let random = Math.random;
      let temp = null;
      let result = null;
      for (var i = 0; i < openCount; i++) {
         temp = random();
         result = openCount * temp;
         array.add(result);
         array.add(result);
         array.add(result);
         array.add(result);
      }

      for (var i = 0; i < array.getSize(); i++) {
         result = array.get(i);
         if (map.contains(result)) map.add(result, map.get(result) + 1);
         else map.add(result, 1);
      }

      for (var i = 0; i < array.getSize(); i++) {
         result = array.get(i);
         map.remove(result);
      }

      let endTime = Date.now();

      return this.calcTime(endTime - startTime);
   }

   // 对比堆 主要对比 使用heapify 与 不使用heapify时的性能
   testHeap(heap, array, isHeapify) {
      const startTime = Date.now();

      // 是否支持 heapify
      if (isHeapify) heap.heapify(array);
      else {
         for (const element of array) heap.add(element);
      }

      console.log('heap size:' + heap.size() + '\r\n');
      document.body.innerHTML += 'heap size:' + heap.size() + '<br /><br />';

      // 使用数组取值
      let arr = new Array(heap.size());
      for (let i = 0; i < arr.length; i++) arr[i] = heap.extractMax();

      console.log(
         'Array size:' + arr.length + '，heap size:' + heap.size() + '\r\n'
      );
      document.body.innerHTML +=
         'Array size:' +
         arr.length +
         '，heap size:' +
         heap.size() +
         '<br /><br />';

      // 检验一下是否符合要求
      for (let i = 1; i < arr.length; i++)
         if (arr[i - 1] < arr[i]) throw new Error('error.');

      console.log('test heap completed.' + '\r\n');
      document.body.innerHTML += 'test heap completed.' + '<br /><br />';

      const endTime = Date.now();
      return this.calcTime(endTime - startTime);
   }

   // 计算运行的时间，转换为 天-小时-分钟-秒-毫秒
   calcTime(result) {
      //获取距离的天数
      var day = Math.floor(result / (24 * 60 * 60 * 1000));

      //获取距离的小时数
      var hours = Math.floor((result / (60 * 60 * 1000)) % 24);

      //获取距离的分钟数
      var minutes = Math.floor((result / (60 * 1000)) % 60);

      //获取距离的秒数
      var seconds = Math.floor((result / 1000) % 60);

      //获取距离的毫秒数
      var milliSeconds = Math.floor(result % 1000);

      // 计算时间
      day = day < 10 ? '0' + day : day;
      hours = hours < 10 ? '0' + hours : hours;
      minutes = minutes < 10 ? '0' + minutes : minutes;
      seconds = seconds < 10 ? '0' + seconds : seconds;
      milliSeconds =
         milliSeconds < 100
            ? milliSeconds < 10
               ? '00' + milliSeconds
               : '0' + milliSeconds
            : milliSeconds;

      // 输出耗时字符串
      result =
         day +
         '天' +
         hours +
         '小时' +
         minutes +
         '分' +
         seconds +
         '秒' +
         milliSeconds +
         '毫秒' +
         '  <<<<============>>>>  总毫秒数：' +
         result;

      return result;
   }
}

  5. Main

    // main 函数
class Main {
   constructor() {
      this.alterLine('MaxHeap Comparison Area');
      const n = 1000000;

      const maxHeapIsHeapify = new MyMaxHeap();
      const maxHeapNotHeapify = new MyMaxHeap();
      let performanceTest1 = new PerformanceTest();

      const random = Math.random;
      let arr = [];
      let arr1 = [];

      // 循环添加随机数的值
      for (let i = 0; i < n; i++) {
         arr.push(random() * n);
         arr1.push(arr[i]);
      }

      this.alterLine('MaxHeap Is Heapify Area');
      const maxHeapIsHeapifyInfo = performanceTest1.testHeap(
         maxHeapIsHeapify,
         arr,
         true
      );
      console.log(maxHeapIsHeapifyInfo);
      this.show(maxHeapIsHeapifyInfo);

      this.alterLine('MaxHeap Not Heapify Area');
      const maxHeapNotHeapifyInfo = performanceTest1.testHeap(
         maxHeapNotHeapify,
         arr1,
         false
      );
      console.log(maxHeapNotHeapifyInfo);
      this.show(maxHeapNotHeapifyInfo);

      // this.alterLine("MyMaxHeap Replace Area");
      // const n = 20;

      // const maxHeap = new MyMaxHeap();
      // const random = Math.random;

      // // 循环添加随机数的值
      // for (let i = 0; i < n; i++)
      //   maxHeap.add(random() * n);

      // console.log("MaxHeap maxHeap size:" + maxHeap.size());
      // this.show("MaxHeap maxHeap size:" + maxHeap.size());

      // // 使用数组取值
      // let arr = [];
      // for (let i = 0; i < n ; i++)
      //   arr[i] = maxHeap.replace(0);

      // console.log("Array arr size:" + arr.length + "，MaxHeap maxHeap size:" + maxHeap.size());
      // this.show("Array arr size:" + arr.length + "，MaxHeap maxHeap size:" + maxHeap.size());
      // console.log(arr, maxHeap);
      // // 检验一下是否符合要求
      // for (let i = 1; i < n; i++)
      //   if (arr[i - 1] < arr[i]) throw new Error("error.");

      // console.log("test maxHeap completed.");
      // this.show("test maxHeap completed.");
   }

   // 将内容显示在页面上
   show(content) {
      document.body.innerHTML += `${content}<br /><br />`;
   }

   // 展示分割线
   alterLine(title) {
      let line = `--------------------${title}----------------------`;
      console.log(line);
      document.body.innerHTML += `${line}<br /><br />`;
   }
}

// 页面加载完毕
window.onload = function() {
   // 执行主函数
   new Main();
};

使用堆来实现优先队列

  1. 优先队列即可以使用普通的线性数据结构来实现
    1. 动态数组、链表。
  2. 优先队列也可以使用一个维护顺序的线性数据结构来实现
    1. 动态数组、链表。
  3. 队列的接口是完全一致的，同时它们的功能也是一样的
    1. 只不过用的底层的数据结构是不同的，
    2. 这样就会导致一些方法在时间复杂度上产生不同的效果，
    3. 在使用普通数组的时候入队这个操作是O(1)的复杂度，
    4. 但是出队的那个操作，寻找那个最大值就是O(n)的复杂度，
    5. 如果使用顺序的线性结构的时候，那会有点相反，
    6. 入队会变成O(n)的复杂度，因为要找到待插入的这个元素的正确位置，
    7. 出队会是O(1)的复杂度。

代码示例

  1. (class: Myarray, class: MaxHeap, class: MyPriorityQueue)

  2. Myarray

    // 自定义类
class MyArray {
   // 构造函数，传入数组的容量capacity构造Array 默认数组的容量capacity=10
   constructor(capacity = 10) {
      this.data = new Array(capacity);
      this.size = 0;
   }

   // 获取数组中的元素实际个数
   getSize() {
      return this.size;
   }

   // 获取数组的容量
   getCapacity() {
      return this.data.length;
   }

   // 判断数组是否为空
   isEmpty() {
      return this.size === 0;
   }

   // 给数组扩容
   resize(capacity) {
      let newArray = new Array(capacity);
      for (var i = 0; i < this.size; i++) {
         newArray[i] = this.data[i];
      }

      // let index = this.size - 1;
      // while (index > -1) {
      //   newArray[index] = this.data[index];
      //   index --;
      // }

      this.data = newArray;
   }

   // 在指定索引处插入元素
   insert(index, element) {
      // 先判断数组是否已满
      if (this.size == this.getCapacity()) {
         // throw new Error("add error. Array is full.");
         this.resize(this.size * 2);
      }

      // 然后判断索引是否符合要求
      if (index < 0 || index > this.size) {
         throw new Error(
            'insert error. require  index < 0 or index > size.'
         );
      }

      // 最后 将指定索引处腾出来
      // 从指定索引处开始，所有数组元素全部往后移动一位
      // 从后往前移动
      for (let i = this.size - 1; i >= index; i--) {
         this.data[i + 1] = this.data[i];
      }

      // 在指定索引处插入元素
      this.data[index] = element;
      // 维护一下size
      this.size++;
   }

   // 扩展 在数组最前面插入一个元素
   unshift(element) {
      this.insert(0, element);
   }

   // 扩展 在数组最后面插入一个元素
   push(element) {
      this.insert(this.size, element);
   }

   // 其实在数组中添加元素 就相当于在数组最后面插入一个元素
   add(element) {
      if (this.size == this.getCapacity()) {
         // throw new Error("add error. Array is full.");
         this.resize(this.size * 2);
      }

      // size其实指向的是 当前数组最后一个元素的 后一个位置的索引。
      this.data[this.size] = element;
      // 维护size
      this.size++;
   }

   // get
   get(index) {
      // 不能访问没有存放元素的位置
      if (index < 0 || index >= this.size) {
         throw new Error('get error. index < 0 or index >= size.');
      }
      return this.data[index];
   }

   // 扩展： 获取数组中第一个元素
   getFirst() {
      return this.get(0);
   }

   // 扩展： 获取数组中最后一个元素
   getLast() {
      return this.get(this.size - 1);
   }

   // set
   set(index, newElement) {
      // 不能修改没有存放元素的位置
      if (index < 0 || index >= this.size) {
         throw new Error('set error. index < 0 or index >= size.');
      }
      this.data[index] = newElement;
   }

   // contain
   contain(element) {
      for (var i = 0; i < this.size; i++) {
         if (this.data[i] === element) {
            return true;
         }
      }
      return false;
   }

   // find
   find(element) {
      for (var i = 0; i < this.size; i++) {
         if (this.data[i] === element) {
            return i;
         }
      }
      return -1;
   }

   // findAll
   findAll(element) {
      // 创建一个自定义数组来存取这些 元素的索引
      let myarray = new MyArray(this.size);

      for (var i = 0; i < this.size; i++) {
         if (this.data[i] === element) {
            myarray.push(i);
         }
      }

      // 返回这个自定义数组
      return myarray;
   }

   // 删除指定索引处的元素
   remove(index) {
      // 索引合法性验证
      if (index < 0 || index >= this.size) {
         throw new Error('remove error. index < 0 or index >= size.');
      }

      // 暂存即将要被删除的元素
      let element = this.data[index];

      // 后面的元素覆盖前面的元素
      for (let i = index; i < this.size - 1; i++) {
         this.data[i] = this.data[i + 1];
      }

      this.size--;
      this.data[this.size] = null;

      // 如果size 为容量的四分之一时 就可以缩容了
      // 防止复杂度震荡
      if (Math.floor(this.getCapacity() / 4) === this.size) {
         // 缩容一半
         this.resize(Math.floor(this.getCapacity() / 2));
      }

      return element;
   }

   // 扩展：删除数组中第一个元素
   shift() {
      return this.remove(0);
   }

   // 扩展： 删除数组中最后一个元素
   pop() {
      return this.remove(this.size - 1);
   }

   // 扩展： 根据元素来进行删除
   removeElement(element) {
      let index = this.find(element);
      if (index !== -1) {
         this.remove(index);
      }
   }

   // 扩展： 根据元素来删除所有元素
   removeAllElement(element) {
      let index = this.find(element);
      while (index != -1) {
         this.remove(index);
         index = this.find(element);
      }

      // let indexArray = this.findAll(element);
      // let cur, index = 0;
      // for (var i = 0; i < indexArray.getSize(); i++) {
      //   // 每删除一个元素 原数组中就少一个元素，
      //   // 索引数组中的索引值是按照大小顺序排列的，
      //   // 所以 这个cur记录的是 原数组元素索引的偏移量
      //   // 只有这样才能够正确的删除元素。
      //   index = indexArray.get(i) - cur++;
      //   this.remove(index);
      // }
   }

   // 新增： 交换两个索引位置的变量 2018-11-6
   swap(indexA, indexB) {
      if (
         indexA < 0 ||
         indexA >= this.size ||
         indexB < 0 ||
         indexB >= this.size
      )
         throw new Error('Index is Illegal.'); // 索引越界异常

      let temp = this.data[indexA];
      this.data[indexA] = this.data[indexB];
      this.data[indexB] = temp;
   }

   // @Override toString 2018-10-17-jwl
   toString() {
      let arrInfo = `Array: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
      arrInfo += `data = [`;
      for (var i = 0; i < this.size - 1; i++) {
         arrInfo += `${this.data[i]}, `;
      }
      if (!this.isEmpty()) {
         arrInfo += `${this.data[this.size - 1]}`;
      }
      arrInfo += `]`;

      // 在页面上展示
      document.body.innerHTML += `${arrInfo}<br /><br /> `;

      return arrInfo;
   }
}

  3. MaxHeap

    // 自定义二叉堆之最大堆 Heap
class MyMaxHeap {
   constructor(capacity = 10) {
      this.myArray = new MyArray(capacity);
   }

   // 添加操作
   add(element) {
      // 追加元素
      this.myArray.push(element);

      // 将追加的元素上浮到堆中合适的位置
      this.siftUp(this.myArray.getSize() - 1);
   }

   // 堆的上浮操作 -
   siftUp(index) {
      this.nonRecursiveSiftUp(index);
      // this.recursiveSiftUp(index);

      // 无论是递归还是非递归都有一个
      // 元素上浮后结束的条件 当前节点元素值 小于其父节点元素值
      // 和
      // 索引即将越界的终止条件 要上浮的元素索引 小于等于0
   }

   // 堆的上浮操作 递归算法 -
   recursiveSiftUp(index) {
      // 解决最基本的问题， 递归终止条件
      if (index <= 0) return;

      let currentValue = this.myArray.get(index);
      let parentIndex = this.calcParentIndex(index);
      let parentValue = this.myArray.get(parentIndex);

      // 递归写法
      if (this.compare(currentValue, parentValue) > 0) {
         this.swap(index, parentIndex);
         this.recursiveSiftUp(parentIndex);
      }
   }

   // 堆的上浮操作 非递归算法 -
   nonRecursiveSiftUp(index) {
      if (index <= 0) return;

      let currentValue = this.myArray.get(index);
      let parentIndex = this.calcParentIndex(index);
      let parentValue = this.myArray.get(parentIndex);

      while (this.compare(currentValue, parentValue) > 0) {
         // 交换堆中两个元素位置的值
         this.swap(index, parentIndex);

         // 交换了位置之后，元素上浮后的索引变量也要进行相应的变更
         index = parentIndex;
         // 如果索引小于等于0了 那就结束循环
         if (index <= 0) break;
         currentValue = this.myArray.get(index);
         parentIndex = this.calcParentIndex(index);
         parentValue = this.myArray.get(parentIndex);
      }
   }

   // 找到优先级最大的元素 （查找元素）操作
   findMax() {
      if (this.myArray.isEmpty())
         throw new Error('can not findMax when heap is empty.');
      return this.myArray.getFirst();
   }

   // 提取优先级最大的元素（删除元素）操作
   extractMax() {
      // 获取堆顶的元素
      let maxElement = this.findMax();

      // 获取堆底的元素
      let element = this.myArray.getLast();

      // 让堆底的元素替换掉堆顶的元素
      this.myArray.set(0, element);

      // 移除堆底的元素
      this.myArray.pop();

      // 让堆顶的元素开始下沉，从而能够正常满足堆的性质
      this.siftDown(0);

      // 返回堆顶的元素
      return maxElement;
   }

   // 堆的下沉操作 -
   siftDown(index) {
      this.nonRecursiveSiftDown(index);
      // this.recursiveSiftDown(index);
   }

   // 堆的下沉操作 递归算法
   recursiveSiftDown(index) {
      // 递归终止条件
      // 如果当前索引位置的元素没有左孩子就说也没有右孩子，
      // 那么可以直接终止，因为无法下沉
      if (this.calcLeftChildIndex(index) >= this.myArray.getSize()) return;

      let leftChildIndex = this.calcLeftChildIndex(index);
      let leftChildValue = this.myArray.get(leftChildIndex);
      let rightChildIndex = this.calcRightChildIndex(index);
      let rightChildValue = null;

      // let maxIndex = 0;
      // if (rightChildIndex >= this.myArray.getSize())
      //   maxIndex = leftChildIndex;
      // else {
      //   rightChildValue = this.myArray.get(rightChildIndex);
      //   if (this.compare(rightChildValue, leftChildValue) > 0)
      //     maxIndex = rightChildIndex;
      //   else
      //     maxIndex = leftChildIndex;
      // }

      // 这段代码是上面注释代码的优化
      let maxIndex = leftChildIndex;
      if (rightChildIndex < this.myArray.getSize()) {
         rightChildValue = this.myArray.get(rightChildIndex);
         if (this.compare(leftChildValue, rightChildValue) < 0)
            maxIndex = rightChildIndex;
      }

      let maxValue = this.myArray.get(maxIndex);
      let currentValue = this.myArray.get(index);

      if (this.compare(maxValue, currentValue) > 0) {
         // 交换位置
         this.swap(maxIndex, index);
         // 继续下沉
         this.recursiveSiftDown(maxIndex);
      }
   }

   // 堆的下沉操作 非递归算法 -
   nonRecursiveSiftDown(index) {
      // 该索引位置的元素有左右孩子节点才可以下沉，
      // 在完全二叉树中 如果一个节点没有左孩子必然没有右孩子
      while (this.calcLeftChildIndex(index) < this.myArray.getSize()) {
         let leftChildIndex = this.calcLeftChildIndex(index);
         let leftChildValue = this.myArray.get(leftChildIndex);
         let rightChildIndex = this.calcRightChildIndex(index);
         let rightChildValue = null;
         let maxIndex = leftChildIndex;

         if (rightChildIndex < this.myArray.getSize()) {
            rightChildValue = this.myArray.get(rightChildIndex);
            if (this.compare(leftChildValue, rightChildValue) < 0)
               maxIndex = rightChildIndex;
         }

         let maxValue = this.myArray.get(maxIndex);
         let currentValue = this.myArray.get(index);

         if (this.compare(maxValue, currentValue) > 0) {
            this.swap(maxIndex, index);
            index = maxIndex;
            continue;
         } else break;
      }
   }

   // 将堆顶的元素用一个新元素替换出来
   replace(element) {
      let maxElement = this.findMax();

      this.myArray.set(0, element);

      this.siftDown(0);

      return maxElement;
   }

   // 将一个数组变成一个最大堆 -
   heapify(array) {
      // 将数组中的元素添加到自定义动态数组里
      for (const element of array) this.myArray.push(element);

      // 减少一个O(n)的操作，不然性能相对来说会差一些
      // this.myArray.data = array;
      // this.myArray.size = array.length;

      // 这个动态数组满足了一棵完全二叉树的性质
      // 获取 这棵完全二叉树 最后一个非叶子节点的索引
      let index = this.calcParentIndex(this.myArray.getSize() - 1);

      // 从最后一个非叶子节点开始遍历  从后向前遍历 不停的下沉， 这个就是heapify的过程
      // for (let i = index; i >= 0; i --) { this.siftDown(i);}
      while (0 <= index) this.siftDown(index--);
   }

   // 堆中两个元素的位置进行交换
   swap(indexA, indexB) {
      this.myArray.swap(indexA, indexB);
   }

   // 辅助函数 计算出堆中指定索引位置的元素其父节点的索引 -
   calcParentIndex(index) {
      if (index === 0)
         // 索引为0是根节点，根节点没有父亲节点，小于0就更加不可以了
         throw new Error("index is 0. doesn't have parent.");
      return Math.floor((index - 1) / 2);
   }

   // 辅助函数 计算出堆中指定索引位置的元素其左孩子节点的索引 -
   calcLeftChildIndex(index) {
      return index * 2 + 1;
   }

   // 辅助函数 计算出堆中指定索引位置的元素其右孩子节点的索引 -
   calcRightChildIndex(index) {
      return index * 2 + 2;
   }

   // 比较的功能 -
   compare(elementA, elementB) {
      if (elementA === null || elementB === null)
         throw new Error("element is error. element can't compare.");
      if (elementA > elementB) return 1;
      else if (elementA < elementB) return -1;
      else return 0;
   }

   // 获取堆中实际的元素个数
   size() {
      return this.myArray.getSize();
   }

   // 返回堆中元素是否为空的判断值
   isEmpty() {
      return this.myArray.isEmpty();
   }
}

  4. MyPriorityQueue

    // 自定义优先队列 PriorityQueue
class MyPriorityQueue {
   constructor() {
      this.maxHeap = new MyMaxHeap();
   }

   // 入队
   enqueue(element) {
      this.maxHeap.add(element);
   }

   // 出队
   dequeue() {
      return this.maxHeap.extractMax();
   }

   // 查看队首元素
   getFront() {
      return this.maxHeap.findMax();
   }

   // 查看队列中实际元素的个数
   getSize() {
      return this.maxHeap.size();
   }

   // 返回队列是否为空的判断值
   isEmpty() {
      return this.maxHeap.isEmpty();
   }

   // 扩展： 修改最大堆中的比较算法
   updateCompare(compareMethod) {
      // 传入参数可以替换掉原堆中实现的compare方法
      this.maxHeap.compare = compareMethod;
   }

   // 扩展： 用一个新元素去替换队首的元素，同时再次确认优先级别
   replaceFront(element) {
      // 这样就就可 不需要 出队入队操作这么麻烦了
      return this.maxHeap.replace(element);
   }
}

Leetcode 上优先队列相关的问题

优先队列的经典问题

  1. 在1,000,000个元素中选出前 100 名？
    1. 也就是在 N 个元素中选出前 M 个元素，
    2. 如果 M 等于 1，那么就是在 N 个元素中就选择第一名的那个元素，
    3. 只需要遍历一遍就好了，非常的简单，
    4. 整个算法的时间复杂度是 O(n)级别的，
    5. 但是 M 如果不等于 1 的话，那么就有一点棘手，
    6. 最朴素的想法就是对这一百万个元素进行一下排序，
    7. 对于一百万这个级别的元素来说，使用高级的排序算法，
    8. 无论是归并排序也好还是快速排序也好
    9. 都可以在NlogN的时间里完成任务，
    10. 整体来说这种时间复杂还是可以接受的，
    11. 排序完成后直接取出前一百名元素就好了，非常容易，
  2. 但是问题的关键在于有没有更好的方法，
    1. 在这个问题上，如果使用优先队列的话，
    2. 那么就可以在NlogM这个时间复杂度内解决问题，
    3. 如果这个 M 等于 100 的话，logM 大概是 7 左右。
    4. 如果使用高级的排序算法，
    5. 在NlogN这个时间复杂度内的话，
    6. 那么 logN 大概是 20。
    7. 这样一来它们相差了三倍左右，
    8. 所以 NlogM 是比 NlogN 更好的时间复杂度。
  3. 使用优先队列，维护当前看到的前 M 个元素
    1. 对于这 100 万个元素，肯定是要从头到尾扫描一遍，
    2. 在扫描的过程中，首先将这 N 个元素中的前 M 个元素放入优先队列中，
    3. 之后每次看到一个新的元素，
    4. 如果这个新的元素比当前优先队列中最小的元素还要大，
    5. 那么就把优先队列中最小的那个元素给扔出去，
    6. 取而代之的换上这个新的元素，用这样的方式，
    7. 相当于这个优先队列中一直维护者当前可以看到的前 M 个元素，
    8. 直到把这 n 个元素全都扫描完，在优先队列中最终留下来的这 M 个元素，
    9. 就是最终要求的结果。
  4. 实际需要的是一个最小堆 MinHeap，
    1. 要能够非常快速的取出当前看到前 M 个元素中最小的那个元素，
    2. 需要不断的将当前可以看到的前 M 大的元素中最小的元素进行替换，
    3. 已经实现了最大堆 MaxHeap，你只需要把这个逻辑改一改，
    4. 把它变成一个最小堆 MinHeap 是非常容易的，
    5. 就是将核心逻辑比较的时候符号进行一个改变。
  5. 实际上解决这个问题并不需要真的使用最小堆 MinHeap，
    1. 依然使用最大堆也是可以的，这里面最关键的怎么去定义优先级，
    2. 优先级的大小，没有谁规定最大的元素优先级就是最高的，
    3. 这个问题的解决方案中，每次都是去取出这个优先队列中最小的元素，
    4. 那么就完全可以自己去定义，例如元素的值越小，它的优先级越高，
    5. 在这样的一个定义下，依然可以使用底层以最大堆实现的优先队列了，
    6. 大和小其实是相对的。

在 leetcode 上的问题

  1. 347.前K个高频元素

    1. https://leetcode-cn.com/problems/top-k-frequent-elements/，
    2. 可以使用 系统内置的 Map 来统计频率，
    3. 然后使用 PriorityQueue 来进行频率的优先级统计，
    4. 由于自己实现的自定义优先队列是以一个最大堆为底层实现，
    5. 那么入队的元素的比较操作需要相反，
    6. 要支持的是，频次越低优先级就越高，
    7. 那么当当前元素的频次越低，就让它在堆的最顶端，
    8. 那么 compareTo 操作时，返回的值为正数则会进行向上浮动，
    9. 返回的值如果为负数则会进行下沉。

  2. 代码示例

    // 答题
class Solution {
   // leetcode 347. 前K个高频元素
   topKFrequent(nums, k) {
      /**
       * @param {number[]} nums
       * @param {number} k
       * @return {number[]}
       * 原版
       */
      var topKFrequent = function(nums, k) {
         let map = new Map();
         // 统计 数组中每一个元素出现频率
         for (const num of nums) {
            if (map.has(num)) map.set(num, map.get(num) + 1);
            else map.set(num, 1);
         }

         // 优先队列：使用的时候指定优先级比较的方式
         let queue = new MyPriorityQueue();
         // 变更优先队列中的定义优先级的方法
         queue.updateCompare((elementA, elementB) => {
            // 原的比较算法是 值越大 优先级越大
            // 现在改为 值越小 优先级越大
            if (elementA.value < elementB.value) return 1;
            else if (elementA.value > elementB.value) return -1;
            else return 0;
         });

         for (const key of map.keys()) {
            if (queue.getSize() < k)
               queue.enqueue({ key: key, value: map.get(key) });
            else if (map.get(key) > queue.getFront().value) {
               queue.replaceFront({ key: key, value: map.get(key) });
               // queue.dequeue();
               // queue.enqueue({"key": key, "value": map.get(key)});
            }
         }

         let result = [];
         for (var i = 0; i < k; i++) {
            result.push(queue.dequeue().key);
         }
         return result;
      };

      // 精简版
      var topKFrequent = function(nums, k) {
         let map = new Map();
         // 统计 数组中每一个元素出现频率
         for (const num of nums) {
            if (map.has(num)) map.set(num, map.get(num) + 1);
            else map.set(num, 1);
         }

         // 优先队列：使用的时候指定优先级比较的方式
         let queue = new MyPriorityQueue();
         // 变更优先队列中的定义优先级的方法
         queue.updateCompare((keyA, keyB) => {
            // 原的比较算法是 值越大 优先级越大
            // 现在改为 值越小 优先级越大
            if (map.get(keyA) < map.get(keyB)) return 1;
            else if (map.get(keyA) > map.get(keyB)) return -1;
            else return 0;
         });

         for (const key of map.keys()) {
            if (queue.getSize() < k) queue.enqueue(key);
            else if (map.get(key) > map.get(queue.getFront())) {
               queue.replaceFront(key);
            }
         }

         let result = [];
         for (var i = 0; i < k; i++) {
            result.push(queue.dequeue());
         }
         return result;
      };

      return topKFrequent(nums, k);
   }
}

// main 函数
class Main {
   constructor() {
      this.alterLine('leetcode 347. 前K个高频元素');
      let s = new Solution();

      let arr = [
         5,
         -3,
         9,
         1,
         7,
         7,
         9,
         10,
         2,
         2,
         10,
         10,
         3,
         -1,
         3,
         7,
         -9,
         -1,
         3,
         3
      ];
      console.log(arr);
      this.show(arr);

      let result = s.topKFrequent(arr, 3);
      console.log(result);
      this.show(result);
   }

   // 将内容显示在页面上
   show(content) {
      document.body.innerHTML += `${content}<br /><br />`;
   }

   // 展示分割线
   alterLine(title) {
      let line = `--------------------${title}----------------------`;
      console.log(line);
      document.body.innerHTML += `${line}<br /><br />`;
   }
}

// 页面加载完毕
window.onload = function() {
   // 执行主函数
   new Main();
};

和堆相关的更多话题及广义队列

  1. leetcode 中与堆相关的题目
    1. https://leetcode-cn.com/tag/heap/
  2. 自己实现的堆其实是二叉堆 Binary Heap
    1. 计算机世界中其实还有各种各样的堆，
    2. 学会了二叉堆之后，最容易拓展的就是 d 叉堆 d-ary heap 了，
    3. 也就是说，对于每一个节点来说，它可能有三个四个甚至更多个孩子，
    4. 也排列成完全 d 叉树这种形式，用这样的方式也可以构建出一个堆来，
    5. 对于这种堆而言，其实它的层数是更加的低了，
    6. 那么对它的添加操作删除操作，
    7. 相应的时间复杂度都变成了 log 以 d 为底 n 这样的时间复杂度，
    8. 从这个时间复杂度的角度来讲，好像比 log 以 2 为底 n 这样的时间复杂度要好，
    9. 可是相应的代价会越高，比如每一个节点的 SiftDown 下沉操作时，
    10. 需要考虑的节点数变多了，不仅仅是考虑两个节点了，而是要考虑 d 个节点，
    11. 它们之间就存在了一个制衡的关系。
  3. 自己实现的堆有一个很大的缺点
    1. 只能看到堆首的元素，却不能看到堆中间的元素，
    2. 实际上在很多应用中是需要看到堆中间的元素，
    3. 甚至需要对堆中间的元素进行一定的修改，
    4. 在这种情况下相应的就要有一个索引堆这样的数据结构，
    5. 这种堆除了保持你关注的那个元素之外，还对应了一个索引，
    6. 可以通过这个索引非常方便的检索到元素存在堆中的哪个位置，
    7. 甚至可以根据索引来修改这个元素，
    8. 事实上索引堆还是应用非常广泛的一种数据结构，
    9. 不过这种数据结构相对是比较高级的，
    10. 在慕课网《算法与数据结构》中第四章 8-9 节有，
    11. 无论是最小生成树算法还是最短路径算法，
    12. 也就是对于 Prim 算法和 Dijkstra 算法都可以使用索引堆进行优化，
    13. 在真实的面试中，几乎不会问索引堆的问题。
  4. 在计算机的世界中还有各种奇奇怪怪的堆
    1. 二项堆、斐波那契堆，这些堆更是更高级的数据结构。

广义队列

  1. Queue
    1. void enqueue(e)
    2. E dequeue()
    3. E getFront()
    4. int getSize()
    5. boolean isEmpty()
  2. 只要支持这样的接口或者支持入队或者出队操作，它就可以叫做一个队列。
    1. 这么定义一个队列的话，那么队列这个概念就太广义了，
    2. 如普通队列（先到先得）、优先队列（优先级最高的先出队），
    3. 如此一来，栈其实也可以理解是一个队列，
    4. 入栈和出栈操作也是向一个数据结构添加元素和拿出元素，
    5. 所以栈也可以理解成是一个队列，
    6. 事实上当你这么理解的时候，对于很多计算机算法，
    7. 你理解的角度将会产生新的变化，最典型的例子如二分搜索树，
    8. 实现了一个非递归的前序遍历、层序遍历，
    9. 这两个算法基本的逻辑是完全一样的，
    10. 区别只在于一个使用的栈一个使用的队列，
    11. 当你把栈也看做队列的时候，这两种方式非常完美的统一了，
    12. 对于这两种遍历方式来说，它们的区别在于你使用了怎样的数据结构，
    13. 而不是具体的逻辑，这个具体的逻辑其实是一致的。
avatar
文章
阅读
粉丝