【JavaScript】数据结构之堆

什么是堆？

• 堆都能用树来表示，一般树的实现都是利用链表。
• 而 二叉堆 是一种特殊的堆，它用完全二叉树来表示，却可以利用数组实现。平时使用最多的是二叉堆。
• 二叉堆易于存储，并且便于索引。
• 堆数据结构像树，但是，是通过数组来实现的（不是通过链表是通过二叉堆）。
• 最小堆就是从小到达排序，最大堆相反。

实现堆

• 因为是数组，所以父子节点的关系就不需要特殊的结构去维护，索引之间通过计算就可以得到，省掉了很多麻烦。如果是链表结构，就会复杂很多。
• 完全二叉树要求叶子节点从左往右填满，才能开始填充下一层，这就保证了不需要对数组整体进行大片的移动。这也是随机存储结构（数组）的短板，即删除一个元素之后，整体往前移是比较费时的。这个特性也导致堆在删除元素的时候，要把最后一个叶子节点补充到树根节点的缘由。
• 二叉堆像树的样子我可以理解，但将他们安排在数组里的话，通过当前下标怎么就能找到父节点和子节点呢？（父节点、左子树和右子树）
  • 左子树：index * 2 + 1
  • 右子树：index * 2 + 2
  • 父节点：（ index - 1 ）/ 2

实现最小堆

class MinHeap {
    constructor() {
        this.heap = []
    }
    // 换位置
    swap(i1, i2) {
        let temp = this.heap[i1]
        this.heap[i1] = this.heap[i2]
        this.heap[i2] = temp
    }
    // 找到父节点
    getParentIndex(index) {
        return Math.floor((index - 1) / 2)
    }
    // 上（前）移操作
    up(index) {
        if (index === 0) return
        const parentIndex = this.getParentIndex(index)
        if (this.heap[parentIndex] > this.heap[index] ) {
            this.swap( parentIndex, index )
            this.up(parentIndex)
        }
    }
    // 找到左侧子节点
    getLeftIndex(index) {
        return index * 2 + 1
    }
    // 找到右侧子节点
    getRigthIndex(index) {
        return index * 2 + 2
    }
    // 下（后）移操作
    down(index) {
        const leftIndex = this.getLeftIndex(index)
        const rightIndex = this.getRigthIndex(index)
        if (this.heap[leftIndex] < this.heap[index]) {
            this.swap(leftIndex, index)
            this.down(leftIndex)
        }
        if (this.heap[rightIndex] < this.heap[index]) {
            this.swap(rightIndex, index)
            this.down(rightIndex)
        }
    }
    // 添加元素
    insert( value ) {
        this.heap.push(value)
        this.up( this.heap.length-1 )
    }
    // 删除堆顶
    pop() {
        this.heap[0] = this.heap.pop()
        this.down(0)
    }
    // 获取堆顶
    peek() {
        return this.heap[0]
    }
    // 获取堆长度
    size() {
        return this.heap.length
    }
}

let arr = new MinHeap()
arr.insert(5)
arr.insert(4)
arr.insert(6)
arr.insert(1)
arr.pop()
console.log(arr)
console.log(arr.size())
console.log(arr.peek())

leetcode 习题

堆习题

原文地址：https://blog.csdn.net/weixin_43900414/article/details/142330506

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！