堆

堆是完全二叉树的一种特例

堆上的任意节点值都必须大于等于（大顶堆）或小于等于（小顶堆）其左右子节点值

• 大顶堆

如果对一棵完全二叉树来说，它每个结点的结点值都不小于其左右孩子的结点值，这样的完全二叉树就叫做“大顶堆”，也就是说，在大顶堆中，根节点是堆中最大的元素；

• 小顶堆

若树中每个结点值都不大于其左右孩子的结点值，这样的完全二叉树就叫做“小顶堆”，在小顶堆中，根节点是堆中最小的元素；

图

图是一种（包含若干个节点），每个节点可以连接 0 个或多个元素

两个节点相连的部分称为边（edge）。节点也被称作顶点（vertice）。

图可以有环（cycle），即如果遍历图的顶点，某个顶点可以被访问超过一次。而没有环的图被称为无环图（acyclic graph）。

高频题

• 图

• 堆

最小的K个数(简单) (opens new window)

• 解法一：排序，取前k个数

const findKthLargest =function (nums,k){
  return  nums.sort((a,b)=>a-b).slice(0,k)

}
//时间复杂度：O(nlogn)
//空间复杂度：O(logn)

• 解法二：局部排序，冒泡

题目仅仅需要求出数组中的第K个最大元素，没必要对数组整体进行排序

可以使用冒泡排序，每次将最大的数在最右边冒泡出来，只冒泡 k次即可

let findKthLargest = function(nums, k) {
    // 进行k轮冒泡排序
    bubbleSort(nums, k)
    return nums[nums.length-k]
}

let bubbleSort = function(arr, k) {
    for (let i = 0; i < k; i++) {
        // 提前退出冒泡循环的标识位
        let flag = false;
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
                // 表示发生了数据交换
            }
        }
        // 没有数据交换
        if(!flag) break
    }
}

//时间复杂度：最好时间复杂度 O(n)，平均时间复杂度 O(n*k)
//空间复杂度：O(1)

• 解法三：构建大顶堆求 Top k问题

1. 从数组中取前 k 个数（ 0 到 k-1 位），构造一个大顶堆
2. 从 k 位开始遍历数组，每一个数据都和大顶堆的堆顶元素进行比较，如果大于堆顶元素，则不做任何处理，继续遍历下一元素；如果小于堆顶元素，则将这个元素替换掉堆顶元素，然后再堆化成一个大顶堆。
3. 遍历完成后，堆中的数据就是前 K 小的数据

/*利用堆求 Top k 问题的优势
这种求 Top k 问题是可以使用排序来处理，但当我们需要在一个动态数组中求 Top k 元素怎么办喃？

动态数组可能会插入或删除元素，难道我们每次求 Top k 问题的时候都需要对数组进行重新排序吗？那每次的时间复杂度都为 O(nlogn)

这里就可以使用堆，我们可以维护一个 K 大小的小顶堆，当有数据被添加到数组中时，就将它与堆顶元素比较，如果比堆顶元素大，则将这个元素替换掉堆顶元素，然后再堆化成一个小顶堆；如果比堆顶元素小，则不做处理。这样，每次求 Top k 问题的时间复杂度仅为 O(logk)
*/
let getLeastNumbers = function(arr, k) {
    // 从 arr 中取出前 k 个数，构建一个大顶堆
    let heap = [,], i = 0
    while(i < k) {
       heap.push(arr[i++]) 
    }
    buildHeap(heap, k)
    
    // 从 k 位开始遍历数组
    for(let i = k; i < arr.length; i++) {
        if(heap[1] > arr[i]) {
            // 替换并堆化
            heap[1] = arr[i]
            heapify(heap, k, 1)
        }
    }
    
    // 删除heap中第一个元素
    heap.shift()
    return heap
};

