覃超老师再讲解高级搜索时，提到 启发式搜索 也称 A搜索。这一开始我以为搜索就是等于A

https://leetcode-cn.com/problems/shortest-path-in-binary-matrix
在这道最短路径的题目的时候，对两者产生一个疑问🤔️？两者是等同的吗。还有算法中涉及到的优先队列，二叉堆等数据结构，由于本人本身是算法菜鸡，一时间搞混了。为了更好的理解，决定缕清楚上面说到的知识点。

启发式

heuristic可认为是智能搜索，或者是根据某一项条件来不断优化搜索的方向，也就是说一边搜索一边思考。本质是通过优先级不断地去找要找到的点，先用优先级高的拿出来搜索即可。自然而然的就是用优先级队列存储节点。

启发式函数是一种告知搜索方向的方法。它提供了一种明知的方法来猜测哪个邻节点会导向一个目标。

A*算法

A算法是启发式搜索的一种，其中A的启发式函数定义如下：

f(n) = g(n) + h(n)

g(n)表示起到到顶点n的开销，实际距离
h(n)表示顶点n到终点的估算距离（根据所采用的评估函数的不同而变化）。常见的评估函数有——欧几里得距离、曼哈顿距离、切比雪夫距离；

如果不计算g(n)，也就是g(n) = 0，则算法转换成Greedy Best-First Search，每一步选择距离终点最近的节点，期待最终结果是最优的。实际所得路径未必是最短路径。

如果不计算h(n)，也就是h(n) = 0，则算法转换成为单源最短路径问题，即Dijkstra算法。它只考虑起点到顶点n的实际距离（开销），算法必定是能找到最短路径，但效率没有A高，节点的扩散范围比A大。

优先队列

启发式搜索本质就是找优先级高的处理搜索，自然就是要用到优先队列的数据结构。

优先队列有几种实现方式。

初级实现

  • 有序数组实现：插入O(n)，取出O(1)
  • 无序数组实现：插入O(1)，取出O(n)
  • 链表实现

典型实现

优先队列往往是用(二叉)堆来实现的。二叉堆实现的优先队列保证插入取出的时间复杂度都是O(logn)

二叉堆

二叉堆为一种特殊的二叉树，往往是用数组实现。二叉堆分为最大堆，和最小堆。

最大堆的性质是每个节点都大于等于它的两个子节点

最小堆的性质是每个节点都小于等于它的两个子节点

二叉堆的删除和插入时间复杂度为O(logn)

具体实现

代码参考算法一书实现。

最大优先队列

  1. class MaxPQ {
  2.   constructor(compareTo = (a, b) => a - b) {
  3.     this.compareTo = compareTo;
  4.     this.N = 0;
  5.     this.pq = [null]; // 位置0为哨兵
  6.   }
  8.   max() {
  9.     return this.pq[1];
  10.   }
  12.   delMax() {
  13.     const max = this.pq[1];
  14.     // 把这个最大元素换到最后，删除之
  15.     this.exch(1, this.N);
  16.     this.pq[this.N] = null;
  17.     this.N -= 1;
  18.     // 让 pq[1] 下沉到正确位置
  19.     this.sink(1);
  20.     return max;
  21.   }
  23.   insert(e) {
  24.     this.N += 1;
  25.     // 先把新元素加到最后
  26.     this.pq[this.N] = e;
  27.     // 然后让它上浮到正确的位置
  28.     this.swim(this.N);
  29.   }
  31.   get size() {
  32.     return this.N;
  33.   }
  35.   /** 辅助函数 */
  36.   /** 上浮第 k 个元素，以维护最大堆性质 */
  37.   swim(k) {
  38.     // 浮到堆顶，停止上浮
  39.     while (k > 1 && this.less(this.parent(k), k)) {
  40.       // 如果第k个元素比父级元素大，交换
  41.       this.exch(k, this.parent(k));
  42.       k = this.parent(k);
  43.     }
  44.   }
  46.   /** 下沉第 k 个元素，以维护最大堆性质 */
  47.   sink(k) {
  48.     while (this.left(k) <= this.N) {
  49.       // 先找出左节点
  50.       let j = this.left(k);
  51.       // 如果右节点存在，对比大小，取最大值
  52.       if (j < this.N && this.less(j, j + 1)) {
  53.         j += 1;
  54.       }
  55.       // 如果左右节点的最大值都比k小，就不必下沉了。
  56.       if (this.less(j, k)) break;
  57.       this.exch(j, k);
  58.       k = j;
  59.     }
  60.   }
  62.   exch(i, j) {
  63.     const tmp = this.pq[i];
  64.     this.pq[i] = this.pq[j];
  65.     this.pq[j] = tmp;
  66.   }
  68.   /** pq[i] 是否比 pq[j] 小 */
  69.   less(i, j) {
  70.     return this.compareTo(this.pq[i], this.pq[j]) < 0;
  71.   }
  73.   parent(k) {
  74.     return k >> 1;
  75.   }
  77.   left(k) {
  78.     return k * 2;
  79.   }
  81.   right(k) {
  82.     return k * 2 + 1;
  83.   }
  84. }
  86. const maxpq = new MaxPQ();
  87. maxpq.insert(3); //
  88. maxpq.insert(6); //
  89. maxpq.insert(1); //
  90. maxpq.insert(8); //
  91. console.log(maxpq.max()); // 8
  92. maxpq.delMax(); // 8
  93. console.log(maxpq.max()); // 6
  94. maxpq.insert(11);
  95. console.log(maxpq.max()); // 11

