#85 优先队列


  • 0
    administrators

    优先队列是一种元素带权重的队列,你可以往队列中添加和删除元素,但是删除元素的时候会把优先级最高的元素删除。例如:

    const pq = new PriorityQueue()
    pq.add(1)
    pq.add(2)
    pq.add(3)
    
    pq.remove() // => 3
    pq.remove() // => 2
    pq.remove() // => 1
    

    remove 方法每次删除的时候都会把最大的元素删除掉,并且返回被删除元素。请你完成 PriorityQueue 的实现。

    服务器运行时间限制:20ms。


  • 0

    class PriorityQueue {
      constructor() {
        this.queue = []
        this.isSorted = false
      }
      add (e) {
        this.isSorted = false
        this.queue.push(e)
      }
      
      remove () {
        if (!this.isSorted) {
          this.queue.sort((a,b) => a - b)
          this.isSorted = true
        }
        return this.queue.pop()
      }
    }
    

    终于通过了


  • 0

    class PriorityQueue {
      constructor(){
        this.arr = [];
      }
      add (num) {
        /* TODO */
        this.arr.push(num);
      }
      
      remove () {
        /* TODO */
        var num = Math.max(...this.arr);
         this.arr.splice(this.arr.indexOf(num),1);
        return num;
      }
    }
    

  • 0

    class PriorityQueue {
    constructor () {
    this._maxHeap = [];
    }

    add(item) {
    	this._maxHeap.push(item);
    	this.shiftUp();
    }
    
    remove() {
    	this.swapItem(0, this._maxHeap.length - 1);
    	let ans = this._maxHeap.pop();
    	this.shiftDown();
    	return ans;
    }
    
    shiftUp() {
    	let son = this._maxHeap.length - 1;
    	while (son != 0) {
    		let parent = Math.floor((son - 1) / 2);
    		if (this._maxHeap[son] > this._maxHeap[parent]) {
    			this.swapItem(son, parent);
    			son = parent;
    		} else {
    			break;
    		}
    	}
    }
    
    //每次和儿子中最大值交换
    shiftDown() {
    	let parent = 0;
    	let leftSon = 1;
    	let rightSon = 2;
    	let maxItemIndex;
    	while (leftSon < this._maxHeap.length) {
    		if (rightSon < this._maxHeap.length) {
    			maxItemIndex =  this._maxHeap[leftSon] 
                                                           >= this._maxHeap[rightSon] 
                                                           ? leftSon 
                                                           : rightSon;
    		} else {
    			maxItemIndex = leftSon;
    		}
    		if (this._maxHeap[parent] < this._maxHeap[maxItemIndex]) {
    			this.swapItem(parent, maxItemIndex);
    			parent = maxItemIndex;
    			leftSon = 2 * parent + 1;
    			rightSon = 2 * parent + 2;
    		} else {
    			break;
    		}
    	}
    }
    
    swapItem(a, b) {
    	[this._maxHeap[a], this._maxHeap[b]] = [this._maxHeap[b], this._maxHeap[a]];
    }
    

    }


  • 0

    @终天霸主 这样如果remove和add间隔执行就不行吧


  • 0

    class PriorityQueue {
      constructor () {
        this.queue = []
      }
      add (e) {
        const len = this.queue.length
        if (len === 0) return this.queue.push(e)
        if (len === 1) return this.queue[e > this.queue[0] ? 'unshift' : 'push'](e)
        let v = Math.floor(len/2)
        if (e > this.queue[v]) {
            for (let i = 0; i <= v; i++) {
                if (e >= this.queue[i]) {
                    this.queue.splice(i, 0, e)
                    break
                }
            }
        } else {
            for (let i = len; i >= v; i--) {
                if (e <= this.queue[i]) {
                    this.queue.splice(i + 1, 0, e)
                    break
                }
            }
        }
    }
      remove () {
        return this.queue.shift()
      }
    }

  • 0

    可以维护一个有序数组。每次add的时候使用二分查找,remove的时候就pop()。复杂度为logN,比每次都找max的复杂度(N)要低。


登录后回复
 

与 ScriptOJ 的连接断开,我们正在尝试重连,请耐心等待