算法笔记 #005# 优先队列

留着备用。

“first-in largest-out”最大优先队列：

<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8">
        <title></title>
    </head>
    <body>        
        <script type="text/javascript">
            class PriorityQueue {
                constructor() {
                    this.A = [];
                    Heap.buildMaxHeap(this.A);                
                }
                
                isEmpty() {
                    return this.A.heapSize == 0;
                }
                
                insertWithPriority(x, priority) {
                    this.A.heapSize += 1;
                    this.A[this.A.heapSize] = {
                        x: x,
                        priority: -Infinity
                    };
                    Heap.increasePriority(this.A, this.A.heapSize, priority);
                }
                
                pullHighestPriorityElement() {
                    if (this.A.heapSize == 0) {
                        return null;
                    } else {
                        return Heap.extractMax(this.A).x;
                    }
                }
                
                peek() {
                    return this.A[1].x;
                }
            }
        </script>
        
        <script type="text/javascript">
            // 改进版本2，专门用来写优先队列。
            // 每个数组元素有两个属性：x和priority，后者决定位置，前者是实际存储的内容
            class Heap {
                // 把数组A转化为最大堆
                static buildMaxHeap(A) {
                    A.unshift(undefined); // 便于后续的下标计算
                    
                    A.heapSize = A.length - 1; // 实际多存了一个undefined
                    for (let i = Math.floor(A.heapSize / 2); i >= 1; --i) {
                        // 对所有非叶结点调用一次maxHeapify
                        // 之所以下标从后往前，是因为maxHeapify假定调用结点的左右子树都已经为最大堆
                        // 单个元素（叶结点）很自然地是一个最大堆
                        Heap.maxHeapify(A, i);
                    }
                }
                
                // 维护堆的性质
                static maxHeapify(A, i) {
                    let l = Heap.left(i);
                    let r = Heap.right(i);
                    
                    let largest = i;
                    // maxHeapify假定调用结点的左右子树都已经为最大堆
                    // 只是把调用结点i放到恰当的位置，以维护堆的性质
                    if (l <= A.heapSize && A[l].priority > A[i].priority) {
                        largest = l;
                    }
                    
                    if (r <= A.heapSize && A[r].priority > A[largest].priority) {
                        largest = r;
                    }
                    
                    if (largest != i) {
                        let temp = A[i];
                        A[i] = A[largest];
                        A[largest] = temp;
                        
                        Heap.maxHeapify(A, largest);
                    }
                }
                
                static left(i) {
                    return 2 * i;
                }
                
                static right(i) {
                    return 2 * i + 1;
                }
                
                static parent(i) {
                    return Math.floor(i / 2);
                }
                
                static extractMax(A) {
                    if (A.heapSize < 1) return null;
                    
                    let max = A[1];
                    A[1] = A[A.heapSize];
                    A.heapSize = A.heapSize - 1;
                    
                    Heap.maxHeapify(A, 1);
                    
                    return max;
                }
                
                static increasePriority(A, i, newPriority) {
                    if (newPriority < A[i].priority) {
                        return;
                    }
                    A[i].priority = newPriority;
                    while (i > 1 && A[Heap.parent(i)].priority < A[i].priority) {
                        let temp = A[i];
                        A[i] = A[Heap.parent(i)];
                        A[Heap.parent(i)] = temp;    
                        
                        i = Heap.parent(i);
                    }
                }
            }
        </script>

        <script type="text/javascript">
            let pQ = new PriorityQueue();
            console.log(pQ.isEmpty());
            pQ.insertWithPriority("employee", 15);
            console.log(pQ.isEmpty());
            pQ.insertWithPriority("boss", 25);
            console.log(pQ.peek());
            console.log(pQ.pullHighestPriorityElement());
            console.log(pQ.pullHighestPriorityElement());
            /**
             * output=
             * true
             * false
             * boss
             * boss
             * employee
             */
        </script>
    </body>
</html>

便于copy版最大优先队列：

class PriorityQueue {
    constructor() {
        this.A = [];
        Heap.buildMaxHeap(this.A);
    }

    isEmpty() {
        return this.A.heapSize == 0;
    }

    insertWithPriority(x, priority) {
        this.A.heapSize += 1;
        this.A[this.A.heapSize] = {
            x: x,
            priority: -Infinity
        };
        Heap.increasePriority(this.A, this.A.heapSize, priority);
    }

    pullHighestPriorityElement() {
        if(this.A.heapSize == 0) {
            return null;
        } else {
            return Heap.extractMax(this.A).x;
        }
    }

    peek() {
        return this.A[1].x;
    }
}