// 原地建堆，从后往前，自上而下式建大顶堆
let buildHeap = (arr, k) => {
    if(k === 1) return
    // 从最后一个非叶子节点开始，自上而下式堆化
    for(let i = Math.floor(k/2); i>=1 ; i--) {
        heapify(arr, k, i)
    }
}

// 堆化
let heapify = (arr, k, i) => {
    // 自上而下式堆化
    while(true) {
        let maxIndex = i
        if(2*i <= k && arr[2*i] > arr[i]) {
            maxIndex = 2*i
        }
        if(2*i+1 <= k && arr[2*i+1] > arr[maxIndex]) {
            maxIndex = 2*i+1
        }
        if(maxIndex !== i) {
            swap(arr, i, maxIndex)
            i = maxIndex
        } else {
            break
        }
    }
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

//时间复杂度：遍历数组需要 O(n) 的时间复杂度，一次堆化需要 O(logk) 时间复杂度，所以利用堆求 Top k 问题的时间复杂度为 O(nlogk)
//空间复杂度：O(k)

• 解法四：计数排序

1. 计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。

2. 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。它是一种典型的拿空间换时间的排序算法

let getLeastNumbers = function(arr, k) {
    return countingSort(arr, 10000, k)
}

let countingSort = (arr, maxValue, k) => {
    // 开辟的新的数组，用于将输入的数据值转化为键存储
    var bucket = new Array(maxValue + 1),
        sortedIndex = 0,
        arrLen = arr.length,
        bucketLen = maxValue + 1

    // 存储
    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0
        }
        bucket[arr[i]]++
    }

    // 将数据从bucket按顺序写入res中，控制仅仅输出前k个
    let res = []
    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j]-- > 0 && sortedIndex < k) {
            res[sortedIndex++] = j
        }
        if(sortedIndex === k) {
            break
        }
    }
    return res
}
//时间复杂度：O(n + m)，其中 m 表示数据范围
//空间复杂度：O(k + m) 同时V8也对数组提供了slow、fast存储，一定程度上提高了计数排序的性能

前K个高频元素(中等) (opens new window)

• 解法一: map+数组

利用 map 记录每个元素出现的频率，利用数组来比较排序元素

let topKFrequent = function(nums, k) {
    let map = new Map(), arr = [...new Set(nums)]
    nums.map((num) => {
        if(map.has(num)) map.set(num, map.get(num)+1)
        else map.set(num, 1)
    })
    
    return arr.sort((a, b) => map.get(b) - map.get(a)).slice(0, k);
};

//时间复杂度：O(nlogn)
//空间复杂度：O(n)

• 解法二 ：map+小顶堆

1. 遍历数据，统计每个元素的频率，并将元素(key)与出现的频率(value)保存到map中
2. 遍历 map ，将前k 个数，构造一个小顶堆
3. 从k位开始,继续遍历 map，每一个数据出现频率都和小顶堆的堆顶元素出现频率进行比较，如果小于堆顶元素，则不做任何处理，继续遍历下一元素；如果大于堆顶元素，则将这个元素替换掉堆顶元素，然后再堆化成一个小顶堆。
4. 遍历完成后,堆中的数据就是前k大的数据

 const topKFrequent =function(nums,k){
     let map =new Map(), heap =[]
     nums.map((num)=>{
        if(map.has(num)){
            map.set(num,map.get(num)+1)
        }else{
            map.set(num,1)
        }
     })

     // 如果元素数量小于等于 k
     if(map.size <=k){
         return [...map.keys()]
     }
     // 如果元素数量大于k,遍历map,构建小顶堆
     let i =0
     map.forEach(()=>{
         if(i<k){
             //取前k个建堆
             heap.push(key)
            //原地建立前k堆
             if(i === k-1) buildHeap(heap, map, k)
         }else if(map.get(heap[1])<value){
             //替换并堆化
             heap[1]=key
             //自上而下式堆化第一个元素
            heapify(heap, map, k, 1)
         }
        i++
     })
     //删除heap中第一个元素
     heap.shift()
     return heap
 }

