堆、二叉堆
定义
堆(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;
};