一、大顶堆

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

二、小顶堆

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

三、主要区别

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

最新文章

1. 数据分析师的福音——VS 2017带来一体化的数据分析开发环境
2. javaScript封装的各种写法
3. php连接ftp的研究,自带ftp函数 | fsockopen | curl实现ftp的连接
4. 三级联动查询全国省市区（xml与数据库）
5. linux 病毒 sfewfesfs
6. C# Socket 入门4 UPD 发送结构体(转)
7. Visual C++ 对话框增加菜单栏
8. oracle 报“无效数字”异常和“ORA-01830: 日期格式图片在转换整个输入字符串之前结束”
9. python成长之路11
10. 产生AJAX跨域问题的原因
11. SpringCloud学习之soa基础
12. Android大学课件SQLite3 数据库操作
13. spark-sql(spark sql cli)客户端集成hive
14. IOS_多线程
15. django配置连接多个数据库，自定义表名称
16. Linux登录欢迎图案
17. EasyFastCMS系列教学课程——2、底层代码 ModelHelper与SQLHelper简介
18. 使用MapReduce将mysql数据导入HDFS
19. debiand上安装thunderbird
20. 德尔福 XE5 安卓调试

热门文章

1. python查找相似图片或重复图片
2. 四、Pod 介绍
3. linux清理内存缓存cache
4. JavaSPI详解
5. easyclick 学习
6. Git安装与常用操作
7. PHP 正在“杀死”Python
8. 面试官不按套路，竟然问我Java线程池是怎么统计线程空闲时间？
9. PHP 0817
10. tesseract-orc训练 结合python3图像识别验证码