// 原地建堆，从后往前，自上而下式建小顶堆
let buildHeap = (heap, map, k) => {
    if(k === 1) return
    // 从最后一个非叶子节点开始，自上而下式堆化
    for(let i = Math.floor(k/2); i>=1 ; i--) {
        heapify(heap, map, k, i)
    }
}

// 堆化
let heapify = (heap, map, k, i) => {
    // 自上而下式堆化
    while(true) {
        let minIndex = i
        if(2*i <= k && map.get(heap[2*i]) < map.get(heap[i])) {
            minIndex = 2*i
        }
        if(2*i+1 <= k && map.get(heap[2*i+1]) < map.get(heap[minIndex])) {
            minIndex = 2*i+1
        }
        if(minIndex !== i) {
            swap(heap, i, minIndex)
            i = minIndex
        } else {
            break
        }
    }
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

//时间复杂度：遍历数组需要 O(n) 的时间复杂度，一次堆化需要 O(logk) 时间复杂度，所以利用堆求 Top k 问题的时间复杂度为 O(nlogk)
//空间复杂度：O(k)

• 解法三: 桶排序

1. 首先使用 map 来存储频率
2. 然后创建一个数组（有数量的桶），将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标（桶内）即可

const topKFrequent = function(nums, k) {
    let map = new Map(), arr = [...new Set(nums)]
    nums.map((num) => {
        if(map.has(num)) map.set(num, map.get(num)+1)
        else map.set(num, 1)
    })
    
    // 如果元素数量小于等于 k
    if(map.size <= k) {
        return [...map.keys()]
    }
    
    return bucketSort(map, k)
};

// 桶排序
const bucketSort = (map, k) => {
    let arr = [], res = []
    map.forEach((value, key) => {
        // 利用映射关系（出现频率作为下标）将数据分配到各个桶中
        if(!arr[value]) {
            arr[value] = [key]
        } else {
            arr[value].push(key)
        }
    })
    // 倒序遍历获取出现频率最大的前k个数
    for(let i = arr.length - 1;i >= 0 && res.length < k;i--){
        if(arr[i]) {
            res.push(...arr[i])
        }
	}
	return res
}

数组中的第K个最大元素(中等) (opens new window)

1. 第一步构建初始堆：是自底向上构建，从最后一个非叶子节点开始。

2. 第二步就是下沉操作让尾部元素与堆顶元素交换，最大值被放在数组末尾，并且缩小数组的length，不参与后面大顶堆的调整

3. 第三步就是调整：是从上到下，从左到右,因为堆顶元素下沉到末尾了，要重新调整这颗大顶堆

 // 整个流程就是上浮下沉
var findKthLargest = function(nums, k) {
   let heapSize=nums.length
    buildMaxHeap(nums,heapSize) // 构建好了一个大顶堆
    // 进行下沉 大顶堆是最大元素下沉到末尾
    for(let i=nums.length-1;i>=nums.length-k+1;i--){
        swap(nums,0,i)
        --heapSize // 下沉后的元素不参与到大顶堆的调整
        // 重新调整大顶堆
         maxHeapify(nums, 0, heapSize);
    }
    return nums[0]
   // 自下而上构建一颗大顶堆
   function buildMaxHeap(nums,heapSize){
     for(let i=Math.floor(heapSize/2)-1;i>=0;i--){
        maxHeapify(nums,i,heapSize)
     }
   }
   // 从左向右，自上而下的调整节点
   function maxHeapify(nums,i,heapSize){
       let l=i*2+1
       let r=i*2+2
       let largest=i
       if(l < heapSize && nums[l] > nums[largest]){
           largest=l
       }
       if(r < heapSize && nums[r] > nums[largest]){
           largest=r
       }
       if(largest!==i){
           swap(nums,i,largest) // 进行节点调整
           // 继续调整下面的非叶子节点
           maxHeapify(nums,largest,heapSize)
       }
   }

   function swap(a,  i,  j){
        let temp = a[i];
        a[i] = a[j];
        a[j] = temp;
   }
};

数据流中的中位数(困难) (opens new window)

1. 使用两个堆，来存储数据流

2. 使用最小堆A保存较大的一半，最大堆B保存较小的一半

3. 若总长度N为奇数，则A个数为(N+1)/2，B个数为(N-1)/2

4. 若总长度N为偶数，则A个数为N/2，B个数为N/2

5. 插入操作：当N为偶数，需要向A添加一个元素，先将num插入B，再将B堆顶弹出，插入A

6. 插入操作：当N为奇数，需要向B添加一个元素，先将num插入A，再将A堆顶弹出，插入B

7. 中位数：可以由A和B的堆顶元素得到，若N为奇数，中位数=A的堆顶；若N为偶数，则中位数=(A的堆顶+B的堆顶)/2

const MedianFinder = function () {
    // 默认最大堆
    const defaultCmp = (x, y) => x > y;
    // 交换元素
    const swap = (arr, i, j) => ([arr[i], arr[j]] = [arr[j], arr[i]]);
    // 堆类，默认最大堆
    class Heap {
        constructor(cmp = defaultCmp) {
            this.container = [];
            this.cmp = cmp;
        }
        // 插入
        insert(data) {
            const { container, cmp } = this;
            container.push(data);
            let index = this.size() - 1;
            while (index) {
                let parent = (index - 1) >> 1;
                if (!cmp(container[index], container[parent])) {
                    return;
                }
                swap(container, index, parent);
                index = parent;
            }
        }
        // 弹出堆顶，并返回
        pop() {
            const { container, cmp } = this;
            if (!this.size()) {
                return null;
            }

            swap(container, 0, this.size() - 1);
            const res = container.pop();
            const length = this.size();
            let index = 0,
                exchange = index * 2 + 1;

            while (exchange < length) {
                // // 以最大堆的情况来说：如果有右节点，并且右节点的值大于左节点的值
                let right = index * 2 + 2;
                if (right < length && cmp(container[right], container[exchange])) {
                    exchange = right;
                }
                if (!cmp(container[exchange], container[index])) {
                    break;
                }
                swap(container, exchange, index);
                index = exchange;
                exchange = index * 2 + 1;
            }

            return res;
        }
        // 获取堆大小
        size() {
            return this.container.length;
        }
        // 获取堆顶
        peek() {
            if (this.size()) return this.container[0];
            return null;
        }
    }
    // 最小堆
    this.A = new Heap();
    // 最大堆
    this.B = new Heap((x, y) => x < y);
};

MedianFinder.prototype.addNum = function (num) {
    if (this.A.size() !== this.B.size()) {
        // 当N为奇数，需要向B添加一个元素
        // 先将num插入A，再将A堆顶弹出，插入B
        this.A.insert(num);
        this.B.insert(this.A.pop());
    } else {
        // 当N为偶数，需要向A添加一个元素
        // 先将num插入B，再将B堆顶弹出，插入A
        this.B.insert(num);
        this.A.insert(this.B.pop());
    }
};

MedianFinder.prototype.findMedian = function () {
    // 若总和为偶数，返回两个堆顶的平均数
    // 若总和为奇数，返回A的堆顶
    return this.A.container.length === this.B.container.length
        ? (this.A.peek() + this.B.peek()) / 2
        : this.A.peek();
};

传递信息(简单) (opens new window)

• DP

dp[k][n−1] 即为总的方案数。

var numWays = function(n, relation, k) {
    let dp = new Array(n).fill(0);
    dp[0] = 1;
    for (let i = 0; i < k; i++) {
        const next = new Array(n).fill(0);
        for (const [src, dst] of relation) {
            next[dst] += dp[src];
        }
        dp = next;
    }
    return dp[n - 1];
};

• DFS

可以把传信息的关系看成有向图，每个玩家对应一个节点，每个传信息的关系对应一条有向边。如果 xx 可以向 yy 传信息，则对应从节点 xx 到节点 yy 的一条有向边。寻找从编号 00 的玩家经过 kk 轮传递到编号 n-1n−1 的玩家处的方案数，等价于在有向图中寻找从节点 00 到节点 n-1n−1 的长度为 kk 的路径数，同一条路径可以重复经过同一个节点。

可以使用深度优先搜索计算方案数。从节点 00 出发做深度优先搜索，每一步记录当前所在的节点以及经过的轮数，当经过 kk 轮时，如果位于节点 n-1n−1，则将方案数加 11。搜索结束之后，即可得到总的方案数。

具体实现方面，可以对传信息的关系进行预处理，使用列表存储有向边的关系，即可在 O(1)O(1) 的时间内得到特定节点的相邻节点（即可以沿着有向边一步到达的节点）。

var numWays = function(n, relation, k) {
    let ways = 0;
    const edges = new Array(n).fill(0).map(() => new Array());

    for (const [src, dst] of relation) {
        edges[src].push(dst);
    }

    const dfs = (index, steps) => {
        if (steps === k) {
            if (index === n - 1) {
                ways++;
            }
            return;
        }
        const list = edges[index];
        for (const nextIndex of list) {
            dfs(nextIndex, steps + 1);
        }
    }
    
    dfs(0, 0);
    return ways;
}

• BFS广度优先搜索

也可以使用广度优先搜索计算方案数。从节点 00 出发做广度优先搜索，当遍历到 kk 层时，如果位于节点 n-1n−1，则将方案数加 11。搜索结束之后，即可得到总的方案数。

var numWays = function(n, relation, k) {
    const edges = new Array(n).fill(0).map(() => new Array());
    for (const[src, dst] of relation) {
        edges[src].push(dst);
    }

    let steps = 0;
    const queue = [0];
    while (queue.length && steps < k) {
        steps++;
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const index = queue.shift();
            const list = edges[index];
            for (const nextIndex of list) {
                queue.push(nextIndex);
            }
        }
    }

    let ways = 0;
    if (steps === k) {
        while (queue.length) {
            if (queue.shift() === n - 1) {
                ways++;
            }
        }
    }
    return ways;
};

