JS实现一个优先队列

Posted on

PS: 文中图来源于网络，如有侵权请告知删除。

在复习数据结构和算法的时候，想找找有没有优先队列的实现，却发现找了几篇文章的优先队列都是一个队列然后给元素加个权值，出队的时候扫描一遍队列然后splice出来，感觉好像有那么一点不对。

优先队列的概念

优先队列虽然叫“队列”，但实际上它是一个堆，也就是特殊的完全二叉树。如下图：
优先队列

如果堆顶的数是最小的话，那么这就是一个最小堆，反之就是一个最大堆。

优先队列所含方法

跟堆的数据结构相仿：

1
2
3
4
5
6
queue.size() // 返回queue里元素个数
queue.empty() // 返回queue是否为空，空则返回true，否则返回false
queue.push(k) // 在queue的末尾插入k
queue.pop() // 删掉queue的第一个元素
queue.top() // 返回queue的第一个元素
queue.back() // 返回queue的末尾元素

如果我们需要插入一个新的结点的话，新结点会先加在最后一个新结点中，并依次和父结点进行比较，最小堆情况下，如果新结点比父结点小的话，就跟父结点换位置，以此类推，一直到不能再交换位置。

插入

实现结构

类似堆实现的话，基础结构一般就是数组或者链表，而我这里选择的是数组，主要原因有二：
1) 优先队列插入都是先插到最后的新结点位置，数组的话直接插到最后就行，不需要记录最后结点的位置。
2) 因为完全二叉树的结构，我们可以通过当前结点的索引来计算父结点的索引位置，如上上图表明的索引。

实现

下面实现一个最小堆优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
function PriorityQueue() {
    // 方便计算，将第一位置空
    this.list = [{}]
}

PriorityQueue.prototype.size = function () {
    return this.list.length - 1
}

PriorityQueue.prototype.empty = function () {
    return this.list.length === 1
}

PriorityQueue.prototype.push = function (data) {
    this.list.push(data)
    this._moveUp()
}

// 向上调整数
PriorityQueue.prototype._moveUp = function () {
    let newPos = this.list.length - 1
    let parent = Math.floor(newPos / 2)
    let isChange = true
    while (isChange) {
        isChange = false
      	//父子结点比较
        if (this.list[parent] > this.list[newPos]){
            let temp = this.list[parent]
            this.list[parent] = this.list[newPos]
            this.list[newPos] = temp
            isChange = true
            newPos = parent
            parent = Math.floor(newPos / 2)
        }
    }
}

// 向下调整
PriorityQueue.prototype._moveDown = function () {
    let newPos = 1
    let isChange = true
    while (isChange) {
        isChange = false
      	//父子结点比较
        let leftSonPos = newPos * 2
        let rightSonPos = newPos * 2 + 1
        let leftSonVal = this.list[leftSonPos]
        let rightSonVal = this.list[rightSonPos]
        
        if (typeof leftSonVal === 'undefined' && typeof rightSonVal)
          break
        
        let pos
        // 要注意有结点不存在的情况
		if (typeof leftSonVal !== 'undefined' && typeof rightSonVal === 'undefined') {
            pos = leftSonVal < this.list[newPos] ? leftSonPos : newPos
        
        } else if (typeof leftSonVal === 'undefined' && typeof rightSonVal !== 'undefined') {
            pos = rightSonVal < this.list[newPos] ? rightSonPos : newPos
        
        } else {
         	pos = leftSonVal < rightSonVal ? leftSonPos : rightSonPos
            pos = this.list[newPos] < this.list[pos] ? newPos : pos  
        }
      
        if (pos === newPos) break
        let temp = this.list[pos]
        this.list[pos] = this.list[newPos]
        this.list[newPos] = temp
        isChange = true
        newPos = pos
    }
}

PriorityQueue.prototype.pop = function () {
  	let res = this.top()
    this.list[1] = this.list[this.list.length - 1]
    this.list.splice(this.list.length - 1,1)
    this._moveDown()
    return res
}

PriorityQueue.prototype.top = function () {
    return this.list[1]
}

PriorityQueue.prototype.back = function () {
    return this.list[this.list.length - 1]
}

let queue = new PriorityQueue()
queue.push(2)
queue.push(7)
queue.push(3)
queue.push(15)
queue.push(1)

console.log(!queue.empty()) // true
console.log(queue.size() === 5) // true
console.log(queue.top() === 1) // true
console.log(queue.pop()) // 1
console.log(queue.top() === 2) // true

测试通过，主要留意第一位留空，是因为我们是通过除以二的操作来计算父结点位置的，所以按索引1为起始索引更好计算。

优先队列相关练习题

leetcode 703:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。

示例:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8
说明: 
你可以假设 nums 的长度≥ k-1 且k ≥ 1。

解答(使用上面定义的优先队列)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
    this.k = k
    this.queue = new PriorityQueue('min')
    for (let i = 0; i < nums.length ; i++) {
        if (this.queue.size() < k) {
            this.queue.push(nums[i])
        } else {
            if (this.queue.top() < nums[i]) {
                this.queue.pop()
                this.queue.push(nums[i])
            }
        }
    }
    
    return this
};

/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
    let queue = this.queue
    if (queue.size() < this.k) {
        queue.push(val)
    } else {
        if (queue.top() < val) {
            queue.pop()
            queue.push(val)
        }
    }
    
    return queue.top()
};

因为只需要返回第K大的元素，所以我们只需要维护一个size为k的最小堆，那么堆顶的元素就是第k大的元素。比k小的数都不插入堆，比k大的数就先pop出堆顶元素，再插入到优先队列中。