首页文章资源工具教程 栏目
数据结构与算法插入排序（Insertion Sort）冒泡排序（Bubble Sort）选择排序（Selection Sort）快速排序（Quick Sort）希尔排序（Shell Sort）归并排序（Merge Sort）堆排序（Heap Sort）计数排序（Counting Sort）桶排序（Bucket Sort）基数排序（Radix Sort）栈(Stack)队列(Queue)链表( Linked List)集合(Set)哈希表/散列表（Hash Table）树（ Tree）_二叉树堆（Heap）字典树(Trie)图（Graph）

在线工具_工作生活好帮手

打造各种简单、易用、便捷的在线工具，网友无需注册和下载安装即可使用

点击查看

堆（Heap）

什么是堆？

堆（英语：Heap）是计算机科学中的一种特别的树状数据结构。若是满足以下特性，即可称为堆：“给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于（或大于等于）C的值”。

若母节点的值恒小于等于子节点的值，此堆称为最小堆（MinHeap）；

反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（MaxHeap）。

在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。



为什么需要堆？

堆可以使我们在O(1)的时间复杂度，获取堆中的最大值或者最小值。而数组或者链表则需要O(n)的时间复杂度。如果是二叉数则需要O(log n)的时间复杂度。


如何实现堆？

虽然堆是一种树状的结构，但是可以将堆转换为数组。


我们仔细观察一下上图。最大最小的元素放在index= 0索引的位置，使我们可以在O(1)的时间复杂度内拿到它。root节点的子节点的索引分别是1, 2。而索引等于 1 的节点，它的子节点的索引则是 3, 4。

总结一下堆中父节点，和子节点的索引关系如下：


当然我们也可以通过子节点的索引，反推出父节点的索引 父节点索引 = Math.floor(子节点索引 / 2)

MinHeap

class MinHeap {
    constructor () {
        this.heap = []
    }

    getMin () {
        // 最小值是堆栈的顶
        return this.heap[0]
    }
}

insert


  1. insert(10), heap为空, 10会作为根节点
  2. insert(23), 23 > 10, 23可以作为10的子节点
  3. insert(36), 36 > 10, 36可以作为10的子节点
  4. insert(18), 因为 18 < 23，18不能作为23的子节点。所以18和23需要调换位置。接着我们继续向上查找，18 > 10，所以18可以是10的子节点，迭代结束。

insert方法的具体实现

class MinHeap {
    //  ....

    getParentNode (index) {
        return this.heap[Math.floor(index / 2)]
    } 

    insert (node) {
        this.heap.push(node)
        if (this.heap.length > 1) {
            let currentIndex = this.heap.length - 1
            // 需要依次向上查找
            while (
                currentIndex > 1 &&
                this.getParentNode(currentIndex) > this.heap[currentIndex]
            ) {
                // 最小堆，如果父节点大于子节点，父节点和子节点需要互相交换
                // 父节点的索引
                const parentIndex = Math.floor(currentIndex / 2)
                let temp = this.heap[parentIndex]
                this.heap[parentIndex] = this.heap[currentIndex]
                this.heap[currentIndex] = temp
                currentIndex = parentIndex
            }
        }
    }
}

remove


最小堆中删除节点，删除根节点后，将堆中的最后一位移动到根节点上。然后依次比较根节点和子节点的大小，如果根节点大于子节点，子节点和根节点调换位置。直到全部比较完成。


class MinHeap {
    // ...

