先简单记录一下：

el-collapse-item 的 title 区域会有冒泡行为，禁止冒泡用@click.stop。 但是在其中的按钮如果被 disabled 时，此按钮的 stop 就失效了，解决办法是，在外层增加一层 div，加上@click.stop

           <el-collapse
                v-model="activeNames"
                size="mini"
                :loading="loading"
                :style="{maxHeight: containerHeight + 'px', overflowY: 'auto'}"
                @change="handleCollapseChange"
            >
                <el-collapse-item
                    v-for="(tags, index) in tagsData"
                    :key="index"
                    :name="tags.tagKey"
                    align="left"
                >
                    <span 
                        slot="title"
                        class="collapse-title"
                    >
                        标签键：{{ tags.tagKey }}
                        <div @click.stop> <!-- 按钮被禁用，防止冒泡会失效 -->
                            <el-button
                                v-if="activeNames.includes(tags.tagKey)" 
                                size="mini"
                                :disabled="tableSelectionList && tableSelectionList[`multipleTable-${index}`] &&
                                    tableSelectionList[`multipleTable-${index}`].length > 0 ? false : true"
                                @click.stop="batchDeleteTags(index)"
                            >
                                批量删除标签值
                            </el-button>
                        </div>
                    </span>
                    <el-table
                        :data="tags.tagValues"
                        style="width: 100%"
                        size="mini"
                        tooltip-effect="light"
                        :header-cell-style="rowClass"
                        border
                        @selection-change="
                            (selection) => {
                                handleSelectionChange(selection, index)
                            }"
                    >
                        <el-table-column
                            type="selection"
                            width="50"
                        />
                        <el-table-column
                            label="标签值"
                            prop="tagValue"
                            width="350"
                        />
                        <el-table-column
                            label="绑定资源"
                            prop="resource"
                            :formatter="boundResource"
                            show-overflow-tooltip
                        />
                        <el-table-column
                            label="操作"
                            width="100"
                        >
                            <template slot-scope="scope">
                                <el-button
                                    type="text"
                                    size="mini"
                                    @click="bindResource(scope.row, tags.tagKey)"
                                >
                                    绑定资源
                                </el-button>
                            </template>
                        </el-table-column>
                    </el-table>
                    <p class="selection-display">
                        已选中
                        {{ tableSelectionList && tableSelectionList[`multipleTable-${index}`] &&
                            tableSelectionList[`multipleTable-${index}`].length || 0 }}
                        项 / 共 {{ tags.tagValues.length }} 项
                    </p>
                </el-collapse-item>
            </el-collapse>

各位好，在最近一段时间内，工作有点忙，以至于断更了一段时间，哈哈。

不过在紧张的工作中，我还是记录了一下被坑的地方，分享给大家。

问题是这样的：某一天正在修改一个表格，填数据，大家都知道这种工作是比较简单枯燥的。 但是突然我就发现了一个异常现象，就是在时间的那一栏里，竟然有超过60的数字，这肯定是不太对的，因为我们知道时间的时分秒都是60进制。然后也检查了一下对时间的format格式，写的是'HH:MM:SS'，好像也没错。

就在我怀疑自我的时候，本着打破砂锅问到底的精神，我决定去看下相关的API。不查不要紧，一查发现我之前的认知是错误的。原来在时间相关的format格式中，大小是有不同的定义的。比如说'HH'和'hh'就不同，HH代表24小时制，hh代表12小时制，比如's'代表的是秒数，那S代表的就是毫秒数。下面是关于时间format的具体细节及说明，希望能帮到大家，哈哈。祝大家2022年新年快乐呀～

Tue Nov 11 15:16:42 CST 2014 (EEE MMM dd HH:mm:ss z yyyy)

最近年底了，有点忙，拖更了一个月

进阶算法之排序和搜索

排序和搜索是什么？

• 排序：把某个乱序的数组变成升序或者降序的数组
• 搜索：找出数组中某个元素的下标

JS中的排序和搜索

• JS中的排序：数组的sort方法
• JS中的搜索：数组的indexOf方法

