JavaScript数据结构 + leetcode

本文记录一些堆的知识和高频题。本文知识总结和代码参考自JavaScript数据结构与算法。

什么是堆

堆是一种特殊的完全二叉树。
所有的节点都大于等于(最大堆)或小于等于(最小堆)它的子节点。
JS中通常用数组表示堆。
左侧子节点的位置是2 * index + 1。
右侧子节点的位置是2 * index + 2。
父节点的位置 (index – 1) / 2 取整。

堆的应用

堆能高效，快速地找出最大值和最小值。
时间复杂度：O(1)

最小堆实现

插入

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

class MinHeap {
    constructor() {
        this.heap = [];
    }
    // 当前节点和父节点交换位置
    swap(i1, i2) {
        [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
    }
    // 获取父节点的index值
    getParentIndex(i) {
        return ~~((i - 1 / 2));
    }
    // 上移插入进来的index的节点，直到它的父节点小于等于它
    shiftUp(index) {
        if (index === 0) return;
        const pIndex = this.getParentIndex(index);
        if (this.heap[pIndex] > shit.heap[index]) {
            this.swap(pIndex, index);
            this.shiftUp(pIndex);
        }
    }
    // 插入一个value值，开始执行上移操作
    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }
}

const h = new MinHeap();
h.insert(3);
h.insert(2);
h.insert(1);  // [1,3,2]
复制代码

删除堆顶

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

class MinHeap {
    constructor() {
        this.heap = [];
    }
    // 当前节点和父节点交换位置
    swap(i1, i2) {
        [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
    }
    // 获取父节点的index值
    getParentIndex(i) {
        return ~~((i - 1 / 2));
    }
    // 获取左侧子节点
    getLeftIndex(i) {
        return i * 2 + 1;
    }
    // 获取右侧子节点
    getRightIndex(i) {
        return i * 2 + 2;
    }
    // 上移插入进来的index的节点，直到它的父节点小于等于它
    shiftUp(index) {
        if (index === 0) return;
        const pIndex = this.getParentIndex(index);
        if (this.heap[pIndex] > this.heap[index]) {
            this.swap(pIndex, index);
            this.shiftUp(pIndex);
        }
    }
    // 下移，将这个节点和它的子节点进行交换，直到它的子节点大于等于它
    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);
        }
    }
    // 插入一个value值，开始执行上移操作
    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }
    pop() {
        this.heap[0] = this.heap.pop();
        this.shiftDown(0);
    }
}
const h = new MinHeap();
h.insert(3);
h.insert(2);
h.insert(1);  // [1,2,3]
h.pop(); // [2,3]
复制代码

获取堆顶和堆的大小

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

class MinHeap {
    constructor() {
        this.heap = [];
    }
    // 当前节点和父节点交换位置
    swap(i1, i2) {
        [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
    }
    // 获取父节点的index值
    getParentIndex(i) {
        return ~~((i - 1 / 2));
    }
    // 获取左侧子节点
    getLeftIndex(i) {
        return i * 2 + 1;
    }
    // 获取右侧子节点
    getRightIndex(i) {
        return i * 2 + 2;
    }
    // 上移插入进来的index的节点，直到它的父节点小于等于它
    shiftUp(index) {
        if (index === 0) return;
        const pIndex = this.getParentIndex(index);
        if (this.heap[pIndex] > shit.heap[index]) {
            this.swap(pIndex, index);
            this.shiftUp(pIndex);
        }
    }
    // 下移，将这个节点和它的子节点进行交换，直到它的子节点大于等于它
    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);
        }
    }
    // 插入一个value值，开始执行上移操作
    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;
    }
}
复制代码

leetcode 题目

215. 数组中的第K个最大元素

思路：

构建一个最小堆，并依次把数组的值插入堆中。
当堆的容易超过K，就删除堆顶。
插入结束后，堆顶就是第K个最大元素。

