树堆

[RubyLouvre]

class Node {
    constructor(data, priority) {
        this.priority = priority
        this.data = data;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
};

class Treap {
    constructor() {
        this.root = null;
        this._size = 0;
    }
    size() {
        return this._size;
    }
    transplant(child, parent) {
        if (!parent) {
            this.root = child;
        } else {
            if (parent.data > child.data) {
                parent.left = child
            } else {
                parent.right = child
            }
        }
        if (child) {
            child.parent = parent;
        }
    }
    leftRotate(node) {
        if (!node.right) {
            return;
        }
        var child = node.right;
        node.right = child.left;
        if (child.left) {
            //过继孩子
            child.left.parent = node; //父属性修正1
        }
        this.transplant(child, node.parent) //父属性修正2
        node.parent = child; //父属性修正3
        child.left = node; //旋转
    }
    rightRotate(node) {
        if (!node.left) {
            return;
        }
        var child = node.left;
        node.left = child.right;
        if (child.right) {
            //过继孩子
            child.right.parent = node; //父属性修正1
        }
        this.transplant(child, node.parent) //父属性修正2
        node.parent = child; //父属性修正3
        child.right = node; //旋转
    }

    find(data) {
        var node = this.root;
        while (node) {
            var diff = data - node.data
            if (diff == 0) {
                break
            } else if (diff < 0) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        if (node) {
            return node
        }
        return null
    }
    insert(data) {
        var priority = ~~Math.random().toString().slice(-4)
        if (!this.root) {
            this.root = new Node(data, priority)
            this._size = 1
        } else {
            var node = this.root,
                parent = null;
            while (node) {
                parent = node;
                var diff = data - node.data
                if (diff == 0) {
                    return
                } else if (diff < 0) {
                    node = node.left

                } else {
                    node = node.right
                }
            }
            var node = new Node(data, priority)
            this._size++;
            node.parent = parent;
            if (diff < 0) {
                parent.left = node
            } else {
                parent.right = node;
            }
            this.rebalance(node)
        }
        return true
    }
    rebalance(node) {
        var parent = node.parent
        //我们要构建最小堆，因此父节点的优化级不能大于当前节点的优化级
        do {
            if (node.priority < parent.priority) {
                if (parent.left == node) {
                    this.rightRotate(parent); //让左孩子上浮
                } else {
                    this.leftRotate(parent); //让右孩子上浮
                }
            } else {
                node = parent; //node可能没有上浮，parent不会变, 更换node
            }
            parent = node.parent;
        } while (parent)

    }
    remove(data) {
        var node = this.find(data);
        if (node) {
            this._size--;
            while (node.left && node.right) {
                if (node.left.priority < node.right.priority) {
                    this.rightRotate(node)
                } else {
                    this.leftRotate(node)
                }
            }
            var parent = node.parent;
            var child = node.left || node.right || null;
            if (!parent) {
                this.root = child;
            } else {
                if (parent.left == node) {
                    parent.left = child
                } else {
                    parent.right = child
                }
            }
            if (child) {
                child.parent = parent; //parent的size发生变化
            }
        }
    }

    maxNode(node) {
        var current = node || this.root;
        while (current.right) {
            current = node.right
        }
        return current;
    }
    toString(printNode) {
        if (printNode === void 0) printNode = function (n) {
            return n.priority + ":" + n.data
        };
        var out = [];
        printRow(this.root, '', true, function (v) {
            return out.push(v);
        }, printNode);
        return out.join('');
    };
}

function printRow(root, prefix, isTail, out, printNode) {
    if (root) {
        out(("" + prefix + (isTail ? '└── ' : '├── ') + (printNode(root)) + "\n"));
        var indent = prefix + (isTail ? '    ' : '│   ');
        if (root.left) {
            printRow(root.left, indent, false, out, printNode);
        }
        if (root.right) {
            printRow(root.right, indent, true, out, printNode);
        }
    }
}
var tree = new Treap(); // 30, 20, 60, 55, 54, 53, 52, 51, 56
[10, 50, 40, 30, 20, 60, 55, 54, 53, 52, 51, 56].forEach(function (el) {
    tree.insert(el)
    console.log(tree + "")
})
console.log("delete...")
tree.remove(60)
console.log(tree + "")

console.log(tree)

[RubyLouvre]

有旋Treap