排序算法：

• 冒泡排序
• 选择排序
• 插入排序
• 归并排序
• 快速排序
• ...

搜索算法

• 顺序搜索
• 二分搜索
• ...

JavaScript实现：冒泡排序

冒泡排序的思路

• 比较所有相邻元素，如果第一个比第二个大，则交换他们
• 一轮下来，可以保证最后一个数是最大的
• 执行n-1轮，就可以完成排序

各类排序的思路动画演示 https://visualgo.net/zh

冒泡排序的时间复杂度

• 两个嵌套循环
• 时间复杂度：O（n^2）

// 冒泡排序
Array.prototype.bubbleSort = function () {
  console.log(this);
  for (let i = 0; i < this.length - 1; i += 1) {
    for (let j = 0; j < this.length - 1 - i; j += 1) {
      console.log(this[j], this[j + 1])
      if (this[j] > this[j + 1]) {
        const temp = this[j];
        this[j] = this[j + 1];
        this[j + 1] = temp;
      }
    }
  }
};
const arr = [5, 4, 3, 2, 1]
arr.bubbleSort();

JavaScript实现：选择排序

• 找到数组中的最小值，选中它并将其放置在第一位
• 接着找到第二小的值，选中它并将其放置在第二位
• 以此类推，执行n - 1 轮

选择排序的时间复杂度

• 两个嵌套循环
• 时间复杂度：O（n^2）

// 选择排序的实现
Array.prototype.selectionSort = function () {
  for (let i = 0; i < this.length - 1; i += 1) {
    let indexMin = i;
    for (let j = i; j < this.length; j += 1) {
      if (this[j] < this[indexMin]) {
        indexMin = j;
      }
    }
    if (indexMin !== i) {
      const temp = this[i];
      this[i] = this[indexMin];
      this[indexMin] = temp;
    }
  }
};

const arr = [5, 4, 3, 2, 1]
arr.selectionSort();

JavaScript实现：插入排序

• 从第二个数开始往前比
• 比它大就往后排
• 以此类推进行到最后一个数

插入排序的时间复杂度

• 两个嵌套循环
• 时间复杂度：O（n^2）

// 插入排序的实现
Array.prototype.insertionSort = function () {
  for (let i = 1; i < this.length; i += 1) {
    const temp = this[i];
    let j = i;
    while (j > 0) {
      if (this[j - 1] > temp) {
        this[j] = this[j - 1];
      } else {
        break;
      }
      j -= 1;
    }
    this[j] = temp;
  }
};

const arr = [5, 4, 3, 2, 1]
arr.insertionSort();

JavaScript实现：归并排序

• 分：把数组劈成两半，在递归地对子数组进行"分"操作，直到分成一个个单独的数
• 合：把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组

合并两个有序数组

• 新建一个空数组res，用于存放最终排序后的数组
• 比较两个有序数组的头部，较小者出队并推入res中
• 如果两个数组还有值，就重复第二步

归并排序的时间复杂度

• 分的时间复杂度是O（logN）
• 合的时间复杂度：O（n）
• 时间复杂度：O（nlogN）

// 归并排序的实现
Array.prototype.mergeSort = function () {
  // 分
  const rec = (arr) => {
    if (arr.length === 1) {
      return arr;
    }
    const mid = Math.floor(arr.length / 2); // 获取中间下标
    const left = arr.slice(0, mid); // 获取左边数组
    const right = arr.slice(mid, arr.length); // 获取右边数组
    const orderLeft = rec(left); // 左边数组有序
    const orderRight = rec(right); // 右边数组有序
    const res = [];
    while (orderLeft.length || orderRight.length) {
      if (orderLeft.length && orderRight.length) {
        // 比较队头
        res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift());
      } else if (orderLeft.length) {
        res.push(orderLeft.shift());
      } else if (orderRight.length) {
        res.push(orderRight.shift());
      }
    }
    return res;
  }
  const res = rec(this);
  res.forEach((n, i) => {
    this[i] = n;
  })
}
const arr = [5, 4, 3, 2, 1];
arr.mergeSort();