最小优先队列

  1. class MinPQ {
  2.   constructor(compareTo = (a, b) => a - b) {
  3.     this.compareTo = compareTo;
  4.     this.N = 0;
  5.     this.pq = [null]; // 位置0为哨兵
  6.   }
  8.   max() {
  9.     return this.pq[1];
  10.   }
  12.   delMax() {
  13.     const min = this.pq[1];
  14.     this.exch(1, this.N);
  15.     this.pq[this.N] = null;
  16.     this.N -= 1;
  17.     this.sink(1);
  18.     return min;
  19.   }
  21.   insert(e) {
  22.     this.N += 1;
  23.     this.pq[this.N] = e;
  24.     this.swim(this.N);
  25.   }
  27.   get size() {
  28.     return this.N;
  29.   }
  31.   /** 辅助函数 */
  32.   /** 上浮第 k 个元素，以维护最大堆性质 */
  33.   swim(k) {
  34.     while (k > 1 && this.greater(this.parent(k), k)) {
  35.       // 如果第k个元素比父元素小，交换
  36.       this.exch(k, this.parent(k));
  37.       k = this.parent(k);
  38.     }
  39.   }
  41.   /** 下沉第 k 个元素，以维护最大堆性质 */
  42.   sink(k) {
  43.     while (this.left(k) <= this.N) {
  44.       let j = this.left(k);
  45.       // 找出左右节点的最小节点
  46.       if (j < this.N && this.greater(j, j + 1)) {
  47.         j += 1;
  48.       }
  49.       // 如果k比两个元素都小，不必下沉
  50.       if (this.greater(j, k)) break;
  51.       this.exch(j, k);
  52.       k = j;
  53.     }
  54.   }
  56.   exch(i, j) {
  57.     const tmp = this.pq[i];
  58.     this.pq[i] = this.pq[j];
  59.     this.pq[j] = tmp;
  60.   }
  62.   /** pq[i] 是否比 pq[j] 大 */
  63.   greater(i, j) {
  64.     return this.compareTo(this.pq[i], this.pq[j]) > 0;
  65.   }
  67.   parent(k) {
  68.     return k >> 1;
  69.   }
  71.   left(k) {
  72.     return k * 2;
  73.   }
  75.   right(k) {
  76.     return k * 2 + 1;
  77.   }
  78. }
  80. const minpq = new MinPQ();
  81. minpq.insert(3); //
  82. minpq.insert(6); //
  83. minpq.insert(1); //
  84. minpq.insert(8); //
  85. console.log(minpq.max()); // 1
  86. minpq.delMax(); // 1
  87. console.log(minpq.max()); // 3
  88. minpq.insert(2);
  89. console.log(minpq.max()); // 2