代码展示：

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
*/
class MinHeap {
    constructor() {
        this.heap = [];
    }
    swap(i1, i2) {
        [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
    }
    getParentIndex(i) {
        return ~~((i - 1) / 2);
    }
    getLeftIndex(i) {
        return i * 2 + 1;
    }
    getRightIndex(i) {
        return i * 2 + 2;
    }
    shiftUp(index) {
       if (index === 0) return;
       const pIndex = this.getParentIndex(index);
       if (this.heap[pIndex] > this.heap[index]) {
           this.swap(pIndex, index);
           this.shiftUp(pIndex);
       }
    }
    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) {
    if (nums.length < k || k <= 0) return;
    const h = new MinHeap();
    nums.forEach(item => {
        h.insert(item);
        if (h.size() > k) {
            h.pop();
        }
    });
    return h.peek();
}
复制代码

复杂度分析：

时间复杂度：O(nlogk)：n为数组的长度，k为堆的大小。
空间复杂度：O(n)

347. 前 K 个高频元素

思路：

方法一：

利用哈希表记录所有元素出现的次数，然后根据次数排序，最后取出前k个高频的元素即可

代码展示：

方法一：利用哈希表和排序

/**
 * @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);
  });
  const list = Array.from(map).sort((a, b) => b[1] - a[1]);
  return list.slice(0, k).map(n => n[0]);
};
复制代码

因为方法一使用了排序，所以时间复杂度最好也是O(nlogn)，不符合题意。

方法二：最小堆

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
class MinHeap {
  constructor() {
    this.heap = [];
  }
  swap(i1, i2) {
    [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
  }
  getLeftIndex(i) {
    return i * 2 + 1;
  }
  getRightIndex(i) {
    return i * 2 + 2;
  }
  getParentIndex(i) {
    return ~~((i - 1) / 2);
  }
  shiftUp(i) {
    if (i === 0) return;
    const pIndex = this.getParentIndex(i);
    if (this.heap[pIndex] && this.heap[pIndex].value > this.heap[i].value) {
      this.swap(pIndex, i);
      this.shiftUp(pIndex);
    }
  }
  shiftDown(i) {
    const lIndex = this.getLeftIndex(i);
    const rIndex = this.getRightIndex(i);
    if (this.heap[lIndex] && this.heap[lIndex].value < this.heap[i].value) {
      this.swap(lIndex, i);
      this.shiftDown(lIndex);
    }
    if (this.heap[rIndex] && this.heap[rIndex].value < this.heap[i].value) {
      this.swap(rIndex, i);
      this.shiftDown(rIndex);
    }
  }
  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 h = new MinHeap();
  const map = new Map();
  nums.forEach(n => {
    map.set(n, map.has(n) ? map.get(n) + 1 : 1);
  });
  map.forEach((value, key) => {
    h.insert({value, key});
    if (h.size() > k) {
      h.pop()
    }
  });
  return h.heap.map(n => n.key);
};
复制代码

复杂度分析：

时间复杂度：O(nlogk)
空间复杂度：O(n)

23. 合并K个升序链表

思路：

新链表的下一个节点一定是k个链表头中的最小节点。考虑使用最小堆。
构建一个最小堆，依次把链表头插入堆中。
弹出堆顶接到输出链表，并将堆顶所在链表的新链表头插入堆中。
等堆元素全部弹出，合并完成。

代码展示：

/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
class MinHeap {
  constructor() {
    this.heap = [];
  }
  swap(i1, i2) {
    [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
  }
  getLeftIndex(i) {
    return i * 2 + 1;
  }
  getRightIndex(i) {
    return i * 2 + 2;
  }
  getParentIndex(i) {
    return ~~((i - 1) / 2);
  }
  shiftUp(i) {
    if (i === 0) return;
    const pIndex = this.getParentIndex(i);
    if (this.heap[pIndex] && this.heap[pIndex].val > this.heap[i].val) {
      this.swap(pIndex, i);
      this.shiftUp(pIndex);
    }
  }
  shiftDown(i) {
    const lIndex = this.getLeftIndex(i);
    const rIndex = this.getRightIndex(i);
    if (this.heap[lIndex] && this.heap[lIndex].val < this.heap[i].val) {
      this.swap(lIndex, i);
      this.shiftDown(lIndex);
    }
    if (this.heap[rIndex] && this.heap[rIndex].val < this.heap[i].val) {
      this.swap(rIndex, i);
      this.shiftDown(rIndex);
    }
  }
  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;
  }
}
var mergeKLists = function(lists) {
  const res = new ListNode(0);
  const h = new MinHeap();
  let p = res;
  lists.forEach(l => {
    if (l) h.insert(l);
  });
  while (h.size()) {
    const n = h.pop();
    p.next = n;
    p = p.next;
    if (n.next) h.insert(n.next);
  }
  return res.next;
};
复制代码

复杂度分析：

时间复杂度：O(nlogk)
空间复杂度：O(n)

剑指 Offer 40. 最小的k个数

代码展示：

方法一：最大堆

class MaxHeap {
  constructor() {
    this.heap = [];
  }
  swap(i1, i2) {
    [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
  }
  getLeftIndex(i) {
    return i * 2 + 1;
  }
  getRightIndex(i) {
    return i * 2 + 2;
  }
  getParentIndex(i) {
    return ~~((i - 1) / 2);
  }
  shiftUp(index) {
    if (index === 0) return;
    const pIndex = this.getParentIndex(index);
    if (this.heap[pIndex] < this.heap[index]) {
      this.swap(pIndex, index);
      this.shiftUp(pIndex);
    }
  }
  shiftDown(index) {
    const lIndex = this.getLeftIndex(index);
    const rIndex = this.getRightIndex(index);
    if (this.heap[lIndex] > this.heap[index]) {
      this.swap(lIndex, index);
      this.shiftDown(lIndex);
    }
    if (this.heap[rIndex] > this.heap[index]) {
      this.swap(rIndex, index);
      this.shiftDown(rIndex);
    }
  }
  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 getLeastNumbers = function(arr, k) {
  if (k === 0) return [];
  const h = new MaxHeap();
  arr.forEach(n => {
    h.insert(n);
    if (h.size() > k) {
      h.pop();
    }
  });
  return h.heap;
};
复制代码

方法二：快速排序

var getLeastNumbers = function(arr, k) {
  if (k === 0) return [];
  const quickSort = (arr) => {
    if (arr.length <= 1) { return arr; }
    const val = arr[0];
    const leftArr = [], rightArr = [];
    for (let i = 1; i < arr.length; i++) {
      if (val < arr[i]) {
        rightArr.push(arr[i]);
      } else {
        leftArr.push(arr[i]);
      }
    }
    return [...quickSort(leftArr), val, ...quickSort(rightArr)];
  }
  return quickSort(arr).slice(0, k)
}
复制代码

方法三：sort排序

var getLeastNumbers = function(arr, k) {
  return arr.sort((a, b) => a - b).slice(0, k);
}
复制代码

复杂度分析：

时间复杂度：O(nlogk)
空间复杂度：O(n)

总结

堆可以解决前n个最小元素或最大元素的这一类问题，时间复杂度更优。

文章版权归作者所有，未经允许请勿转载。

THE END

前端

OwnCloud 输入验证漏洞

FFmpeg/Libav ‘adpcm_decode_frame’函数拒绝服务漏洞

前端跨域解决方案

CDS Software Consortium CDS Agenda ‘Sendalertemail.PHP’远程文件包含漏洞

RSA SecurID Software Token 任意代码执行漏洞

Libexif ‘exif_entry_get_value’函数整数下溢漏洞

JavaScript数据结构 + leetcode – 堆

什么是堆

堆的应用

最小堆实现

插入

删除堆顶

获取堆顶和堆的大小

leetcode 题目

总结