JavaScript实现：快速排序

• 分区：从数组中任意选择一个“基准”，所有比基准小的元素放在基准前面，比基准大的元素放在基准的后面
• 递归：递归地对基准前后的子数组进行分区

快速排序的时间复杂度

• 递归的时间复杂度是O（logN）
• 分区操作的时间复杂度：O（n）
• 时间复杂度：O（nlogN）

// 快速排序的实现
Array.prototype.quickSort = function () {
  const rec = (arr) => {
    if (arr.length === 1) {
      return arr;
    }
    const left = [];
    const right = [];
    const mid = arr[0];
    for (let i = 1; i < arr.length; i += 1) {
      if (arr[i] < mid) {
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    return [...rec(left), mid, ...rec(right)];
  }
  const res = rec(this);
  res.forEach((n, i) => {
    this[i] = n;
  });
}
const arr = [2, 4, 5, 3, 1];
arr.quickSort();
console.log(arr)

JavaScript实现：顺序搜索

• 遍历数组
• 找到跟目标值相等的元素，就返回它的下标
• 遍历结束后，如果没有搜索到目标值，就返回-1

顺序搜索的时间复杂度

• 遍历数组是一个循环操作
• 时间复杂度：O（n）

// 顺序搜索的实现
Array.prototype.sequentialSearch = function (item) {
  for (let i = 0; i < this.length; i += 1) {
    if (this[i] === item) {
      return i;
    }
  }
  return -1;
}
const res = [1, 2, 3, 4, 5].sequentialSearch(3);

Javascript实现：二分搜索

• 从数组的中间元素开始，如果中间元素正好是目标值，则搜索结束
• 如果目标值大于或者小于中间元素，则在大于或小于中间元素的那一半数组中搜索

二分搜索的时间复杂度

• 每一次比较都使搜索范围缩小一半
• 时间复杂度：O（logN）

// 二分搜索的实现
Array.prototype.binarySearch = function (item) {
  let low = 0;
  let high = this.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const element = this[mid];
    if (element < item) {
      low = mid + 1;
    } else if (element > item) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}
const res = [1, 2, 3, 4, 5].binarySearch(5);

LeetCode #21 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例：

• 输入：1->2->4, 1->3->4
• 输出：1->1->2->3->4->4

解题思路：

1. 与归并排序中的合并两个有序数组很相似
2. 将数组替换成链表就能解决此题

解题步骤：

1. 新建一个新链表，作为返回结果
2. 用指针遍历两个有序链表，并比较两个链表的当前节点，较小者先接入新链表，并将指针后移一步
3. 链表遍历结束，返回新链表

复杂度：

1. 时间复杂度：O（n）即链表1和链表2的长度之和
2. 空间复杂度：O（1）

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    const res = new ListNode(0); // 新建新链表
    let p = res;
    let p1 = l1; // 指针1：不停指向新链表的最后一个节点。
    let p2 = l2;
    while(p1 && p2){
        // 链表1当前节点值小于链表2当前节点值
        if(p1.val < p2.val){
            p.next = p1; // p1接到新链表最后一个节点上
            p1 = p1.next; // 移动
        }else{
            p.next = p2; // p2接到新链表最后一个节点上
            p2 = p2.next;
        }
        p = p.next; // 保证p永远指向新链表最后一个节点上
    }
    if(p1){
        p.next = p1;
    }
    if(p2){
        p.next = p2;
    }
    return res.next; // 输出链表的头部上一个节点
};

LeetCode #374 猜数字大小

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

• -1：我选出的数字比你猜的数字小 pick < num
• 1：我选出的数字比你猜的数字大 pick > num
• 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

示例 ：

• 输入：n = 10, pick = 6

• 输出：6

• 输入：n = 1, pick = 1

• 输出：1

• 输入：n = 2, pick = 1

• 输出：1

• 输入：n = 2, pick = 2
• 输出：2

提示：

• 1 <= n <= 2^31 - 1
• 1 <= pick <= n

解题思路：

1. 二分搜索
2. 调用guess函数，来判断中间元素是否是目标值

解题步骤：

1. 从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束
2. 如果目标值大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找

复杂度：

1. 时间复杂度：O（logN）
2. 空间复杂度：O（1）

/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return              -1 if num is lower than the guess number
 *                       1 if num is higher than the guess number
 *                       otherwise return 0
 * var guess = function(num) {}
 */

/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function(n) {
    let low = 1;
    let high = n;
    while(low <= high){
        const mid = Math.floor((low + high) / 2);
        const res = guess(mid);
        // console.log('mid', mid);
        // console.log('res', res);
        if(res === 0){
            return mid;
        } else if (res === 1){
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
};

排序与搜索-章节总结

排序和搜索是什么？

• 排序：把某个乱序的数组变成升序或者降序的数组
• 搜索：找出数组中某个元素的下标

  JS中的排序和搜索

• JS中的排序：数组的sort方法
• JS中的搜索：数组的indexOf方法

  排序算法：

• 冒泡排序 O(n²)
• 选择排序 O(n²)
• 插入排序 O(n²)
• 归并排序 O(nlogn)
• 快速排序 O(nlogn)

  搜索算法

• 顺序搜索 O(n)
• 二分搜索 O(logn)

阶段性思考

1. Chrome 最新的Array.prototype.sort用的是什么排序算法？
2. 用二分搜索算法求x的平方根。题目链接：http://leetcode-cn.com/problems/sqrtx/

堆是什么？

• 堆是一种特殊的完全二叉树

• 所有的节点都大于等于(最大堆)或小于等于（最小堆）它的子节点

  

JS中的堆

• JS中通常用数组表示堆
• 左侧子节点的位置是 2 * index + 1
• 右侧子节点的位置是 2 * index + 2

• 父节点位置是（index - 1）/ 2 的商

  

堆的应用

• 堆能高效。快速地找出最大值和最小值，时间复杂度：O（1）
• 找出第k个最大（小）元素

第k个最大（最小）元素

• 构建一个最小（最大）堆，并将元素依次插入堆中
• 当堆的容量超过k，就删除堆顶
• 插入结束后，堆顶就是第k个最大元素

JavaScript 实现最小堆类

实现步骤：

• 在类里，声明一个数组，用来装元素
• 主要方法：插入，删除堆顶，获取堆顶，获取堆大小

插入：

• 将值插入堆的底部，即数组的尾部
• 然后上移：将这个值和它的父节点进行交换，直到父节点小于等于这个插入的值
• 大小为k的堆中插入元素的时间复杂度为O（logK）

删除堆顶

• 用数组尾部元素替换堆顶（直接删除堆顶会破坏堆结构）
• 然后下移：将新堆顶和它的子节点进行交换，直到子节点大于等于这个新堆顶
• 大小为k的堆中删除堆顶的时间复杂度为O（logK）

获取堆顶和堆的大小

• 获取堆顶：返回数组的头部
• 获取堆的大小：返回数组的长度

// 最小堆实现
class MinHeap{
  constructor(){
    this.heap = [];
  }
  // 交换
  swap(i1, i2){
    const temp = this.heap[i1];
    this.heap[i1] = this.heap[i2];
    this.heap[i2] = temp;
  }
  getParentIndex(i){
    // return Math.floor((i - 1) / 2)
    // 进阶写法，二进制操作，二进制右移一位，即除以2
    // 父节点位置是（index - 1）/ 2 的商
    return (i - 1) >> 1;
  }
  getLeftIndex(i){
    // 左侧子节点的位置是 2 * index + 1
    return i * 2 + 1;
  }
  getRightIndex(i){
    // 右侧子节点的位置是 2 * index + 2
    return i * 2 + 2;
  }
  shiftUp(index){
    if(index == 0){ //如果是堆顶，就不再上移
      return;
    }
    const parentIndex = this.getParentIndex(index);
    if(this.heap[parentIndex] > this.heap[index]){
      this.swap(parentIndex, index);
      this.shiftUp(parentIndex);
    }
  }
  shiftDown(index){
    const leftIndex = this.getLeftIndex(index);
    const rightIndex = this.getRightIndex(index);
    if(this.heap[leftIndex] < this.heap[index]){
      this.swap(leftIndex, index);
      this.shiftDown(leftIndex);
    }
    if(this.heap[rightIndex] < this.heap[index]){
      this.swap(rightIndex, index);
      this.shiftDown(rightIndex);
    }
  }
  // 插入
  insert(value){
    this.heap.push(value);
    // 上移（保证堆的结构正确）
    this.shiftUp(this.heap.length-1);
  }
  pop(){
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
  }
  // 获取堆顶
  peek(){
    return this.heap[0];
  }
  // 获取堆的大小
  size(){
    return this.heap.length;
  }
}

const h = new MinHeap();
h.insert(3);
h.insert(2);
h.insert(1);
h.pop();

LeetCode #215 数组中的第k个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例:

• 输入: [3,2,1,5,6,4] 和 k = 2

• 输出: 5

• 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
• 输出: 4

解题思路：

1. 看大“第k个最大元素”
2. 考虑使用最小堆

解题步骤：

1. 构建一个最小堆，并依次把数组的值插入堆中
2. 当堆的容量超过k，就删除堆顶
3. 插入结束后，堆顶就是第k个最大元素

复杂度：

1. 时间复杂度：O（n * logk） （上移和下移操作是递归操作）
2. 空间复杂度：O（k）（实现的是堆，数组的就是它的空间复杂度）

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */

// 最小堆实现
class MinHeap{
  constructor(){
    this.heap = [];
  }
  // 交换
  swap(i1, i2){
    const temp = this.heap[i1];
    this.heap[i1] = this.heap[i2];
    this.heap[i2] = temp;
  }
  getParentIndex(i){
    // return Math.floor((i - 1) / 2)
    // 进阶写法，二进制操作，二进制右移一位，即除以2
    // 父节点位置是（index - 1）/ 2 的商
    return (i - 1) >> 1;
  }
  getLeftIndex(i){
    // 左侧子节点的位置是 2 * index + 1
    return i * 2 + 1;
  }
  getRightIndex(i){
    // 右侧子节点的位置是 2 * index + 2
    return i * 2 + 2;
  }
  shiftUp(index){
    if(index == 0){ //如果是堆顶，就不再上移
      return;
    }
    const parentIndex = this.getParentIndex(index);
    if(this.heap[parentIndex] > this.heap[index]){
      this.swap(parentIndex, index);
      this.shiftUp(parentIndex);
    }
  }
  shiftDown(index){
    const leftIndex = this.getLeftIndex(index);
    const rightIndex = this.getRightIndex(index);
    if(this.heap[leftIndex] < this.heap[index]){
      this.swap(leftIndex, index);
      this.shiftDown(leftIndex);
    }
    if(this.heap[rightIndex] < this.heap[index]){
      this.swap(rightIndex, index);
      this.shiftDown(rightIndex);
    }
  }
  // 插入
  insert(value){
    this.heap.push(value);
    // 上移（保证堆的结构正确）
    this.shiftUp(this.heap.length-1);
  }
  pop(){
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
  }
  // 获取堆顶
  peek(){
    return this.heap[0];
  }
  // 获取堆的大小
  size(){
    return this.heap.length;
  }
}

var findKthLargest = function(nums, k) {
    const heap = new MinHeap();
    // 把数组中的值依次插入到堆中
    nums.forEach(n => {
        heap.insert(n);
        // 当发现堆的大小超过k，部分元素出去
        if(heap.size() > k){
            heap.pop();
        }
    })
    // console.log(heap)
    return heap.peek();
};

LeetCode #347 前k个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例:

• 输入: nums = [1,1,1,2,2,3], k = 2

• 输出: [1,2]

• 输入: nums = 1, k = 1
• 输出: 1

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。 你可以按任意顺序返回答案

解题思路一：（统计所有的元素出现的频率）：

1. 利用map记录所有元素出现的频率
2. 对map进行转数组，然后降序排序
3. 然后通过找出k之前的频率返回出对应的元素

复杂度：

1. 时间复杂度：O（nlogn），原生排序最优的时间复杂度是 O（nlogn）。不符合题目要求
2. 空间复杂度：O（n）

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    // 实现： 统计所有元素出现的次数
    const map = new Map();
    nums.forEach(n => {
        map.set(n, map.has(n) ? map.get(n) + 1 : 1);
    })
    /**
     * 排序
     * 1. map 转数组
     * 2. 降序排序
     */ 
    const list = Array.from(map).sort((a,b) => b[1] - a[1]);
    // console.log(list)
    // console.log(map);
    return list.slice(0, k).map(n=>{
        return n[0]
    })
};

解题思路二：（堆的思路）

1. 建立一个最小堆
2. 把元素及频率插入到堆中
3. 按照频率排序

复杂度：

1. 时间复杂度：O（n logk）。因为1<= k <= n 所以 n logk < n * logn。符合题意
2. 空间复杂度：O（n）。字典复杂度是n 堆的复杂度是k ，k<n

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */

// 最小堆实现
class MinHeap{
  constructor(){
    this.heap = [];
  }
  // 交换
  swap(i1, i2){
    const temp = this.heap[i1];
    this.heap[i1] = this.heap[i2];
    this.heap[i2] = temp;
  }
  getParentIndex(i){
    // return Math.floor((i - 1) / 2)
    // 进阶写法，二进制操作，二进制右移一位，即除以2
    // 父节点位置是（index - 1）/ 2 的商
    return (i - 1) >> 1;
  }
  getLeftIndex(i){
    // 左侧子节点的位置是 2 * index + 1
    return i * 2 + 1;
  }
  getRightIndex(i){
    // 右侧子节点的位置是 2 * index + 2
    return i * 2 + 2;
  }
  shiftUp(index){
    if(index == 0){ //如果是堆顶，就不再上移
      return;
    }
    const parentIndex = this.getParentIndex(index);
    if(this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value){
      this.swap(parentIndex, index);
      this.shiftUp(parentIndex);
    }
  }
  shiftDown(index){
    const leftIndex = this.getLeftIndex(index);
    const rightIndex = this.getRightIndex(index);
    if(this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value){
      this.swap(leftIndex, index);
      this.shiftDown(leftIndex);
    }
    if(this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value){
      this.swap(rightIndex, index);
      this.shiftDown(rightIndex);
    }
  }
  // 插入
  insert(value){
    this.heap.push(value);
    // 上移（保证堆的结构正确）
    this.shiftUp(this.heap.length-1);
  }
  pop(){
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
  }
  // 获取堆顶
  peek(){
    return this.heap[0];
  }
  // 获取堆的大小
  size(){
    return this.heap.length;
  }
}

var topKFrequent = function(nums, k) {
    // 实现： 堆的思路，最小堆
    const map = new Map();
    nums.forEach(n => {
        map.set(n, map.has(n) ? map.get(n) + 1 : 1)
    })
    const heap = new MinHeap();
    map.forEach((value, key)=>{
        heap.insert({value, key});
        // 保证最小堆的尺寸永远小于k
        if(heap.size() > k){
            // 剔除最小的
            heap.pop();
        }
    })
    // console.log(heap)
    return heap.heap.map(obj => obj.key)
};

LeetCode #23 合并k个排序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

• 输入：lists = [[1,4,5],[1,3,4],[2,6]]
• 输出：[1,1,2,3,4,4,5,6]

• 解释：链表数组如下：

  [
  1->4->5,
  1->3->4,
  2->6
  ]
  将它们合并到一个有序链表中得到。
  1->1->2->3->4->4->5->6

  示例 2：

• 输入：lists = []
• 输出：[]

示例 3：

• 输入：lists = [[]]
• 输出：[]  

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

解题思路：

1. 新链表的下一个节点一定是k个链表头中的最小节点
2. 考虑选择使用最小堆

解题步骤：

1. 构建一个最小堆，并依次把链表头插入堆中
2. 弹出堆顶接到输出链表，并将堆顶所在链表的新链表头插入堆中
3. 堆元素全部弹出，合并工作就完成了。

复杂度：

1. 时间复杂度：O（n * logk）
2. 空间复杂度：O（k）

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
// 最小堆实现
class MinHeap{
  constructor(){
    this.heap = [];
  }
  // 交换
  swap(i1, i2){
    const temp = this.heap[i1];
    this.heap[i1] = this.heap[i2];
    this.heap[i2] = temp;
  }
  getParentIndex(i){
    // return Math.floor((i - 1) / 2)
    // 进阶写法，二进制操作，二进制右移一位，即除以2
    // 父节点位置是（index - 1）/ 2 的商
    return (i - 1) >> 1;
  }
  getLeftIndex(i){
    // 左侧子节点的位置是 2 * index + 1
    return i * 2 + 1;
  }
  getRightIndex(i){
    // 右侧子节点的位置是 2 * index + 2
    return i * 2 + 2;
  }
  shiftUp(index){
    if(index == 0){ //如果是堆顶，就不再上移
      return;
    }
    const parentIndex = this.getParentIndex(index);
    if(this.heap[parentIndex] && this.heap[parentIndex].val > this.heap[index].val){
      this.swap(parentIndex, index);
      this.shiftUp(parentIndex);
    }
  }
  // 下移
  shiftDown(index){
    const leftIndex = this.getLeftIndex(index);
    const rightIndex = this.getRightIndex(index);
    if(this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[index].val){
      this.swap(leftIndex, index);
      this.shiftDown(leftIndex);
    }
    if(this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val){
      this.swap(rightIndex, index);
      this.shiftDown(rightIndex);
    }
  }
  // 插入
  insert(value){
    this.heap.push(value);
    // 上移（保证堆的结构正确）
    this.shiftUp(this.heap.length-1);
  }
  // 弹出堆顶
  pop(){
    if(this.size() === 1){
        return this.heap.shift();
    }
    const top = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
    return top;
  }
  // 获取堆顶
  peek(){
    return this.heap[0];
  }
  // 获取堆的大小
  size(){
    return this.heap.length;
  }
}
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    // 输出链表
    const res = new ListNode(0);
    let p = res; // 声明指针，接入输入链表
    // 新建最小堆
    const heap = new MinHeap();
    // 把链表的头部节点都放在最小堆中
    lists.forEach(list => { // 循环所有链表
        if(list){
            heap.insert(list);
        }
    })
    while(heap.size()){
        // 弹出堆顶，即链表们中头部节点最小值
        const n = heap.pop(); 
        p.next = n;
        p = p.next; // 指针向下走
        if(n.next){ // 最小节点的next 插入到堆中
            heap.insert(n.next);
        } 
    }
    return res.next;  
};

堆-章节总结

• 堆是一种特殊的完全二叉树
• 所有的节点都大于等于（最大堆）或者小于等于（最小堆）它的子节点

• JS中通常用数组表示堆

• 堆能高效，快速地找出最大值和最小值，时间复杂度：O（1）
• 找出第k个最大（小）元素

一、业务背景 近期，我司在做相关云服务的拓扑架构感知，因此项目中最大也最复杂的功能就是拓扑图的实现，拓扑图和普通的图有一些不同的地方。

1. 拓扑图不同于其他简单图的实现，拓扑图是现实网络及节点的真实写照，因此会有很巨量的节点，因此性能是一个很大的问题需要被关注。也就是如何保证不卡顿，流畅。
2. 拓扑图往往存在不同的层级或维度，因此在实现过程中，会有不同维度的拓扑图的穿插出现。
3. 拓扑图是图的数据结构，但是某个节点的数据项中可能还是树的数据结构，且会有不同交集的节点存在连线问题。因此数据结构是很复杂的，在进行数据结构设计时要考虑充分。

二、实现方案对比

1、 免费方案

2、付费方案