索引优先队列

优先队列有一个缺点，就是不能直接访问已存在于优先队列中的对象，并更新它们。

索引优先队用一个整数和对象进行关联，当我们需要更新该对象的值时，可以通这个整数进行快速索引，然后对对象的值进行更新（简而言之，用一个索引数组保存了对象在数组中的位置）。当然更新后的对象在优先队列中的位置可能发生变化，这样以保证整个队列还是一个优先队列。

实现原理

keys存放对象，pq存放与对象相关的整数，也就是对象在数组中的位置。
qp存储与对象相关的整数在pq数组中的下标，目的是为了在修改k对应的对象时，能够快速找到pq中元素值对应的下标，同时在上浮/下沉的过程中同时维护它。

keys存放的对象不一定在数组中是连续存放的，qp同keys。pq是连续存放的，且作为优先队列，是需要通过swim/sink维护堆有序的。
在维护堆有序时，keys是不需要修改的，需要修改pq，qp

具体实现

代码参考算法一书实现。

索引最大优先队列

  1. /**
  2.  * 索引最大优先队列
  3.  * 索引优先队列，用一个索引数组保存了元素在数组中的位置。
  4.  * 对于pq是连续的，但是qp，keys是不连续的，
  5.  */
  6. class IndexMaxPQ {
  7.   constructor(maxN, compareTo = (a, b) => a - b) {
  8.     // `keys`存放对象，`pq`存放与对象相关的整数，也就是对象在数组中的位置。
  9.     // `qp`存储与对象相关的整数在`pq`数组中的下标
  10.     // qp[pq[i]] = i, pq[qp[j]] = j
  11.     this.compareTo = compareTo;
  12.     this.maxN = maxN;
  13.     this.N = 0;
  14.     this.keys = new Array(maxN + 1);
  15.     this.pq = new Array(maxN + 1);
  16.     // 整数没对象没关联的时候，设置为-1
  17.     this.qp = new Array(maxN + 1).fill(-1);
  18.   }
  20.   insert(i, key) {
  21.     if (!this.validateIndex(i)) return;
  22.     if (this.contains(i)) return;
  23.     this.N += 1;
  24.     this.pq[this.N] = i;
  25.     this.qp[i] = this.N;
  26.     this.keys[i] = key;
  27.     this.swim(this.N);
  28.   }
  30.   change(i, key) {
  31.     if (!this.validateIndex(i)) return;
  32.     if (!this.contains(i)) return;
  33.     this.keys[i] = key;
  34.     // 修改对象后，通过上浮/下沉恢复堆有序
  35.     this.swim(this.qp[i]);
  36.     this.sink(this.qp[i]);
  37.   }
  39.   /** 删除整数i关联的对象 */
  40.   delete(i) {
  41.     if (!this.validateIndex(i)) return;
  42.     if (!this.contains(i)) return;
  43.     // i对应的对象和最后一个交换，上浮/下沉，删除最后一个
  44.     const index = this.pq[i];
  45.     this.exch(index, this.N);
  46.     this.N -= 1;
  47.     this.swim(index);
  48.     this.sink(index);
  49.     this.keys[i] = null;
  50.     this.pq[i] = -1;
  51.   }
  53.   maxKey() {
  54.     return this.keys[this.pq[1]];
  55.   }
  57.   maxIndex() {
  58.     return this.pq[1];
  59.   }
  61.   /** 删除堆顶元素，并返回关联的整数 */
  62.   delMax() {
  63.     if (this.isEmpty()) return undefined;
  64.     const index = this.maxIndex();
  65.     // 堆顶和最后一个交换，之后堆顶下沉，删除最后的元素
  66.     this.exch(1, this.N);
  67.     this.N -= 1;
  68.     this.sink(1);
  69.     this.keys[index] = null;
  70.     this.qp[index] = -1;
  71.     this.pq[this.N + 1] = null;
  72.     return index;
  73.   }
  75.   /** 查找有没有和整数i关联的对象 */
  76.   contains(i) {
  77.     return this.qp[i] !== -1;
  78.   }
  80.   /** 检查整数是否在有效 */
  81.   validateIndex(i) {
  82.     return i >= 0 && i < this.maxN;
  83.   }
  85.   isEmpty() {
  86.     return this.N === 0;
  87.   }
  89.   get size() {
  90.     return this.N;
  91.   }
  93.   exch(i, j) {
  94.     const swap = this.pq[i];
  95.     this.pq[i] = this.pq[j];
  96.     this.pq[j] = swap;
  97.     this.qp[this.pq[i]] = i;
  98.     this.qp[this.pq[j]] = j;
  99.   }
  101.   less(i, j) {
  102.     return this.compareTo(this.keys[this.pq[i]], this.keys[this.pq[j]]) < 0;
  103.   }
  105.   swim(i) {
  106.     while (i > 1 && this.less(this.parent(i), i)) {
  107.       // 如果i对应的对象大于父节点的，上浮
  108.       this.exch(i, this.parent(i));
  109.       i = this.parent(i);
  110.     }
  111.   }
  113.   sink(i) {
  114.     while (this.left(i) <= this.N) {
  115.       let child = this.left(i);
  116.       // 左右两个节点中找出最大的一个
  117.       if (child < this.N && this.less(child, child + 1)) {
  118.         child += 1;
  119.       }
  120.       // 如果i对应的对象没比最大的子节点小，那么无需下沉
  121.       if (!this.less(i, child)) break;
  122.       this.exch(i, child);
  123.       i = child;
  124.     }
  125.   }
  127.   parent(k) {
  128.     return k >> 1;
  129.   }
  131.   left(k) {
  132.     return k * 2;
  133.   }
  135.   right(k) {
  136.     return k * 2 + 1;
  137.   }
  138. }
  140. const strings = ['nkg', 'nmi', 'liba'];
  141. const strArr = strings.map((str) => str.split(''));
  142. const ipq = new IndexMaxPQ(strArr.length, (a, b) => a.charCodeAt(0) - b.charCodeAt(0));
  143. let ans = '';
  144. for (let i = 0; i < strArr.length; i += 1) {
  145.   ipq.insert(i, strArr[i].shift());
  146. }
  147. while (!ipq.isEmpty()) {
  148.   ans += ipq.maxKey();
  149.   const i = ipq.delMax();
  150.   const char = strArr[i].shift();
  151.   if (char) {
  152.     ipq.insert(i, char);
  153.   }
  154. }
  155. console.log(ans);
  156. console.log(ans === 'nnmlkiigba');

