优先队列(Priority Queue)

简单介绍下优先队列,它不记录入队顺序,而是当前最大/最小的元素优先出队。我们可以用最大/最小堆来实现优先队列,每一次入队操作就是堆的插入操作,每一次出队操作就是删除堆顶节点。这篇文章以Heapify的源码为例,简要介绍其实现。

优先队列的表示

我们用数组来表示二叉堆,并将根节点的索引置为 1。Heapify 中使用使用两个独立的类型数组(默认使用 Uint32Array )表示二叉堆。

heap-representations.png

在堆中,位置k的节点的父节点在位置k / 2;相反,位于位置k的节点的两个子节点位于位置2k2k +1。我们可以通过对数组索引执行简单的计算来上下移动。

    constructor(capacity = 64, keys = [], priorities = [],
        KeysBackingArrayType = Uint32Array,
        PrioritiesBackingArrayType = Uint32Array) {

        this.capacity = capacity;
        this._keys = new KeysBackingArrayType(capacity + ROOT_INDEX); // ROOT_INDEX = 1;
        this._priorities = new PrioritiesBackingArrayType(capacity + ROOT_INDEX);
        if (keys.length !== priorities.length) {
            throw new Error("Number of keys does not match number of priorities provided.");
        }
        if (capacity < keys.length) {
            throw new Error("Capacity less than number of provided keys.");
        }
        // copy data from user
        for (let i = 0; i < keys.length; i++) {
            this._keys[i + ROOT_INDEX] = keys[i];
            this._priorities[i + ROOT_INDEX] = priorities[i];
        }
        this.length = keys.length;
        for (let i = keys.length >>> 1; i >= ROOT_INDEX; i--) {
            this.bubbleDown(i);
        }
    }

插入或删除元素

插入或删除后都后需要重新调整堆的结构。插入时我们直接放在最后然后递归向上浮动到合适位置;删除时顶部空缺,我们先将最后一个节点换到顶部,然后将其下沉到合适位置。浮动的时间复杂度为O(log n)

上浮

  bubbleUp(index) {
        const key = this._keys[index];
        const priority = this._priorities[index];

        while (index > ROOT_INDEX) {
            const parentIndex = index >>> 1;   // 父元素索引
            if (this._priorities[parentIndex] <= priority) {
                break;  // 如果父元素优先级更小,则满足了堆的性质
            }
            // 否则将父元素沉下来
            this._keys[index] = this._keys[parentIndex];
            this._priorities[index] = this._priorities[parentIndex];

            index = parentIndex; // 重复下一级
        }

        // 至此找到了插入元素要放置的位置
        this._keys[index] = key;
        this._priorities[index] = priority;
    }

下沉

bubbleDown(index) {
        const key = this._keys[index];
        const priority = this._priorities[index];

        const halfLength = ROOT_INDEX + (this.length >>> 1);  // no need to check the last level
        const lastIndex = this.length + ROOT_INDEX;
        while (index < halfLength) {
            const left = index << 1;
            if (left >= lastIndex) {
                break;  // 到最后一个节点,无法继续下沉
            }

            // 选择左孩子
            let childPriority = this._priorities[left];
            let childKey = this._keys[left];
            let childIndex = left;

            // 如有右孩子,选择优先级最小的
            const right = left + 1;
            if (right < lastIndex) {
                const rightPriority = this._priorities[right];
                if (rightPriority < childPriority) {
                    childPriority = rightPriority;
                    childKey = this._keys[right];
                    childIndex = right;
                }
            }

            if (childPriority >= priority) {
                break;  // 如果孩子优先级更小,则满足了堆的性质
            }

            // 否则将子元素浮上去
            this._keys[index] = childKey;
            this._priorities[index] = childPriority;

            index = childIndex;
        }

        // 至此找到了插入元素要放置的位置
        this._keys[index] = key;
        this._priorities[index] = priority;
    }