找到小镇的法官(简单) (opens new window)

• 寻找法官即是寻找 入度为N-1，出度为0的点

const findJudge = function(N, trust) {
  //构造0-N个节点的图
  let graph = Array.from({length:N+1}, () => ({outDegree:0, inDegree:0}))
  trust.forEach(([a, b]) => {
    graph[a].outDegree++
    graph[b].inDegree++
  })
  return graph.findIndex(({outDegree, inDegree}, index) => {
    //剔除0
    return index != 0 && outDegree === 0 && inDegree === N-1 
  })
};
//时间复杂度：O(N)
//空间复杂度：O(N)

• 解法二

其实法官也是唯一一个 出入度差值为 N-1 ，所以这里可以简化为寻找出入度差值为 N-1

const findJudge = function(N, trust) {
  let graph = Array(N+1).fill(0)
  // 出度加一
  // 入度减一
  trust.forEach(([a, b]) => {
    graph[a]--
    graph[b]++
  })
  return graph.findIndex((node, index) => {
    // 剔除0
    return index != 0 && node === N-1 
  })
};

岛屿数量中等) (opens new window)

• DFS深度优先遍历

1. 从起点 (i, j) 的上下左右四个方向进行深度搜索。
2. 搜索过程中，将搜索过的岛屿标记为 '0'。
3. 遍历整个矩阵，当 grid[i][j] === '1' 时，进行搜索并且将岛屿数加 1。
4. 注意递归终止条件