// 改进版本2，专门用来写优先队列。
// 每个数组元素有两个属性：x和priority，后者决定位置，前者是实际存储的内容
class Heap {
    // 把数组A转化为最大堆
    static buildMaxHeap(A) {
        A.unshift(undefined); // 便于后续的下标计算

        A.heapSize = A.length - 1; // 实际多存了一个undefined
        for(let i = Math.floor(A.heapSize / 2); i >= 1; --i) {
            // 对所有非叶结点调用一次maxHeapify
            // 之所以下标从后往前，是因为maxHeapify假定调用结点的左右子树都已经为最大堆
            // 单个元素（叶结点）很自然地是一个最大堆
            Heap.maxHeapify(A, i);
        }
    }

    // 维护堆的性质
    static maxHeapify(A, i) {
        let l = Heap.left(i);
        let r = Heap.right(i);

        let largest = i;
        // maxHeapify假定调用结点的左右子树都已经为最大堆
        // 只是把调用结点i放到恰当的位置，以维护堆的性质
        if(l <= A.heapSize && A[l].priority > A[i].priority) {
            largest = l;
        }

        if(r <= A.heapSize && A[r].priority > A[largest].priority) {
            largest = r;
        }

        if(largest != i) {
            let temp = A[i];
            A[i] = A[largest];
            A[largest] = temp;

            Heap.maxHeapify(A, largest);
        }
    }

    static left(i) {
        return 2 * i;
    }

    static right(i) {
        return 2 * i + 1;
    }

    static parent(i) {
        return Math.floor(i / 2);
    }

    static extractMax(A) {
        if(A.heapSize < 1) return null;

        let max = A[1];
        A[1] = A[A.heapSize];
        A.heapSize = A.heapSize - 1;

        Heap.maxHeapify(A, 1);

        return max;
    }

    static increasePriority(A, i, newPriority) {
        if(newPriority < A[i].priority) {
            return;
        }

        let temp = A[i]; // 待插入元素
        temp.priority = newPriority;
        while(i > 1 && A[Heap.parent(i)].priority < newPriority) {
            A[i] = A[Heap.parent(i)];
            i = Heap.parent(i);
        } // 寻找合适的插入位置
        A[i] = temp; // 插入元素
    }
}

View Code

最小优先队列（可以用在huffman编码中）：

// 最小优先队列
class PriorityQueue {
    constructor() {
        this.A = [];
        Heap.buildMinHeap(this.A);
    }

    isEmpty() {
        return this.A.heapSize == 0;
    }
    
    size() {
        return this.A.heapSize;
    }

    insertWithPriority(x, priority) {
        this.A.heapSize += 1;
        this.A[this.A.heapSize] = {
            x: x,
            priority: Infinity
        };
        Heap.decreasePriority(this.A, this.A.heapSize, priority);
    }

    pullLowestPriorityElement() {
        if(this.A.heapSize == 0) {
            return null;
        } else {
            return Heap.extractMin(this.A).x;
        }
    }

    peek() {
        return this.A[1].x;
    }
}

// 改进版本3，专门用来写最小优先队列。
// 每个数组元素有两个属性：x和priority，后者决定位置，前者是实际存储的内容
class Heap {
    // 把数组A转化为最小堆
    static buildMinHeap(A) {
        A.unshift(undefined); // 便于后续的下标计算

        A.heapSize = A.length - 1; // 实际多存了一个undefined
        for(let i = Math.floor(A.heapSize / 2); i >= 1; --i) {
            // 对所有非叶结点调用一次minHeapify
            // 之所以下标从后往前，是因为minHeapify假定调用结点的左右子树都已经为最小堆
            // 单个元素（叶结点）很自然地是一个最小
            Heap.minHeapify(A, i);
        }
    }

    // 维护堆的性质
    static minHeapify(A, i) {
        let l = Heap.left(i);
        let r = Heap.right(i);

        let smallest = i;
        // minHeapify假定调用结点的左右子树都已经为最小堆
        // 只是把调用结点i放到恰当的位置，以维护堆的性质
        if(l <= A.heapSize && A[l].priority < A[i].priority) {
            smallest = l;
        }

        if(r <= A.heapSize && A[r].priority < A[smallest].priority) {
            smallest = r;
        }

        if(smallest != i) {
            let temp = A[i];
            A[i] = A[smallest];
            A[smallest] = temp;

            Heap.minHeapify(A, smallest);
        }
    }

    static left(i) {
        return 2 * i;
    }

    static right(i) {
        return 2 * i + 1;
    }

    static parent(i) {
        return Math.floor(i / 2);
    }

    static extractMin(A) {
        if(A.heapSize < 1) return null;

        let min = A[1];
        A[1] = A[A.heapSize];
        A.heapSize = A.heapSize - 1;

        Heap.minHeapify(A, 1);

        return min;
    }

    static decreasePriority(A, i, newPriority) {
        if(newPriority > A[i].priority) {
            return;
        }

        let temp = A[i]; // 待插入元素
        temp.priority = newPriority;
        while(i > 1 && A[Heap.parent(i)].priority > newPriority) {
            A[i] = A[Heap.parent(i)];
            i = Heap.parent(i);
        } // 寻找合适的插入位置
        A[i] = temp; // 插入元素
    }
}

View Code