实现几种数据结构

链表

class ListNode {
    val: number
    next: ListNode | null

    constructor(val: number = 0, next: ListNode | null = null) {
        this.val = val
        this.next = next
    }
}

二叉树

class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null

    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val
        this.left = left
        this.right = right
    }
}

优先队列（堆）

class Heap<T = number> {
    private store: T[]
    private compareFn: (pre: T, cur: T) => boolean

    constructor(store: T[] = [], compareFn: (pre: T, cur: T) => boolean = (pre, cur) => pre < cur) {
        store.unshift(null)
        this.store = store
        this.compareFn = compareFn
        this.build()
    }

    get size() {
        return this.store.length - 1
    }

    offer(val: T) {
        this.store.push(val)
        this.adjustUp(this.size)
    }

    poll(): T {
        const temp = this.store[1]

        if (!this.isEmpty()) {
            this.swap(1, this.size)
            this.store.pop()
            this.adjustDown(1)
        }

        return temp
    }

    peek(): T {
        return this.store[1]
    }

    clear() {
        this.store.splice(1, this.size)
    }

    isEmpty(): boolean {
        return this.size === 0
    }

    private judge(a: number, b: number, dir: 'up' | 'down'): boolean {
        if (dir === 'up') {
            return this.compareFn(this.store[a], this.store[b])
        } else if (dir === 'down') {
            return !this.compareFn(this.store[a], this.store[b])
        } else {
            let nv: never
            return nv
        }
    }

    private swap(a: number, b: number) {
        const temp = this.store[a]

        this.store[a] = this.store[b]
        this.store[b] = temp
    }

    private adjustUp(idx: number) {
        while (idx > 1) {
            const parent = Math.floor(idx / 2)
            if (this.judge(idx, parent, 'up')) {
                this.swap(idx, parent)
            }
            idx = parent
        }
    }

    private adjustDown(idx: number, maxIdx: number = this.size) {
        while (idx <= maxIdx) {
            const left = idx * 2, right = idx * 2 + 1
            let cur = idx
            if (left <= maxIdx && this.judge(cur, left, 'down')) {
                cur = left
            }
            if (right <= maxIdx && this.judge(cur, right, 'down')) {
                cur = right
            }
            if (cur === idx) {
                break
            }
            this.swap(idx, cur)
            idx = cur
        }
    }

    private build() {
        for (let i = Math.floor(this.size / 2); i >= 1; i--) {
            this.adjustDown(i)
        }
    }
}