关于javascript:最小堆

4次阅读

共计 1596 个字符，预计需要花费 4 分钟才能阅读完成。

<!DOCTYPE html>
<html>
<head>
    <meta charset="UTF-8">
    <title> 最小堆类 </title>
</head>
<body>
    <p> 最小堆类 </p>
    <script src="./index.js"></script>
</body>
</html>

class MinHeap{constructor() {this.heap = []
    }
    // 获取堆
    getHeap() {return this.heap}
    // 获取元素父元素下标
    getParentIndex(i) {return (i - 1) >> 1
    }
    // 获取元素左孩子下标
    getLeftIndex(index) {return index * 2 + 1}
    // 获取元素的右孩子下标
    getRightIndex(index) {return index * 2 + 2}
    // 替换值
    swap(i1, i2) {const temp = this.heap[i1]
        this.heap[i1] = this.heap[i2]
        this.heap[i2] = temp
    }
    // 向上调整
    shiftUp(index) {
        // 元素下标为 0，进行调整
        if (index === 0) return
        // 获取父元素下标
        const parentIndex = this.getParentIndex(index)
        // 如果以后元素比父元素小，替换值
        if (this.heap[parentIndex] > this.heap[index]) {this.swap(index, parentIndex)
            // 递归
            this.shiftUp(parentIndex)
        }
    }
    // 向下调整
    shiftDown(index) {
        // 获取左右孩子下标
        const left = this.getLeftIndex(index)
        const right = this.getRightIndex(index)
        // 如果左孩子比以后节点小，替换值
        if (this.heap[index] > this.heap[left]) {this.swap(index, left)
            // 递归
            this.shiftDown(left)
        }
        // 如果右孩子比以后节点小，替换值
        if (this.heap[index] > this.heap[right]) {this.swap(index, right)
            // 递归
            this.shiftDown(right)
        }
    }
    // 向堆中插入元素
    insert(n) {this.heap.push(n)
        // 从堆尾元素开始向上调整堆，使其成为最小堆
        this.shiftUp(this.heap.length - 1)
    }
    // 删除堆顶
    pop() {
        // 将堆顶元素与堆尾元素替换
        this.swap(0, this.heap.length - 1)
        // 保留堆顶元素，作为函数返回值
        const value = this.heap.pop()
        // 从堆顶元素开始向下调整堆，使其成为最小堆
        this.shiftDown(0)
        // 返回删除的堆顶元素
        return value
    }
}

const h = new MinHeap()
h.insert(9)
h.insert(6)
h.insert(7)
h.insert(4)
h.insert(3)
h.insert(5)
h.insert(2)
h.insert(8)
h.insert(1)
console.log('heap', h.getHeap())
console.log('pop', h.pop())
console.log('heap', h.getHeap())
console.log('pop', h.pop())
console.log('heap', h.getHeap())
console.log('pop', h.pop())
console.log('heap', h.getHeap())
console.log('pop', h.pop())
console.log('heap', h.getHeap())

正文完