最大堆

堆的基本存储结构是数组
插入删除的具体思路，
最大堆的前提是二叉搜索树，插入的思路是，先将数据插入到元素最末尾，然后依次与其父节点进行比较，如果比父节点大，则将父节点与其交换位置，直到父节点小于等于插入的数。

删除的思路，
先弹出最大的节点，然后将最后一个节点放到最大堆的堆顶，依次与子节点进行比较，与子节点中最大值进行比较，如果大于子节点的最大值，则退出循环，反之则与子节点中最大值进行交换，并继续与子节点进行比较。

JavaScript

class MaxHeap {
            constructor() {
                this.item = []
                this.item[0] = 1000000007
            }
            /**
             * @param {int} value 插入的值
             */
            push = (value) => {
                let item = this.item
                item.push(value)
                let k = this.size()
                while (item[Math.floor(k / 2)] < value) {
                    item[k] = item[Math.floor(k / 2)]
                    k = Math.floor(k / 2)
                }
                item[k] = value
            }
            /**
             * @return 去掉最大值，并返回值
             */
            pop = () => {
                if (this.isEmpty()) return Error('堆为空')
                let item = this.item
                let i, k, maxItem = item[1]
                let temp = item.pop()
                /*从根节点开始遍历*/
                for (i = 1; i * 2 <= this.size(); i = k) {
                    k = i * 2
                    if (k !== this.size()) {
                        /* k指向较大的节点*/
                        k = item[k] < item[k + 1] ? k + 1 : k
                    }
                    if (temp >= item[k]) break
                    else item[i] = item[k]
                }
                item[i] = temp
                return maxItem
            }
            /**
             * @return 返回值
             */
            get = () => {
                return this.item[1]
            }
            /**
             * @return 返回堆中数的大小
             */
            size = () => {
                return this.item.length - 1
            }
            /**
             * @return {boolean} 返回堆是否为空 
             */
            isEmpty = () => {
                return this.item.length == 1 ? true : false
            }

        }

最小堆

思路与最大堆一样

JavaScript

class MinHeap {
            constructor() {
                this.item = []
                this.item[0] = -1000000007
            }

            push = (value) => {
                let item = this.item
                item.push(value)
                let k = this.size()
                while (value < item[Math.floor(k / 2)]) {
                    item[k] = item[Math.floor(k / 2)]
                    k = Math.floor(k / 2)
                }
                item[k] = value
            }

            pop = () => {
                if (this.isEmpty()) return Error('MinHeap has null')
                let item = this.item
                let k, i,minItem = item[1]
                let temp = item.pop()
                for (i = 1; i * 2 <= this.size(); i = k) {
                    k = i * 2
                    if (k !== this.size()) k = item[k] < item[k + 1] ? k : k + 1
                    if (temp <= item[k]) break
                    else item[i] = item[k]
                }
                item[i] = temp
                return minItem
            }

            get = () => {
                return this.item[1]
            }

            size = () => {
                return this.item.length - 1
            }

            isEmpty = () => {
                return this.size() === 0
            }
        }

自定义堆

class Heap {
    /**
     * 传入的最大最小值，如果是最小堆，传入-1000000007，最大值传入1000000007，
     * 如果是对象则传{value:-1000000007}
     * @param {number} key
    */
    constructor(key,func) {
        this.item = []
        this.item[0] = key?? -1000000007
        if (typeof func === 'function') this.compare = func
    }

    push = (value) => {
        let compare = this.compare
        let item = this.item
        item.push(value)
        let k = this.size()
        while (compare(value, item[Math.floor(k / 2)])<0) {
            item[k] = item[Math.floor(k / 2)]
            k = Math.floor(k / 2)
        }
        item[k] = value
    }

    pop = () => {
        
        if (this.isEmpty()) return Error('MinHeap has null')
        let item = this.item
        let k, i, minItem = item[1]
        let temp = item.pop()
        let compare = this.compare
        for (i = 1; i * 2 <= this.size(); i = k) {
            k = i * 2
            if (k !== this.size()) k = compare(item[k], item[k + 1]) <0 ? k : k + 1
            if (compare(temp, item[k]) <= 0) break
            else item[i] = item[k]
        }
        item[i] = temp
        return minItem
    }

    get = () => {
        return this.item[1]
    }

    size = () => {
        return this.item.length - 1
    }
    /**
     * 比较函数，如果是最小堆，返回a-b，如果是最大堆，返回b-a
    */
    compare = (a, b) => {
        return b-a
    }

    isEmpty = () => {
        return this.size() === 0
    }
}

使用举例

//最小堆
let heap = new Heap(-1000000007,(a,b)=>a-b)
        for(let i=10;i>0;i--){
            heap.push(i)
        }
        for(let i=0;i<10;i++){
            console.log(heap.pop())
        }
            console.log(1);

//最大堆
let heap = new Heap(1000000007,(a,b)=>a-b)
        for(let i=10;i>0;i--){
            heap.push(i)
        }
        for(let i=0;i<10;i++){
            console.log(heap.pop())
        }
            console.log(1);

Q.E.D.