loserTree

[Mike-Zhu]

class LoserTree {
    constructor(branches) {
        this.branches = branches
        this.len = branches.length
        this.tree = Array(this.len)
        this.nodes = {}
        this.create()
    }
    merge() {
        var top
        let ret = null, cur = ret
        while ((top = this.get(this.tree[0])) !== null && !!top) {
            if (ret === null) {
                ret = {
                    val: top.val,
                    next: null
                }
                cur = ret
            } else {
                cur.next = {
                    val: top.val,
                    next: null
                }
                cur = cur.next
            }
            this.put(this.tree[0])
            this.adjust(this.tree[0])
        }
        return ret
    }
    create() {
        var size = this.len,
            winner = 0
        // 为叶子节点赋值
        for (var i = 0; i < size; i++) {
            this.nodes[i] = this.branches[i]
        }
        for (var i = 0; i < size; i++) {
            if (this.beat(i, winner)) {
                winner = i
            }
        }
        this.tree.fill(winner)
        // 从后向前依次调整非叶子节点
        for (var i = size - 1; i >= 0; i--)
            this.adjust(i);
    }
    adjust(index) {
        var size = this.len,
            t = this.except(size + index, 2)
        while (t > 0) {
            //新插入的index与树中的值相比较
            //比较parent，胜者继续比较，败者留在这里
            let isIndexLose = this.beat(this.tree[t], index)
            if (isIndexLose) {
                var temp = this.tree[t]
                this.tree[t] = index;
                index = temp
            }
            t = this.except(t, 2)
        }
        this.tree[0] = index
    }
    put(index) {
        let branch = this.nodes[index]
        this.nodes[index] = branch && branch.next ? branch.next : null
    }
    get(index) {
        return this.nodes[index]
    }
    beat(index1, index2) {
        var t1 = this.get(index1)
        var t2 = this.get(index2)
        if (t1 == null)
            return false;
        if (t2 == null)
            return true;
        // 这里, 当叶节点数据相等时比较分支索引是为了实现排序算法的稳定性
        let n = t1.val - t2.val
        if (n === 0) {
            return index1 < index2
        }//index1 < index2 为胜
        return n < 0
    }
    except(num, se) {
        return parseInt(num / se, 10)
    }
}

TEST

var node1 = new ListNode(1)
node1.next = new ListNode(4)
node1.next.next = new ListNode(5)

var node2 = new ListNode(1)
node2.next = new ListNode(3)
node2.next.next = new ListNode(4)

var node3 = new ListNode(2)
node3.next = new ListNode(6)
var temp1 = new LoserTree([node1, node2, node3])
function ListNode(val) {
    this.val = val;
    this.next = null;
}