const numIslands =function(grid){
    const dfs =function(grid,i,j){
        if(i<0 || i>= grid.length || j<0 || j>=grid[0].length || grid[i][j] ==='0') return 
        grid[i][j]='0'
        dfs(grid,i+1,j)
        dfs(grid,i,j+1)
        dfs(grid,i-1,j)
        dfs(grid,i,j-1)
    }
    let count =0
    for(let i = 0;i<grid.length;i++){
        for(let j =0;j<grid[0].length;j++){
            if(grid[i][j]==='1'){
                dfs[grid,i,j]
                count++
            }
        }
    }
    return count
}

课程表(中等) (opens new window)

• 广度优先遍历

使用 邻接表 来表示有向图中各个节点的依赖关系，同时维护一个入度表，则入度表中入度为 0 的节点所表示的课程是可以立即开始学习的（没有先决条件条件或先觉条件已完成）

1. 创建一个队列，并将临接表中所有入度为 0 的节点放入队列中
2. 若队列非空，则从队列中出队第一个节点，numCourse — （学习该课程），然后将将依赖该课程所有临接节点的入度减 1
3. 若减 1 后节点入度为 0，则该课程又是可立即学习课程，将该节点添加到队尾
4. 若减 1 后节点入度不为 0 ，则继续遍历下一节点
5. 当队列为空，检查 numCourses === 0 （所有课程是否全部学习结束）即可