在最后实现了下面三个生成器函数,让我们可以方便的获取优先队列中的值和优先级。

   * [Symbol.iterator]() {
        for (let i = 0; i < this.length; i++) {
            const priority = this._priorities[i + ROOT_INDEX];
            const key = this._keys[i + ROOT_INDEX];
            yield [key, priority];
        }
    }

    * keys() {
        for (let i = 0; i < this.length; i++) {
            yield this._keys[i + ROOT_INDEX];
        }
    }

    * priorities() {
        for (let i = 0; i < this.length; i++) {
            yield this._priorities[i + ROOT_INDEX];
        }
    }

参考文章

https://github.com/luciopaiva/heapify/blob/master/heapify.mjs
https://algs4.cs.princeton.edu/24pq/

一种使用倒排索引和位图的快速SKU选择方法

使用所有有货的SKU组合生成该SKU到该组合的索引。如 [A-B,B-C] 即生成 {A:[1],B:[1,2],C:[2]}
映射到视图时只需要判断当前选中项的SKU索引的交集(默认为全集),例如选中B,则[1,2,3][1,2]的交集[1,2],然后依次遍历SKU,判断SKU对应的索引与当前选中索引是否有交集。如果有则可选,没有则置灰。

索引可以使用位图数据结构,在判断是否为交集使用位运算提升性能。

   const sku = [];
    const revertIndex = {};
    const size = 8;
    // 随机sku
    for (let i = 0; i < size; i++) {
        sku[i] = new Set();
        for (let j = 0; j < size; j++) {
            const v = j * size + RandomNumBoth(0, size);
            sku[i].add(v)
        }
    }

    for (let i = 0; i < sku.length; i++) {
        sku[i].forEach((e) => {
            if (!revertIndex[e]) revertIndex[e] = 0;
            revertIndex[e] |= 1 << i
        })
    }

判断是否选中使用 (revertIndex[(line-1)*size + e -1] & union)

下面是一个简单的例子,取消选择和选中逻辑是一样的,所以就暂时没写:

See the Pen SKU Demo by zhangchen (@zhangchen915) on CodePen.

JS 实现位图(Bitset)数据结构

位图数组中每个元素在内存中占用1位,所以可以节省存储空间,在索引,数据压缩等方面有广泛应用。
我们使用类型化数组Uint8Array储存位图,数组中每一个元素占8个字节所以最大值是255。关键是寻找偏移量,index>>3 右移三位相当于除8。可以找到对应的数组元素,1 << (index % 8) 找到位对应数组元素的哪一个字节。最后通过按位判断该为1或0。

判断存在时:使用按位与&(只有两个操作数相应的比特位都是1时,结果才为1)
修改某项:使用按位或|

Typescript代码如下:

export class Bitmap {
    private bin: Uint8Array;

    constructor(size: number) {
        this.bin = new Uint8Array(new ArrayBuffer((size >> 3) + 1));
    }

    public get(index: number): boolean {
        const row = index >> 3;
        const bit = 1 << (index % 8);
        return (this.bin[row] & bit) > 0;
    }

    public set(index: number, bool: boolean = true) {
        const row = index >> 3;
        const bit = 1 << (index % 8);
        if (bool) {
            this.bin[row] |= bit;
        } else {
            this.bin[row] &= (255 ^ bit);
        }
    };

    public fill(num: number = 0) {
        this.bin.fill(num);
    }

    public flip(index: number) {
        const row = Math.floor(index / 8);
        const bit = 1 << (index % 8);
        this.bin[row] ^= bit;
    }
}

红黑树

红黑树在C++的STL中很广泛,例如map和set都是用红黑树实现的,此外还大量应用在Linux系统中。所以有必要深入了解下。

定义

红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树的基础上增加了以下要求:

  • 节点是红色或黑色。
  • 根是黑色。
  • 所有叶子都是黑色(叶子是NIL节点)。
  • 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

插入

先把结点标记为红色,再按二叉查找树的方法插入,最后再根据红黑树的要求进行调整。
所以我们根据插入后被破坏的红黑树性质进行分情况讨论。

  1. 被插入节点是根结点直接涂黑
  2. 被插入节点的父根结点为黑色,那么插入后的新树仍然是一棵红黑树
  3. 被插入的节点的父节点是红色,那么我们调整的最终目标是将这两个红色层层上移动,最终通过旋转将其中一个红色移动到最顶端,然后将其涂黑(注意不节点移动,只是颜色自下而上传递)

