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

时间：2023-01-13 11:07:59

一、大顶堆

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

二、小顶堆

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

三、主要区别

  • 小顶堆和大顶堆是堆这种数据结构的两种形式，它们都是一颗完全二叉树，并且满足特定的性质。小顶堆的堆顶元素是最小的元素，而大顶堆的堆顶元素是最大的元素。小顶堆和大顶堆常用于实现优先队列，其操作的时间复杂度通常为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.maxChildValue(index)) {
                // 获取该元素的子节点中的最大值的索引
                let maxChildIndex = this.maxChildIndex(index);
                // 将该元素与它的子节点中的最大值交换
                let temp = this.heap[index];
                this.heap[index] = this.heap[maxChildIndex];
                this.heap[maxChildIndex] = temp;
                // 更新索引
                index = maxChildIndex;
            }
        }
    
        // 返回给定索引的元素的父节点的索引
        parent(index) {
            return Math.floor((index - 1) / 2);
        }
    
        // 返回给定索引的元素的左子节点的索引
        leftChild(index) {
            return index * 2 + 1;
        }
    
        // 返回给定索引的元素的右子节点的索引
        rightChild(index) {
            return index * 2 + 2;
        }
    
        // 返回给定索引的元素的子节点中的最大值
        maxChildValue(index) {
            let leftChildIndex = this.leftChild(index);
            let rightChildIndex = this.rightChild(index);
            if (leftChildIndex >= 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.length;
        }
    
        // 获取左子节点的值
        leftChild(index) {
            return this.heap[this.getLeftChildIndex(index)];
        }
    
        // 获取右子节点的值
        rightChild(index) {
            return this.heap[this.getRightChildIndex(index)];
        }
    
        // 获取父节点的值
        parent(index) {
            return this.heap[this.getParentIndex(index)];
        }
    
        // 交换堆中两个节点的值
        swap(index1, index2) {
            [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
        }
    
        // 获取堆顶元素
        peek() {
            if (this.heap.length === 0) {
                throw new Error('Heap is empty');
            }
            return this.heap[0];
        }
    
        // 取出堆顶元素，并重新排序
        poll() {
            if (this.heap.length === 0) {
                throw new Error('Heap is empty');
            }
            const item = this.heap[0];
            this.heap[0] = this.heap.pop();
            this.heapifyDown();
            return item;
        }
    
        // 向堆中插入新元素，并重新排序
        add(item) {
            this.heap.push(item);
            this.heapifyUp();
        }
    
        // 从下往上重新排序
        heapifyUp() {
            let index = this.heap.length - 1;
            // 只要当前节点有父节点，并且父节点的值比当前节点的值大，就交换它们的值
            while (this.hasParent(index) && this.parent(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.maxChildValue(index)) {
            // 获取该元素的子节点中的最大值的索引
            let maxChildIndex = this.maxChildIndex(index);
            // 将该元素与它的子节点中的最大值交换
            let temp = this.heap[index];
            this.heap[index] = this.heap[maxChildIndex];
            this.heap[maxChildIndex] = temp;
            // 更新索引
            index = maxChildIndex;
        }
    }

    // 返回给定索引的元素的父节点的索引
    parent(index) {
        return Math.floor((index - 1) / 2);
    }

    // 返回给定索引的元素的左子节点的索引
    leftChild(index) {
        return index * 2 + 1;
    }

    // 返回给定索引的元素的右子节点的索引
    rightChild(index) {
        return index * 2 + 2;
    }

    // 返回给定索引的元素的子节点中的最大值
    maxChildValue(index) {
        let leftChildIndex = this.leftChild(index);
        let rightChildIndex = this.rightChild(index);
        if (leftChildIndex >= 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.length;
    }

    // 获取左子节点的值
    leftChild(index) {
        return this.heap[this.getLeftChildIndex(index)];
    }

    // 获取右子节点的值
    rightChild(index) {
        return this.heap[this.getRightChildIndex(index)];
    }

    // 获取父节点的值
    parent(index) {
        return this.heap[this.getParentIndex(index)];
    }

    // 交换堆中两个节点的值
    swap(index1, index2) {
        [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
    }

    // 获取堆顶元素
    peek() {
        if (this.heap.length === 0) {
            throw new Error('Heap is empty');
        }
        return this.heap[0];
    }

    // 取出堆顶元素，并重新排序
    poll() {
        if (this.heap.length === 0) {
            throw new Error('Heap is empty');
        }
        const item = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown();
        return item;
    }

    // 向堆中插入新元素，并重新排序
    add(item) {
        this.heap.push(item);
        this.heapifyUp();
    }

    // 从下往上重新排序
    heapifyUp() {
        let index = this.heap.length - 1;
        // 只要当前节点有父节点，并且父节点的值比当前节点的值大，就交换它们的值
        while (this.hasParent(index) && this.parent(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;
        }
    }
}
标签：

相关文章