每个父节点都小于他的左，右，孩子节点的值，最小堆

  1. var count = 0;
  2. function up_adjust (arr) { // 下沉操作
  3.     let childIndex = arr.length - 1;
  4.     // 取余二等于零 就是一个右孩子
  5.     let parentIndex = childIndex - 1;
  6.     let temp = arr[childIndex];
  7.     while (childIndex > 0 && temp < arr[parentIndex]) {
  8.         count++;
  9.         // 子元素存在 并且 子元素小于父元素
  10.         // 父元素下沉
  11.         arr[childIndex] = arr[parentIndex];
  12.         childIndex = parentIndex;
  13.         parentIndex = childIndex - 1;
  14.     }
  15.     // 子元素上浮
  16.     arr[childIndex] = temp;
  17. }
  19. function down_adjust(parentIndex, len, arr) { // 上浮操作
  20.     // parentIndex 待下沉目标
  21.     // len 堆的长度范围
  22.     // arr 二叉堆数组
  23.     let temp = arr[parentIndex];
  24.     let childIndex = 2 * parentIndex + 1; // 左孩子
  25.     while (childIndex < len) {
  26.         count++;
  27.         if (childIndex + 1 < len && arr[childIndex + 1] < arr[childIndex]) {
  28.             // 右孩子存在，并且右孩子小于左孩子
  29.             childIndex += 1;
  30.         }
  31.         if (temp <= arr[childIndex]) {
  32.             // 父节点小于任何一个孩子的值，直接跳出
  33.             break;
  34.         }
  35.         // 父元素下沉，子元素上浮
  36.         arr[parentIndex] = arr[childIndex];
  37.         parentIndex = childIndex;
  38.         childIndex = 2 * childIndex + 1; // 左孩子的下标
  39.     }
  40.     // 子元素上浮
  41.     arr[parentIndex] = temp;
  42. }
  44. function build_heap(arr) {
  45.     for (let i = arr.length - 2; i >= 0; i--) {
  46.         down_adjust(i, arr.length, arr);
  47.     }
  48. }
  50. var a = [7, 1, 3, 10, 5, 2, 8, 9, 6]
  51. build_heap(a); // 最小二叉堆的自均衡
  52. while (a.length) {
  53.     console.log(a.shift()); // 输出0～9
  54.     build_heap(a)
  55. }
  56. console.log(count); // 23

上面的代码是书本里面介绍的方法，简直扯淡，完全就是遍历，下面是二叉堆的上浮

  1. var count = 0;
  2. function up_adjust (arr) { // 下沉操作
  3.     let childIndex = arr.length - 1;
  4.     let childOffset = childIndex % 2 === 0 ? 2 : 1; // 右孩子
  5.     // 取余二等于零 就是一个右孩子
  6.     let parentIndex = (childIndex - childOffset) / 2;
  7.     let temp = arr[childIndex];
  8.     while (childIndex > 0 && temp < arr[parentIndex]) {
  9.         count++;
  10.         // 子元素存在 并且 子元素小于父元素
  11.         // 父元素下沉
  12.         arr[childIndex] = arr[parentIndex];
  13.         childIndex = parentIndex;
  14.         childOffset = childIndex % 2 === 0 ? 2 : 1; // 右孩子
  15.         // 取余二等于零 就是一个右孩子
  16.         parentIndex = (childIndex - childOffset) / 2;
  17.     }
  18.     // 子元素上浮
  19.     arr[childIndex] = temp;
  20. }
  21. var a = [1, 5, 2, 6, 7, 3, 8, 9, 10, 0]
  22. up_adjust(a);
  23. console.log(a); [0, 1, 2, 6, 5, 3, 8, 9, 10, 7]
  24. console.log(count); // 3

每个父节点都大于他左右孩子的值 最大堆

略

优先队列，每次把头元素出掉，然后树自均衡一下，然后在出，在自均衡。

代码略
为什么优先队列比循环排序输出更优呢，下面省略if比较的执行次数计算
假设长度为10的无序数值数值，要排序输出，最少要55次执行，冒泡排序执行45(10 * 10 / 2 + 10 / 2 - 10)次，循环输出10次。

优先队列，
出队列1，首次自均衡 9 - 2 = 7
出队列1 ，自均衡 8 - 2 = 6
…
10次输出完毕，7+6+5+4+3+2+1 = 28次 ,构建二叉堆1，1(和树深度一致) …
[1, 1,1,2,2,2,2,3,3,3] 最大 20次 总共 45次

如果100次的话
循环 99 99 / 2 + 99 / 2 = 4950
优先队列 97 97 /2 + 97 / 2 = 4753 + 127 = 4880 比循环更优先，但是按实际情况，可能次数更少一些

  1. // 计算树的层次
  2. for (let i = 100, x = 1; i > 1; i /= 2, x++) {
  3.    console.log(i, x);
  4. }
  5. /*
  6. 100 1
  7. VM1643:2 50 2
  8. VM1643:2 25 3
  9. VM1643:2 12.5 4
  10. VM1643:2 6.25 5
  11. VM1643:2 3.125 6
  12. VM1643:2 1.5625 7
  14. 7层， 除掉根
  15. 2一次方
  16. 2二次方
  17. ...
  18. 2的六次方
  19. */
  20. var count = 0
  21. for (let i = 6; i > 0; i--) {
  22.     count += Math.pow(2, i)
  23. }
  24. 126 + 1