Case 1 当前节点的父节点是红色,且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色。
(01) 将“父节点”设为黑色。
(02) 将“叔叔节点”设为黑色。
(03) 将“祖父节点”设为“红色”。
(04) 将“祖父节点”设为“当前节点”(红色节点);即,之后继续对“当前节点”进行操作。

Case 2 当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的右孩子
(01) 将“父节点”作为“新的当前节点”。
(02) 以“新的当前节点”为支点进行左旋。

Case 3 当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的左孩子
(01) 将“父节点”设为“黑色”。
(02) 将“祖父节点”设为“红色”。
(03) 以“祖父节点”为支点进行右旋。

为何将插入节点置为红色?
选黑色不是不可以,调整嘛,最终总是能符合定义。首先我们插入操作对之前的红黑树造成的破坏只可能有2.4.5,当我们选择红色的时候永远不会违反性质5,所以置为红色比黑色要简单。

与AVL树比较

  1. 如果插入引起了树的不平衡,AVL和红黑树都是最多只需要2次旋转操作,即两者都是O(1);但是在删除引起树的不平衡时,最坏情况下,AVL需要维护从被删节点到根这条路径上所有节点的平衡性,因此需要旋转的量级O(logN),而红黑最多只需3次旋转,只需要O(1)的复杂度。
  2. AVL的结构相较RB-Tree来说更为平衡,所以在插入和删除node更容易造成不平衡,因此在大量数据需要插入或者删除时红黑树效率更高。

二叉搜索树

特点

  1. 左子树的节点 < 根节点 < 右子树节点
  2. 没有重复节点

查找

    search(key, node = this.roots) {
        if (node) {
            if (key < node.key) {
                return this.search(node.left, key);
            } else if (key > node.key) {
                return this.search(node.right, key);
            } else {
                return true;
            }
        } else {
            return false;
        }
    }

插入和删除

插入很简单,就是在树的最底层寻找一个合适的位置。

   insert(key) {
        let newNode = {
            key: key,
            left: null,
            right: null
        };
        if (!this.roots) {
            this.roots = newNode;
        } else {
            this.insertNode(this.roots, newNode);  // 从根节点开始
        }
        return this;  // 链式操作
    };

    insertNode(node, newNode) {
        if (newNode.key < node.key) {
            if (!node.left) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else if(newNode.key > node.key){
            if (!node.right) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }else{
            return false;  //不能有键值相等的节点
        }
    }

删除比较复杂,要根据子节点情况分三类进行操作:
1.如果没有子节点直接删除
2.如果有一个子节点那么将孩子提升到被删除元素的位置
3.如果有两个子节点则需要用被删除节点的右子树中最小节点替换,如下图所示:

屏幕快照 2017-05-11 下午6.06.00.png

    remove(key, node = this.roots) {
        if (node === null) {
            return false;
        }

        if (key < node.key) {
            node.left = this.remove(key, node.left);
            return node;
        } else if (key > node.key) {
            node.right = this.remove(key, node.right);
            return node;
        } else {
            //如果没有子节点直接删除
            //如果有一个子节点那么将孩子提升到被删除元素的位置
            if (node.left === null && node.right === null) {
                node = null;
                return node;
            } else if (node.left === null) {
                node = node.right;
                return node;
            } else if (node.right === null) {
                node = node.left;
                return node;
            } else {
                //如果有两个子节点
                console.log(node)
                let aux = this.findMinNode(node.right);  //在右子树中向左到尽头找到最小节点
                node.key = aux.key;
                node.right = this.remove(aux.key, node.right);
                return node;
            }
        }
    }

    findMinNode(node) {
        while (node && node.left) {
            node = node.left;
        }
        return node;
    }

复杂度

搜索、插入、删除的复杂度等于树高。
同样一棵二叉搜索树,全部由插入生成的和经过插入和删除的两棵树就不一样。树高的期望为 {O(log n)},最坏 {O(n)}

正因为这种随机性,特别是当插入有序的节点时,树就会退化成线性表,所以我们还会对二叉搜索树进行优化,让其拥有最好的最坏复杂度。你听说过的红黑树、AVL树就是解决这一问题而出现的,下篇文章我们会介绍。