1 | export abstract class Heap<T>{
|
2 | private container: Array<T> = [];
|
3 |
|
4 | public get Size(){
|
5 | return this.container.length;
|
6 | }
|
7 |
|
8 | |
9 |
|
10 |
|
11 |
|
12 | private getLeftChildIndex(parent: number){
|
13 | return (2 * parent) + 1;
|
14 | }
|
15 |
|
16 | |
17 |
|
18 |
|
19 |
|
20 | private getRigthChildIndex(parent: number){
|
21 | return (2 * parent) + 2;
|
22 | }
|
23 |
|
24 | |
25 |
|
26 |
|
27 |
|
28 | private getParentIndex(index: number){
|
29 | return Math.floor((index - 1) / 2);
|
30 | }
|
31 |
|
32 | |
33 |
|
34 |
|
35 |
|
36 | private getLeftChild(parent: number){
|
37 | return this.container[this.getLeftChildIndex(parent)];
|
38 | }
|
39 |
|
40 | |
41 |
|
42 |
|
43 |
|
44 | private getRightChild(parent: number){
|
45 | return this.container[this.getRigthChildIndex(parent)];
|
46 | }
|
47 |
|
48 | |
49 |
|
50 |
|
51 |
|
52 | private getParent(index: number){
|
53 | return this.container[this.getParentIndex(index)];
|
54 | }
|
55 |
|
56 | private hasLeftChild(parent: number){
|
57 | return this.getLeftChildIndex(parent) < this.container.length;
|
58 | }
|
59 |
|
60 | private hasRightChild(parent: number){
|
61 | return this.getRigthChildIndex(parent) < this.container.length;
|
62 | }
|
63 |
|
64 | private hasParent(index: number){
|
65 | return this.getParentIndex(index) >= 0;
|
66 | }
|
67 |
|
68 | private swap(indexOne: number, indexTwo: number){
|
69 | const temp = this.container[indexTwo];
|
70 | this.container[indexTwo] = this.container[indexOne];
|
71 | this.container[indexOne] = temp;
|
72 | }
|
73 |
|
74 | |
75 |
|
76 |
|
77 |
|
78 | private heapifyUp(customStartIndex?: number){
|
79 |
|
80 | let currentIndex = customStartIndex || this.container.length - 1;
|
81 | while (this.hasParent(currentIndex) && !this.compare(this.getParent(currentIndex),
|
82 | this.container[currentIndex])){
|
83 | this.swap(currentIndex, this.getParentIndex(currentIndex));
|
84 | currentIndex = this.getParentIndex(currentIndex);
|
85 | }
|
86 | }
|
87 |
|
88 | |
89 |
|
90 |
|
91 |
|
92 | private heapifyDown(customStartIndex?: number){
|
93 | |
94 |
|
95 |
|
96 |
|
97 |
|
98 | let currentIndex = customStartIndex || 0;
|
99 | let nextIndex: number = null;
|
100 | while (this.hasLeftChild(currentIndex)){
|
101 | if (this.hasRightChild(currentIndex)
|
102 | && this.compare(this.getRightChild(currentIndex), this.getLeftChild(currentIndex))){
|
103 | nextIndex = this.getRigthChildIndex(currentIndex);
|
104 | }else{
|
105 | nextIndex = this.getLeftChildIndex(currentIndex);
|
106 | }
|
107 | if (this.compare(this.container[currentIndex], this.container[nextIndex])){
|
108 | break;
|
109 | }
|
110 | this.swap(currentIndex, nextIndex);
|
111 | currentIndex = nextIndex;
|
112 | }
|
113 | }
|
114 |
|
115 |
|
116 |
|
117 |
|
118 |
|
119 |
|
120 |
|
121 |
|
122 |
|
123 |
|
124 |
|
125 |
|
126 |
|
127 |
|
128 |
|
129 |
|
130 |
|
131 |
|
132 |
|
133 |
|
134 |
|
135 |
|
136 |
|
137 |
|
138 | |
139 |
|
140 |
|
141 |
|
142 | public poll(){
|
143 | if (this.container.length === 0){
|
144 | return null;
|
145 | }
|
146 | if (this.container.length === 1){
|
147 | return this.container.pop();
|
148 | }
|
149 | const item = this.container[0];
|
150 |
|
151 | this.container[0] = this.container.pop();
|
152 | this.heapifyDown();
|
153 | return item;
|
154 | }
|
155 |
|
156 | public peek() {
|
157 | if (this.container.length === 0) {
|
158 | return null;
|
159 | }
|
160 |
|
161 | return this.container[0];
|
162 | }
|
163 |
|
164 | |
165 |
|
166 |
|
167 |
|
168 | public add(item: T){
|
169 |
|
170 | this.container.push(item);
|
171 | this.heapifyUp();
|
172 | return this;
|
173 | }
|
174 |
|
175 | |
176 |
|
177 |
|
178 |
|
179 | public remove(item: ((item: T) => boolean)|T) {
|
180 | // 查找所有要删除的节点,用于迭代
|
181 | const numberOfItemsToRemove = this.findAll(item).length;
|
182 |
|
183 | for (let iteration = 0; iteration < numberOfItemsToRemove; iteration += 1) {
|
184 | // 每次查找要删除节点的索引,因为每删除一个值,表中的索引都会发生变化
|
185 | const indexToRemove = this.findAllIndex(item).pop();
|
186 | // 最后一个节点,直接弹出
|
187 | if (indexToRemove === (this.container.length - 1)) {
|
188 | this.container.pop();
|
189 | } else {
|
190 | this.container[indexToRemove] = this.container.pop();
|
191 |
|
192 | const parentItem = this.getParent(indexToRemove);
|
193 |
|
194 | // 存在子节点并且(是根节点或者满足父级和子级关系) 向下堆化
|
195 | // 否则向上堆化
|
196 | if (this.hasLeftChild(indexToRemove) &&
|
197 | (!parentItem || this.compare(parentItem, this.container[indexToRemove]))){
|
198 | this.heapifyDown(indexToRemove);
|
199 | } else {
|
200 | this.heapifyUp(indexToRemove);
|
201 | }
|
202 | }
|
203 | }
|
204 |
|
205 | return numberOfItemsToRemove > 0;
|
206 | }
|
207 |
|
208 | public toString() {
|
209 | return this.container.toString();
|
210 | }
|
211 |
|
212 | public isEmpty(){
|
213 | return !this.container.length;
|
214 | }
|
215 |
|
216 | /**
|
217 | * 查找符合条件的节点
|
218 | * @param arg T|T=>boolean
|
219 | */
|
220 | public find(arg: any){
|
221 | let temp: T = null;
|
222 |
|
223 | for (let index = 0; index < this.container.length; index++) {
|
224 | const element = this.container[index];
|
225 | const match = typeof arg === "function" ? arg(element) : arg === element;
|
226 | if (match){
|
227 | temp = element;
|
228 | break;
|
229 | }
|
230 | }
|
231 | return temp;
|
232 | }
|
233 |
|
234 | |
235 |
|
236 |
|
237 |
|
238 | public findAll(arg: any){
|
239 | const temp: Array<T> = [];
|
240 | this.container.forEach(item => {
|
241 | const match = typeof arg === "function" ? arg(item) : arg === item;
|
242 | if (match){
|
243 | temp.push(item);
|
244 | }
|
245 | });
|
246 | return temp;
|
247 | }
|
248 |
|
249 | public clear(){
|
250 | this.container.length = 0;
|
251 | }
|
252 |
|
253 | public entries(){
|
254 | return [...this.container];
|
255 | }
|
256 |
|
257 | private findAllIndex(arg: any){
|
258 | const temp: Array<number> = [];
|
259 | this.container.forEach((item, index) => {
|
260 | const match = typeof arg === "function" ? arg(item) : arg === item;
|
261 | if (match){
|
262 | temp.push(index);
|
263 | }
|
264 | });
|
265 | return temp;
|
266 | }
|
267 |
|
268 | protected abstract compare(a: any, b: any): boolean;
|
269 | }
|