-
Notifications
You must be signed in to change notification settings - Fork 0
/
PriorityQueue.ts
121 lines (118 loc) · 3.12 KB
/
PriorityQueue.ts
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
// deno-lint-ignore no-explicit-any
export interface PriorityQueue<T = any> {
clear: () => void;
length: () => number;
comparator: (a: T, b: T) => number;
offer: (value: T) => void;
head: () => T | undefined;
tail: () => T | undefined;
pop: () => T | undefined;
shift: () => T | undefined;
// at: (index: number) => T | undefined;
}
/**
* Your KthLargest object will be instantiated and called as such:
* var obj = new KthLargest(k, nums)
* var param_1 = obj.add(val)
*/
// deno-lint-ignore no-explicit-any
export function PriorityQueue<T = any>(
comparator: (a: T, b: T) => number,
): PriorityQueue<T> {
//默认升序
//comparator Function used to determine the order of the elements. It is expected to return a negative value if the head argument is less than the second argument, zero if they're equal, and a positive value otherwise.
const data: T[] = [];
function length(): number {
return data.length;
}
function swap(i1: number, i2: number) {
[data[i1], data[i2]] = [data[i2], data[i1]];
}
function bubble_head_to_tail() {
if (data.length < 2) {
return;
}
for (let i = 0, j = 1; j < data.length && i < data.length; i++, j++) {
if (comparator(data[i], data[j]) > 0) {
swap(i, j);
} else {
break;
}
}
}
function bubble_tail_to_head() {
if (data.length < 2) {
return;
}
for (
let i = data.length - 2, j = data.length - 1;
j >= 0 && i >= 0;
i--, j--
) {
if (comparator(data[i], data[j]) > 0) {
swap(i, j);
} else {
break;
}
}
}
function offer(value: T) {
const f = head();
if (typeof f === "undefined") {
data.push(value);
return;
}
const l = tail();
if (typeof l === "undefined") {
data.push(value);
return;
}
if (comparator(value, l) > 0) {
data.push(value);
} else if (comparator(value, f) < 0) {
data.unshift(value);
} else {
if (comparator(value, data[Math.floor(data.length / 2)]) > 0) {
data.push(value);
bubble_tail_to_head();
} else {
data.unshift(value);
bubble_head_to_tail();
}
}
}
function head() {
if (!data.length) {
return undefined;
}
return data[0];
}
function tail() {
if (!data.length) {
return undefined;
}
return data[data.length - 1];
}
function pop() {
return data.pop();
}
function shift() {
return data.shift();
}
function clear() {
data.length = 0;
}
//function at(index: number): T | undefined {
// return data.at(index);
// }
return {
clear,
length,
comparator,
offer,
head,
tail,
pop,
shift, /*, at*/
};
}