    remove () {
        let min = this.getMin()

        if (this.heap.length > 2) {
            this.heap[1] = this.heap[this.heap.length - 1]
            this.heap.splice(this.heap.length - 1)

            // 如果只有两个节点的情况下，直接比较两个节点即可, 不需要依次比较所以的子节点
            if (this.heap.length === 3) {
                if (this.heap[1] > this.heap[2]) {
                    let temp = this.heap[1]
                    this.heap[1] = this.heap[2]
                    this.heap[2] = temp
                }
                return min
            }

            let currentIndex = 1
            // 首位是null，所以不加1
            let leftChildIndex = currentIndex * 2
            let rightChildIndex = currentIndex * 2 + 1

            // 如果有大于2个节点，父节点需要比较左右两个子节点
            while (
                this.heap[leftChildIndex] &&
                this.heap[rightChildIndex] &&
                (this.heap[currentIndex] > this.heap[leftChildIndex] || this.heap[currentIndex] > this.heap[rightChildIndex])
            ) {
                if (this.heap[leftChildIndex] < this.heap[rightChildIndex]) {
                    let temp = this.heap[currentIndex]
                    this.heap[currentIndex] = this.heap[leftChildIndex] 
                    this.heap[leftChildIndex] = temp
                    currentIndex = leftChildIndex
                } else {
                    let temp = this.heap[currentIndex]
                    this.heap[currentIndex] = this.heap[rightChildIndex]
                    this.heap[rightChildIndex] = temp
                    currentIndex = rightChildIndex
                }

                leftChildIndex = currentIndex * 2
                rightChildIndex = currentIndex * 2 + 1
            }
        } else if (this.heap.length === 2) {
            // 当前只有一个节点的情况下，直接删除root节点
            this.heap.splice(1, 1)
        } else {
            return null
        }

        return min
    }
}

MinHeap 完整的实现


class MinHeap {
    constructor () {
        this.heap = [null]
    }

    getMin () {
        return this.heap[1]
    }

    getParentNode (index) {
        return this.heap[Math.floor(index / 2)]
    } 

    insert (node) {
        this.heap.push(node)
        if (this.heap.length > 1) {
            let currentIndex = this.heap.length - 1
            // 需要依次向上查找
            while (
                currentIndex > 1 &&
                this.getParentNode(currentIndex) > this.heap[currentIndex]
            ) {
                // 最小堆，如果父节点大于子节点，父节点和子节点需要互相交换
                // 父节点的索引
                const parentIndex = Math.floor(currentIndex / 2)
                let temp = this.heap[parentIndex]
                this.heap[parentIndex] = this.heap[currentIndex]
                this.heap[currentIndex] = temp
                currentIndex = parentIndex
            }
        }
    }

    remove () {
        let min = this.getMin()

        if (this.heap.length > 2) {
            this.heap[1] = this.heap[this.heap.length - 1]
            this.heap.splice(this.heap.length - 1)

            // 如果只有两个节点的情况下，直接比较两个节点即可, 不需要依次比较所以的子节点
            if (this.heap.length === 3) {
                if (this.heap[1] > this.heap[2]) {
                    let temp = this.heap[1]
                    this.heap[1] = this.heap[2]
                    this.heap[2] = temp
                }
                return min
            }

            let currentIndex = 1
            // 首位是null，所以不加1
            let leftChildIndex = currentIndex * 2
            let rightChildIndex = currentIndex * 2 + 1

            // 如果有大于2个节点，父节点需要比较左右两个子节点
            while (
                this.heap[leftChildIndex] &&
                this.heap[rightChildIndex] &&
                (this.heap[currentIndex] > this.heap[leftChildIndex] || this.heap[currentIndex] > this.heap[rightChildIndex])
            ) {
                if (this.heap[leftChildIndex] < this.heap[rightChildIndex]) {
                    let temp = this.heap[currentIndex]
                    this.heap[currentIndex] = this.heap[leftChildIndex] 
                    this.heap[leftChildIndex] = temp
                    currentIndex = leftChildIndex
                } else {
                    let temp = this.heap[currentIndex]
                    this.heap[currentIndex] = this.heap[rightChildIndex]
                    this.heap[rightChildIndex] = temp
                    currentIndex = rightChildIndex
                }

                leftChildIndex = currentIndex * 2
                rightChildIndex = currentIndex * 2 + 1
            }
        } else if (this.heap.length === 2) {
            // 当前只有一个节点的情况下，直接删除root节点
            this.heap.splice(1, 1)
        } else {
            return null
        }

        return min
    }
}


实际应用: 数组中的第K个最大元素

题目

在未排序(不能进行排序)的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

解答


/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    if (nums.length == 0) {
        return -1
    }
    
    if (nums.length < k) {
        return -1
    }
    
    const heap = new MinHeap()
    let result = null
    
    for (let i = 0; i < nums.length; i++) {
        heap.insert(nums[i])
    }
    
    // 题目是第几大 可以转换为对应的第几小
    // 如果直接使用最大堆也可以
    k = nums.length - k + 1
    
    while (k > 0) {
        result = heap.remove()
        k -= 1
    }
    
    return result
};

链接: https://www.fly63.com/course/28_1310

字典树(Trie) >>