UNPKG

7.75 kBPlain TextView Raw
1export abstract class Heap<T>{
2 private container: Array<T> = [];
3
4 public get Size(){
5 return this.container.length;
6 }
7
8 /**
9 * 获取左节点索引(2n+1)
10 * @param parent
11 */
12 private getLeftChildIndex(parent: number){
13 return (2 * parent) + 1;
14 }
15
16 /**
17 * 获取右节点索引(2n+2)
18 * @param parent
19 */
20 private getRigthChildIndex(parent: number){
21 return (2 * parent) + 2;
22 }
23
24 /**
25 * 获取父节点索引 当前索引值一半下取整
26 * @param index
27 */
28 private getParentIndex(index: number){
29 return Math.floor((index - 1) / 2);
30 }
31
32 /**
33 * 获取左节点
34 * @param parent
35 */
36 private getLeftChild(parent: number){
37 return this.container[this.getLeftChildIndex(parent)];
38 }
39
40 /**
41 * 获取右节点
42 * @param parent
43 */
44 private getRightChild(parent: number){
45 return this.container[this.getRigthChildIndex(parent)];
46 }
47
48 /**
49 * 获取父节点
50 * @param index
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 * @param customStartIndex 未指定位置默认从最末级开始
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 * @param customStartIndex 未指定位置默认从根级开始
91 */
92 private heapifyDown(customStartIndex?: number){
93 /**
94 * desc
95 * 1、取左右节点 比较大小 取索引
96 * 2、比较当前节点和第一步所取的索引,交换元素或跳出
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 // public getContainer(){
116 // return this.container;
117 // }
118
119 // NOTE:查看 binomialheap,leftist-tree
120 // public union(heap:Heap<T>){
121 // const mergeThreshold = 100;
122 // if(heap.Size - this.Size > mergeThreshold){
123 // const arr = this.container;
124 // const heapArr = heap.getContainer();
125 // for (let index = 0; index < heapArr.length; index++) {
126 // this.add(heapArr[index]);
127 // }
128 // for (let index = 0; index < arr.length; index++) {
129 // this.add(arr[index]);
130 // }
131 // }else{
132 // while(heap.Size){
133 // this.add(heap.poll());
134 // }
135 // }
136 // }
137
138 /**
139 * 弹出堆顶元素
140 * @returns T|null
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 * @param item
167 */
168 public add(item: T){
169 // 添加节点到末级,然后向上堆化
170 this.container.push(item);
171 this.heapifyUp();
172 return this;
173 }
174
175 /**
176 * 删除对应节点
177 * @param item
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 // tslint:disable-next-line:prefer-for-of
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 * @param arg T|T=>boolean
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}