数据结构与算法 -> 大顶堆与小顶堆

一、大顶堆

• 大顶堆是一种数据结构，它是一颗完全二叉树，并且满足以下性质：
  • 每个节点的值都大于或等于它的子节点的值
  • 因此，大顶堆的根节点（也称为堆顶）总是最大的元素

二、小顶堆

• 小顶堆也是一种数据结构，它是一颗完全二叉树，并且满足以下性质：
  • 每个节点的值都小于或等于它的子节点的值
  • 因此，小顶堆的根节点（也称为堆顶）总是最小的元素

三、主要区别

• 小顶堆和大顶堆是堆这种数据结构的两种形式，它们都是一颗完全二叉树，并且满足特定的性质。小顶堆的堆顶元素是最小的元素，而大顶堆的堆顶元素是最大的元素。小顶堆和大顶堆常用于实现优先队列，其操作的时间复杂度通常为O(log n)。

• 小顶堆和大顶堆的区别在于它们的堆顶元素分别是最小的和最大的元素。因此，小顶堆通常用于求出数据集中的最小值，而大顶堆通常用于求出数据集中的最大值。

四、算法模板1.大顶堆模板

// 大顶堆模板class MaxHeap {        constructor() {            this.heap = [];        }            // 返回堆的大小        size() {            return this.heap.length;        }            // 向堆中插入一个新元素        insert(val) {            // 将新元素添加到堆的末尾            this.heap.push(val);            // 调整堆使其满足大顶堆的性质            this.heapifyUp();        }            // 删除堆顶元素        deleteTop() {            // 如果堆为空，则直接返回            if (this.size() === 0) return;            // 将堆顶元素与堆的最后一个元素交换            let temp = this.heap[0];            this.heap[0] = this.heap[this.size() - 1];            this.heap[this.size() - 1] = temp;            // 将堆的最后一个元素从堆中删除            this.heap.pop();            // 调整堆使其满足大顶堆的性质            this.heapifyDown();        }            // 调整堆使其满足大顶堆的性质        heapifyUp() {            // 获取新插入的元素的索引            let index = this.size() - 1;            // 循环，直到该元素的值大于等于它的父节点的值            while (index > 0 && this.heap[index] > this.heap[this.parent(index)]) {                // 将该元素与它的父节点交换                let temp = this.heap[index];                this.heap[index] = this.heap[this.parent(index)];                this.heap[this.parent(index)] = temp;                // 更新索引                index = this.parent(index);            }        }            // 调整堆使其满足大顶堆的性质        heapifyDown() {            // 获取堆顶元素的索引            let index = 0;            // 循环，直到该元素的值小于等于它的子节点的值            while (index < this.size() && this.heap[index] = this.size()) return -Infinity;            if (rightChildIndex >= this.size()) return this.heap[leftChildIndex];            return Math.max(this.heap[leftChildIndex], this.heap[rightChildIndex]);        }            // 返回给定索引的元素的子节点中的最大值的索引        maxChildIndex(index) {            let leftChildIndex = this.leftChild(index);            let rightChildIndex = this.rightChild(index);            if (leftChildIndex >= this.size()) return -1;            if (rightChildIndex >= this.size()) return leftChildIndex;            return this.heap[leftChildIndex] > this.heap[rightChildIndex] ? leftChildIndex : rightChildIndex;        }    }

2.小顶堆模板

// 小顶堆模板class MinHeap {        constructor() {            // 初始化堆数组            this.heap = [];        }            // 获取父节点的索引        getParentIndex(childIndex) {            return Math.floor((childIndex - 1) / 2);        }            // 获取左子节点的索引        getLeftChildIndex(parentIndex) {            return 2 * parentIndex + 1;        }            // 获取右子节点的索引        getRightChildIndex(parentIndex) {            return 2 * parentIndex + 2;        }            // 判断是否存在父节点        hasParent(index) {            return this.getParentIndex(index) >= 0;        }            // 判断是否存在左子节点        hasLeftChild(index) {            return this.getLeftChildIndex(index) < this.heap.length;        }            // 判断是否存在右子节点        hasRightChild(index) {            return this.getRightChildIndex(index)  this.heap[index]) {                this.swap(this.getParentIndex(index), index);                index = this.getParentIndex(index);            }        }            // 从上往下重新排序        heapifyDown() {            let index = 0;            // 只要当前节点有左子节点            while (this.hasLeftChild(index)) {                let smallerChildIndex = this.getLeftChildIndex(index);                // 如果当前节点有右子节点，并且右子节点的值比左子节点的值小，就把右子节点的索引赋给smallerChildIndex                if (this.hasRightChild(index) && this.rightChild(index) < this.leftChild(index)) {                    smallerChildIndex = this.getRightChildIndex(index);                }                // 如果当前节点的值已经比子节点的值小，就退出循环                if (this.heap[index] < this.heap[smallerChildIndex]) {                    break;                } else {                    // 否则交换它们的值，并继续循环                    this.swap(index, smallerChildIndex);                }                index = smallerChildIndex;            }        }    }