 class Node {
    constructor(data) {
      this.data = data;
      this.right = null;
      this.left = null;
      this.fix = ~~(Math.random() + "").slice(2, 7);
      this.size = 1;
      this.count = 1;
    }
    maintain() {
      var leftSize = this.left ? this.left.size : 0;
      var rightSize = this.right ? this.right.size : 0;
      this.size = leftSize + rightSize + this.count;
    }
  }
  class Treap {
      find(value) {
        var node = this.root;
        while (node) {
          var diff = value - node.data;
          if (value === 0) {
            return node
          } else if (value > 0) {
            node = node.right;
          } else {
            node = node.left;
          }
        }
        return null;
      }
      insert(value) {
        this.root = this._insert(this.root, value)
        getOrder(this)
      }
      _insert(node, value) {
        if (!node) {
          return new Node(value)
        }
        if (node.data == value) {
          node.count++;
          node.maintain()
          return node;
        } else if (node.data > value) {
          node.left = this._insert(node.left, value);
          if (node.left.fix < node.fix) {
            node = this.rotateRight(node)
          }
        } else {
          node.right = this._insert(node.right, value);
          if (node.right.fix < node.fix) {
            node = this.rotateLeft(node)
          }
        }
        node.maintain()
        return node;
      }
      rotateLeft(node) {
        var top = node.right; //会上浮的子节点
        // top.size = node.size;//外面会处理，这里就不重复
        node.right = top.left;//过继
        node.maintain()//维护size
        top.left = node;//旋转
        return top;
      }

      rotateRight(node) {
        var top = node.left;//会上浮的子节点
        // top.size = node.size;
        node.left = top.right;//过继
        node.maintain();//维护size
        top.right = node;//旋转
        return top;
      }

      inOrder(cb) {
        function recursion(node) {
          if (node) {
            recursion(node.left)
            cb(node)
            recursion(node.right)
          }
        }
        recursion(this.root)
      }
      preOrder(cb) {
        function recursion(node) {
          if (node) {
            cb(node)
            recursion(node.left)
            recursion(node.right)
          }
        }
        recursion(this.root)
      }
      postOrder(cb) {
        function recursion(node) {
          if (node) {
            recursion(node.left)
            recursion(node.right)
            cb(node)
          }
        }
        recursion(this.root)
      }
      getSize(node) {
        return node ? node.size : 0
      }
      getKth(k) {
        var node = this.root
        while (node) {
          if (k <= this.getSize(node.left)) {
            node = node.left
          } else if (k > this.getSize(node.left) + node.count) {
            k -= (this.getSize(node.left) + node.count)
            node = node.right
          } else {
            return node.data
          }
        }
        return null
      }
      getRank(value) {
        return this.getRankInner(this.root, value)
      }

      getRankInner(node, value) {
        if (!node) {
          return 0;
        } else if (node.data == value) {
          return this.getSize(node.left) + 1
        } else if (node.data > value) {
          return this.getRankInner(node.left, value);
        } else {
          return this.getRankInner(node.right, value) + this.getSize(node.left) + node.count
        }
      }

      remove(value) {
        var parents = [], node = this.root;
        while (node) {
          var diff = value - node.data;
          if (diff === 0) {
            break
          }
          parents.push(node)
          if (diff > 0) {
            node = node.right;
          } else {
            node = node.left;
          }
        }
        if (node) { //找到要删除的节点
          console.log("找到要删除的节点", node)
          if (node.count > 1) {
            node.count--
          } else {
            var parent = parents[parents.length - 1], newParent
            while (node.left && node.right) {
              var dir = Object(parent).left == node ? 'left' : 'right'
              if (node.left.fix < node.right.fix) {
                //left上位
                newParent = this.rotateRight(node)
                console.log('右旋', newParent.data)
              } else {
                newParent = this.rotateLeft(node)
                console.log('左旋', newParent.data)
                //right上位
              }
              if (!parent) {
                this.root = newParent
              } else {
                parent[dir] = newParent;
              }
              parent = newParent;
              parents.push(parent)
            }

            var dir = Object(parent).left == node ? 'left' : 'right'
            parent[dir] = node.left || node.right || null
          }
          console.log("找到要维护的父节点", parents.map(function (el) {
            return el.data
          }))
          while (parents.length) {
            var a = parents.pop()
            a.maintain()
          }
          return true
        }
        return false
      }
    }
    var array = [7, 11, 13, 8, 44, 78, 15, 9, 77, 1, 2]  //[11,7,14,3,9,18,16,15]
    var t = new Treap(2);
    array.forEach(function (el) {
      t.insert(el)
    })
    function getOrder(t) {
      var array = []
      t.inOrder(function (node) {
        array.push(node.data)
      })
      console.log(array + "")
    }
    var a = t.getRank(44)
    console.log('t.getRank(44)', a);
    var b = t.getKth(a)
    console.log(`t.getKth(${a})`, b);

    t.remove(11)
    t.remove(3)
    console.log("移除11,3后")
    t.insert(23)

[RubyLouvre]

无旋Treap

