堆、二叉堆

定义

堆(Heap):可以迅速找到一堆数中的最大或者最小值的数据结构。

将根节点最大的堆叫做大顶堆,根节点最小的堆叫做小顶堆。常见的堆有二叉堆、斐波那契堆等。

以大顶堆为例,常见操作:

  • find-max:O(1)
  • delete-max:O(log n)
  • insert(create):O(log n) or O(1)

不同实现的比较:https://en.wikipedia.org/wiki/Heap_(data_structure)

堆有很多实现方式,二叉堆是堆的一种常见且简单的实现,但不是最优的实现。

二叉堆性质

通过完全二叉树来实现(注意:不是二叉搜索树);二叉搜索树的查询最小元素是 O(n) 的。

完全二叉树:除叶子结点之外,其他都是满的。

二叉堆(大顶)满足以下性质:

  • 是一颗完全树
  • 树中任意节点的值总是等于等于其子节点的值

二叉堆实现细节

二叉堆一般都是通过 ”数组“ 来实现。

假设 ”第一个元素“ 在数组中的索引为 0,则父节点和子节点的位置关系如下:

  • 索引为 i 的左子结点索引:2 * i + 1
  • 索引为 i 的右子结点索引:2 * i + 2
  • 索引为 i 的父结点索引:Math.floor((i - 1) / 2)

插入操作

新元素一律先插入堆的尾部;
依次向上调整整个堆的结构(一直到根);

HeapifyUp,O(log n)。

删除堆顶操作

将堆尾元素替换到顶部(即对顶被替代的删除掉);
依次从根部向下调整整个堆的结构(一直到堆尾即可);

HeapifyDown,O(logn)。

代码实现

class BinaryHeap { constructor (compare) { this.data = []; this.compare = compare; } swap (i1, i2) { [this.data[i1], this.data[i2]] = [this.data[i2], this.data[i1]]; } getParentIndex (i) { return (i - 1) >> 1; } getLeftIndex (i) { return i * 2 + 1; } getRightIndex (i) { return i * 2 + 2; } heapifyUp (curIdx) { if (curIdx == 0) return; const parentIdx = this.getParentIndex(curIdx); if (this.data[parentIdx] && this.compare(this.data[curIdx], this.data[parentIdx]) < 0) { this.swap(parentIdx, curIdx); this.heapifyUp(parentIdx); } } heapifyDown (curIdx) { const leftIdx = this.getLeftIndex(curIdx), rightIdx = this.getRightIndex(curIdx); if (this.data[leftIdx] && this.compare(this.data[leftIdx], this.data[curIdx]) < 0) { this.swap(leftIdx, curIdx); this.heapifyDown(leftIdx); } if (this.data[rightIdx] && this.compare(this.data[rightIdx], this.data[curIdx]) < 0) { this.swap(rightIdx, curIdx); this.heapifyDown(rightIdx); } } insert (val) { this.data.push(val); this.heapifyUp(this.size() - 1); } pop () { this.data[0] = this.data.pop(); this.heapifyDown(0); return this.data[0]; } peek () { return this.data[0]; } size () { return this.data.length; } }

堆排序:https://www.geeksforgeeks.org/heap-sort/

相关题目

最小的 k 个数(字节跳动在半年内面试中考过)

滑动窗口最大值(亚马逊在半年内面试中常考)

前 K 个高频元素(亚马逊在半年内面试中常考)

丑数(字节跳动在半年内面试中考过)

// 最小的 k 个数 // 思路1:sort,O(nlogn) // 思路2:heap,添加 O(nlogk) // 思路3:快速排序 /** * @param {number[]} arr * @param {number} k * @return {number[]} */ var getLeastNumbers = function(arr, k) { if (k == 0) return []; const heap = new BinaryHeap((a, b) => b - a); for (let i = 0; i < arr.length; i++) { heap.insert(arr[i]); if (heap.size() > k) heap.pop(); } return heap.data; };
// 滑动窗口最大值 // 思路1:大顶堆实现(超出时间限制,自定义的二叉堆需要优化) /** * @param {number[]} nums * @param {number} k * @return {number[]} */ var maxSlidingWindow = function(nums, k) { const heap = new BinaryHeap((a, b) => b[0] - a[0]); for (let i = 0; i < k - 1; i++) { heap.insert([nums[i], i]); } const res = []; for (let i = k -1; i < nums.length; i++) { heap.insert([nums[i], i]); while (heap.peek()[1] <= i - k) heap.pop(); res.push(heap.peek()[0]); } return res; }; // 思路2:双端队列实现 /** * @param {number[]} nums * @param {number} k * @return {number[]} */ var maxSlidingWindow = function(nums, k) { const queue = [], result = []; for (let i = 0; i < nums.length; i++) { while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) { queue.pop(); } queue.push(i); while (queue[0] <= i - k) { queue.shift(); } if (i >= k - 1) result.push(nums[queue[0]]); } return result; };
// 前 k 个高频元素 // 思路:小顶堆实现,时间复杂度 O(nlogk)、空间复杂度 O(n) /** * @param {number[]} nums * @param {number} k * @return {number[]} */ var topKFrequent = function(nums, k) { const map = new Map(); for(const num of nums) { map.set(num, (map.get(num) || 0) + 1); } const heap = new BinaryHeap((a, b) => a[1] - b[1]); for (const entry of map.entries()) { heap.insert(entry); if (heap.size() > k) heap.pop(); } return heap.data.map(item => item[0]); };
// 丑数 // 思路:小顶堆,时间复杂度 O(nlogn)、空间复杂度 O(n) /** * @param {number} n * @return {number} */ var nthUglyNumber = function(n) { const heap = new BinaryHeap((a, b) => a - b); const factors = [2, 3, 5]; const set = new Set(); set.add(1); heap.insert(1); let ugly = 0; for (let i = 0; i < n; i++) { ugly = heap.pop(); for (const factor of factors) { const next = ugly * factor; if (!set.has(next)) { set.add(next); heap.insert(next); } } } return ugly; };