五、力扣实操1.大顶堆例题：

第 327 场周赛T2 – 执行 K 次操作后的最大分数

• 

• 代码如下：

  • 

  • /** * @param {number[]} nums * @param {number} k * @return {number} */var maxKelements = function(nums, k) {    let score = []    let heap = new MaxHeap()    for (let item of nums) {        heap.insert(item)    }    while (k) {        let max = heap.heap[0]        score.push(max)        max = Math.ceil(max / 3)        heap.heap[0] = max        heap.heapifyDown()        k--    }    return score.reduce((item, total) => { return item + total }, 0)};// 大顶堆模板class MaxHeap {    constructor() {        this.heap = [];    }    // 返回堆的大小    size() {        return this.heap.length;    }    // 向堆中插入一个新元素    insert(val) {        // 将新元素添加到堆的末尾        this.heap.push(val);        // 调整堆使其满足大顶堆的性质        this.heapifyUp();    }    // 删除堆顶元素    deleteTop() {        // 如果堆为空，则直接返回        if (this.size() === 0) return;        // 将堆顶元素与堆的最后一个元素交换        let temp = this.heap[0];        this.heap[0] = this.heap[this.size() - 1];        this.heap[this.size() - 1] = temp;        // 将堆的最后一个元素从堆中删除        this.heap.pop();        // 调整堆使其满足大顶堆的性质        this.heapifyDown();    }    // 调整堆使其满足大顶堆的性质    heapifyUp() {        // 获取新插入的元素的索引        let index = this.size() - 1;        // 循环，直到该元素的值大于等于它的父节点的值        while (index > 0 && this.heap[index] > this.heap[this.parent(index)]) {            // 将该元素与它的父节点交换            let temp = this.heap[index];            this.heap[index] = this.heap[this.parent(index)];            this.heap[this.parent(index)] = temp;            // 更新索引            index = this.parent(index);        }    }    // 调整堆使其满足大顶堆的性质    heapifyDown() {        // 获取堆顶元素的索引        let index = 0;        // 循环，直到该元素的值小于等于它的子节点的值        while (index < this.size() && this.heap[index] = this.size()) return -Infinity;        if (rightChildIndex >= this.size()) return this.heap[leftChildIndex];        return Math.max(this.heap[leftChildIndex], this.heap[rightChildIndex]);    }    // 返回给定索引的元素的子节点中的最大值的索引    maxChildIndex(index) {        let leftChildIndex = this.leftChild(index);        let rightChildIndex = this.rightChild(index);        if (leftChildIndex >= this.size()) return -1;        if (rightChildIndex >= this.size()) return leftChildIndex;        return this.heap[leftChildIndex] > this.heap[rightChildIndex] ? leftChildIndex : rightChildIndex;    }}

2.小顶堆例题：

面试题 17.14. 最小K个数 – 力扣（LeetCode）

• 

• 代码如下：

  • 

  • /** * @param {number[]} arr * @param {number} k * @return {number[]} */var smallestK = function(arr, k) {    let res = []    let heap = new MinHeap()    for (let item of arr) {        heap.add(item)    }    while (k) {        let min = heap.heap[0]        res.push(min)        heap.heap[0] = Number.MAX_VALUE        min = heap.heap[0]        heap.heapifyDown()        k--    }    return res};// 小顶堆模板class MinHeap {    constructor() {        // 初始化堆数组        this.heap = [];    }    // 获取父节点的索引    getParentIndex(childIndex) {        return Math.floor((childIndex - 1) / 2);    }    // 获取左子节点的索引    getLeftChildIndex(parentIndex) {        return 2 * parentIndex + 1;    }    // 获取右子节点的索引    getRightChildIndex(parentIndex) {        return 2 * parentIndex + 2;    }    // 判断是否存在父节点    hasParent(index) {        return this.getParentIndex(index) >= 0;    }    // 判断是否存在左子节点    hasLeftChild(index) {        return this.getLeftChildIndex(index) < this.heap.length;    }    // 判断是否存在右子节点    hasRightChild(index) {        return this.getRightChildIndex(index)  this.heap[index]) {            this.swap(this.getParentIndex(index), index);            index = this.getParentIndex(index);        }    }    // 从上往下重新排序    heapifyDown() {        let index = 0;        // 只要当前节点有左子节点        while (this.hasLeftChild(index)) {            let smallerChildIndex = this.getLeftChildIndex(index);            // 如果当前节点有右子节点，并且右子节点的值比左子节点的值小，就把右子节点的索引赋给smallerChildIndex            if (this.hasRightChild(index) && this.rightChild(index) < this.leftChild(index)) {                smallerChildIndex = this.getRightChildIndex(index);            }            // 如果当前节点的值已经比子节点的值小，就退出循环            if (this.heap[index] < this.heap[smallerChildIndex]) {                break;            } else {                // 否则交换它们的值，并继续循环                this.swap(index, smallerChildIndex);            }            index = smallerChildIndex;        }    }}