  class Node {
        constructor(value) {
            this.left = null
            this.right = null;
            this.size = 1;
            this.data = value;
            this.fix = ~~(Math.random() + "").slice(2, 5)
        }
        maintain() {
            var dummy = {
                size: 0
            }
            var left = this.left || dummy
            var right = this.right || dummy
            //  left.parent = this
            // right.parent = this
            this.size = left.size + right.size + 1
        }
    }
    function Pair(a, b) {
        this.first = a;
        this.second = b;
    }
    class Treap {
        constructor(mode) {

        }

        split(node, value) {
            if (!node) {
                return new Pair(null, null)
            }
            var p; //pair
            if (node.data <= value) {
                p = this.split(node.right, value)
                node.right = p.first;
                p.first = node;
            } else {
                p = this.split(node.left, value)
                node.left = p.second;
                p.second = node;
            }
            node.maintain();
            return p;
        }

        insert(value) {
            var p = this.split(this.root, value);
            var node = new Node(value)
            this.root = this.merge(p.first, this.merge(node, p.second));
            getOrder(t)
        }

        remove(value) {
            var p1 = this.split(this.root, value);//分为x树为<=待删除，y树大于 
            //value包含在p1.first中
            var p2 = this.split(p1.first, value - 1);
            //value孤零零地在p2.second中
            this.root = this.merge(p2.first, p1.second)
        }

        getValueBySize(node, k) {
            while (node) {
                var lsize = this.getSize(node.left);
                if (lsize + 1 === k) {
                    return node.data
                } else if (lsize + 1 > k) {
                    node = node.left
                } else {
                    k -= (lsize + 1)
                    node = node.right
                }
            }
            return 0;
            if (!node) {
                return 0
            }
            while (this.getSize(node.left) + 1 != k) {
                if (this.getSize(node.left) >= k)
                    node = node.left
                else {
                    k -= (this.getSize(node.left) + 1)
                    node = node.right
                }
                if (!node) {
                    return 0
                }
            }
            return node.data
        }
        getRank(value) {//从1数起
            var p = this.split(this.root, value - 1);
            var ans = this.getSize(p.first) + 1
            this.root = this.merge(p.first, p.second);
            return ans
        }
        getKth(k) {
            return this.getValueBySize(this.root, k)
        }
        getSize(node) {
            return node ? node.size : 0
        }
        merge(a, b) { //此时a树所有节点的值都应少于b中所有节点的值
            if (!a || !b) {//如果有一个为空，那么返回不为空的
                return a || b;
            }
            if (a.fix < b.fix) {//要满足堆的性质
                a.right = this.merge(a.right, b);
                a.maintain();//维护它的节点大小
                return a;
            } else {
                b.left = this.merge(a, b.left);
                b.maintain();//维护它的节点大小
                return b;
            }
        }
        getPrev(val) {
            var p = this.split(this.root, val - 1);
            var ans = this.getValueBySize(p.first, this.getSize(p.first));
            this.root = this.merge(p.first, p.second);
            return ans;
        }
        getSucc(val) {
            var p = this.split(this.root, val);
            var ans = this.getValueBySize(p.second, 1);
            this.root = this.merge(p.first, p.second);
            return ans;
        }
        getMin() {
            return this.getValueBySize(this.root, 1)
        }
        getMax() {
            return this.getValueBySize(this.root, this.getSize(this.root))
        }
        inOrder(cb) {
            function recursion(node) {
                if (node) {
                    recursion(node.left)
                    cb(node)
                    recursion(node.right)
                }
            }
            recursion(this.root)
        }
        preOrder(cb) {
            function recursion(node) {
                if (node) {
                    cb(node)
                    recursion(node.left)
                    recursion(node.right)
                }
            }
            recursion(this.root)
        }

    }

    var array = [7, 11, 13, 8, 44, 78, 15, 9, 77, 1, 2]  //[11,7,14,3,9,18,16,15]
    var t = new Treap(2);
    array.forEach(function (el) {
        t.insert(el)
    })
    function getOrder(t) {
        var array = []
        t.inOrder(function (node) {
            array.push(node.data)
        })
        console.log(array + "")
    }
    var a = t.getRank(44)
    console.log('t.getRank(44)', a);
    var b = t.getKth(a)
    console.log(`t.getKth(${a})`, b);
    console.log(`t.getPrev(44)`, t.getPrev(44))
    console.log(`t.getSucc(44)`, t.getSucc(44))
    console.log('t.getMin()', t.getMin())
    console.log('t.getMax()', t.getMax())
    t.remove(11)
    t.remove(3)
    t.insert(23)