const canFinish = function(numCourses, prerequisites) {
    // 如果没有先决条件，即所有的课程均没有依赖关系
    // 直接返回 true
    if (prerequisites.length === 0) {
        return true
    }

    // 维护入度表
    let inDegree = new Array(numCourses).fill(0)
    // 维护临接表
    let adj = new Map()
    
    for (let e of prerequisites) {
        inDegree[e[0]]++
        if(!adj.has(e[1])) adj.set(e[1], [])
        let vEdge = adj.get(e[1])
        vEdge.push(e[0])
    }

    let queue = []
    // 首先加入入度为 0 的结点
    for (let i = 0; i < numCourses; i++) {
        if (inDegree[i] === 0) {
            queue.push(i)
        }
    }

    while (queue.length > 0) {
        // 从队首移除
        var v = queue.shift() 
        // 出队一门课程
        numCourses--
        if(!adj.has(v)) continue
        // 遍历当前出队结点的所有临接结点
        for(let w of adj.get(v)) {
            inDegree[w]--
            if (inDegree[w] === 0) {
                queue.push(w)
            }
        }
    }
    return numCourses === 0
}
//时间复杂度：O(V+E)，遍历一个图需要访问所有节点和边
//间复杂度：O(V+E)，用于存储临接表等

螺旋矩阵(中等) (opens new window)

• 按对角线反转后再逐行倒序

var rotate = function(matrix) {
    const n = matrix.length;
    //对角线反转 0,0  n-1,n-1
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < i; j++) {
            swap(matrix, [i, j], [j, i]);
        }
    }

    //中线左右反转
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < n / 2; j++) {
            swap(matrix, [i, j], [i, n - 1 - j]);
        }
    }

    function swap(matrix, [x1, y1], [x2, y2]) {
        const tmp = matrix[x1][y1];
        matrix[x1][y1] = matrix[x2][y2];
        matrix[x2][y2] = tmp;
    }
};

螺旋矩阵II(中等) (opens new window)

const generateMatrix = (n) => {
    // 定义一个二维数组进行数据保存
    const result = []
    for (let i = 0; i < n; i++) {
        result.push(new Array(n))
    }
    let left = 0
    let right = n - 1
    let top = 0
    let bottom = n - 1
    let current = 1, max = n * n
    while(current <= max) {
        // 上面从左到右
        for (let i = left; i <= right; i++) {
            result[top][i] = current++
        }
        top ++
        // 右边从上到下
        for (let i = top; i <= bottom; i++) {
            result[i][right] = current++
        }
        right --
        // 下边从右到左
        for (let i = right; i >= left; i--) {
            result[bottom][i] = current++
        }
        bottom --
        // 左边从下到上
        for (let i = bottom; i >= top; i--) {
            result[i][left] = current++
        }
        left ++
    }
    return result
}