索引最小优先队列

  1. /**
  2.  * 索引最小优先队列
  3.  */
  4. class IndexMinPQ {
  5.   constructor(maxN, compareTo = (a, b) => a - b) {
  6.     this.maxN = maxN;
  7.     this.compareTo = compareTo;
  8.     this.keys = new Array(maxN + 1);
  9.     this.pq = new Array(maxN + 1);
  10.     this.qp = new Array(maxN + 1).fill(-1);
  11.     this.N = 0;
  12.   }
  14.   insert(i, key) {
  15.     // 整数超过
  16.     if (!this.validateIndex(i)) return;
  17.     if (this.contains(i)) return;
  18.     this.N += 1;
  19.     this.pq[this.N] = i;
  20.     this.qp[i] = this.N;
  21.     this.keys[i] = key;
  22.     this.swim(this.N);
  23.   }
  25.   change(i, key) {
  26.     if (!this.validateIndex(i)) return;
  27.     if (!this.contains(i)) return;
  28.     this.keys[i] = key;
  29.     // 修改对象之后，需要调整下堆有序，上浮或下沉，
  30.     // 两个都操作一下，就不用判断具体是执行哪个操作了。
  31.     this.swim(this.qp[i]);
  32.     this.sink(this.qp[i]);
  33.   }
  35.   contains(i) {
  36.     return this.qp[i] !== -1;
  37.   }
  39.   delete(i) {
  40.     if (!this.validateIndex(i)) return;
  41.     if (!this.contains(i)) return;
  42.     // i对应的对象和最后一个交换，上浮/下沉，删除最后一个
  43.     const index = this.qp[i];
  44.     this.exch(this.pq, i, this.N);
  45.     this.N -= 1;
  46.     this.swim(index);
  47.     this.sink(index);
  48.     this.qp[i] = -1;
  49.     this.keys[i] = null;
  50.   }
  52.   /** 返回堆顶对象 */
  53.   minKey() {
  54.     return this.keys[this.pq[1]];
  55.   }
  57.   /** 返回堆顶对象关联的整数 */
  58.   minIndex() {
  59.     return this.pq[1];
  60.   }
  62.   /** 删除堆顶对象，并返回堆顶对象关联的整数 */
  63.   delMin() {
  64.     if (this.isEmpty()) return undefined;
  65.     const index = this.minIndex();
  66.     // 堆顶和最后一个元素交换，然后删除最后一个元素
  67.     this.exch(1, this.N);
  68.     this.N -= 1;
  69.     this.sink(1);
  70.     this.keys[index] = null;
  71.     this.qp[index] = -1;
  72.     this.pq[this.N + 1] = null;
  73.     return index;
  74.   }
  76.   isEmpty() {
  77.     return this.N === 0;
  78.   }
  80.   get size() {
  81.     return this.N;
  82.   }
  84.   swim(k) {
  85.     while (k > 1 && this.greater(this.parent(k), k)) {
  86.       this.exch(k, this.parent(k));
  87.       k = this.parent(k);
  88.     }
  89.   }
  91.   sink(k) {
  92.     while (this.left(k) <= this.N) {
  93.       let child = this.left(k);
  94.       if (child < this.N && this.greater(child, child + 1)) {
  95.         child += 1;
  96.       }
  97.       if (!this.greater(k, child)) break;
  98.       this.exch(k, child);
  99.       k = child;
  100.     }
  101.   }
  103.   greater(i, j) {
  104.     return this.compareTo(this.keys[this.pq[i]], this.keys[this.pq[j]]) > 0;
  105.   }
  107.   exch(i, j) {
  108.     const swap = this.pq[i];
  109.     this.pq[i] = this.pq[j];
  110.     this.pq[j] = swap;
  111.     this.qp[this.pq[i]] = i;
  112.     this.qp[this.pq[j]] = j;
  113.   }
  115.   parent(k) {
  116.     return k >> 1;
  117.   }
  119.   left(k) {
  120.     return k * 2;
  121.   }
  123.   right(k) {
  124.     return k * 2 + 1;
  125.   }
  127.   /** 检查整数是否在有效 */
  128.   validateIndex(i) {
  129.     return i >= 0 && i < this.maxN;
  130.   }
  131. }
  133. const ipq = new IndexMinPQ(4, (a, b) => a.charCodeAt(0) - b.charCodeAt(0));
  134. ipq.insert(2, 'b');
  135. ipq.insert(0, 'e');
  136. ipq.insert(1, 's');
  137. ipq.insert(3, 't'); // pq = [2,0,1,3]
  138. console.log(ipq.minIndex()); // 2
  139. ipq.change(1, 'a');
  140. console.log(ipq.minIndex()); // 1
  141. console.log(ipq.delMin()); // 1
  143. // 多个有序字符串合并成一个有序字符串， 多项归并
  144. {
  145.   const strings = ['afg', 'beh', 'ccdi'];
  146.   const ipq = new IndexMinPQ(4, (a, b) => a.charCodeAt(0) - b.charCodeAt(0));
  147.   const strArrs = strings.map((str) => str.split(''));
  148.   for (let i = 0; i < strArrs.length; i += 1) {
  149.     const char = strArrs[i].shift();
  150.     ipq.insert(i, char);
  151.   }
  152.   let res = '';
  153.   while (!ipq.isEmpty()) {
  154.     res += ipq.minKey();
  155.     const i = ipq.delMin();
  156.     const char = strArrs[i].shift();
  157.     if (char) ipq.insert(i, char);
  158.   }
  159.   console.log(res);
  160.   console.log(res === 'abccdefghi');
  161. }

资料