| 1 | import { MaxHeap } from "../MaxHeap";
|
| 2 | import { MinHeap } from "../MinHeap";
|
| 3 |
|
| 4 | describe("MaxHeap test", () => {
|
| 5 | test("should create an empty max heap", () => {
|
| 6 | const maxHeap = new MaxHeap<number>();
|
| 7 | expect(maxHeap).toBeDefined();
|
| 8 | expect(maxHeap.peek()).toBeNull();
|
| 9 | expect(maxHeap.isEmpty()).toBe(true);
|
| 10 | });
|
| 11 |
|
| 12 | test("should add items to the heap and heapify it up", () => {
|
| 13 | const maxHeap = new MaxHeap<number>();
|
| 14 | maxHeap.add(10);
|
| 15 | expect(maxHeap).toBeDefined();
|
| 16 | expect(maxHeap.isEmpty()).toBe(false);
|
| 17 | expect(maxHeap.peek()).toBe(10);
|
| 18 | expect(maxHeap.toString()).toBe("10");
|
| 19 |
|
| 20 | maxHeap.add(5);
|
| 21 | expect(maxHeap.peek()).toBe(10);
|
| 22 | expect(maxHeap.toString()).toBe("10,5");
|
| 23 |
|
| 24 | maxHeap.add(12);
|
| 25 | expect(maxHeap.peek()).toBe(12);
|
| 26 | expect(maxHeap.toString()).toBe("12,5,10");
|
| 27 |
|
| 28 | maxHeap.add(3);
|
| 29 | expect(maxHeap.peek()).toBe(12);
|
| 30 | expect(maxHeap.toString()).toBe("12,5,10,3");
|
| 31 |
|
| 32 | maxHeap.add(7);
|
| 33 | expect(maxHeap.peek()).toBe(12);
|
| 34 | expect(maxHeap.toString()).toBe("12,7,10,3,5");
|
| 35 |
|
| 36 | expect(maxHeap.poll()).toBe(12);
|
| 37 | expect(maxHeap.toString()).toBe("10,7,5,3");
|
| 38 |
|
| 39 | expect(maxHeap.poll()).toBe(10);
|
| 40 | expect(maxHeap.toString()).toBe("7,3,5");
|
| 41 |
|
| 42 | expect(maxHeap.poll()).toBe(7);
|
| 43 | expect(maxHeap.toString()).toBe("5,3");
|
| 44 |
|
| 45 | expect(maxHeap.poll()).toBe(5);
|
| 46 | expect(maxHeap.toString()).toBe("3");
|
| 47 |
|
| 48 | expect(maxHeap.poll()).toBe(3);
|
| 49 | expect(maxHeap.isEmpty()).toBe(true);
|
| 50 | });
|
| 51 |
|
| 52 | test("should find items in heap", () => {
|
| 53 | const maxHeap = new MaxHeap<number>();
|
| 54 | maxHeap.add(5);
|
| 55 | maxHeap.add(12);
|
| 56 | maxHeap.add(7);
|
| 57 | expect(maxHeap.find(item => item === 5)).not.toBeNull();
|
| 58 | expect(maxHeap.find(5)).not.toBeNull();
|
| 59 | expect(maxHeap.findAll(item => item === 5)).toEqual([5]);
|
| 60 | expect(maxHeap.findAll(5)).toEqual([5]);
|
| 61 | });
|
| 62 |
|
| 63 | test("should poll empty to heap", () => {
|
| 64 | const maxHeap = new MaxHeap<number>();
|
| 65 | maxHeap.add(5);
|
| 66 | expect(maxHeap.poll()).toBe(5);
|
| 67 | expect(maxHeap.poll()).toBeNull();
|
| 68 | });
|
| 69 |
|
| 70 | test("should entries to heap", () => {
|
| 71 | const maxHeap = new MaxHeap<number>();
|
| 72 | maxHeap.add(5);
|
| 73 | maxHeap.add(7);
|
| 74 | expect(maxHeap.entries()).toEqual([7, 5]);
|
| 75 | });
|
| 76 | });
|
| 77 |
|
| 78 | describe("MinHeap test", () => {
|
| 79 | test("should create an empty max heap", () => {
|
| 80 | const minHeap = new MinHeap<number>();
|
| 81 | expect(minHeap).toBeDefined();
|
| 82 | expect(minHeap.peek()).toBeNull();
|
| 83 | expect(minHeap.isEmpty()).toBe(true);
|
| 84 | });
|
| 85 |
|
| 86 | test("should add items to the heap and heapify it up", () => {
|
| 87 | const minHeap = new MinHeap<number>();
|
| 88 | minHeap.add(10);
|
| 89 | expect(minHeap.isEmpty()).toBe(false);
|
| 90 | expect(minHeap.peek()).toBe(10);
|
| 91 |
|
| 92 | minHeap.add(5);
|
| 93 | expect(minHeap.peek()).toBe(5);
|
| 94 | expect(minHeap.toString()).toBe("5,10");
|
| 95 |
|
| 96 | minHeap.add(7);
|
| 97 | expect(minHeap.peek()).toBe(5);
|
| 98 | expect(minHeap.toString()).toBe("5,10,7");
|
| 99 |
|
| 100 | minHeap.add(8);
|
| 101 | expect(minHeap.peek()).toBe(5);
|
| 102 | expect(minHeap.toString()).toBe("5,8,7,10");
|
| 103 |
|
| 104 | minHeap.add(3);
|
| 105 | expect(minHeap.peek()).toBe(3);
|
| 106 | expect(minHeap.toString()).toBe("3,5,7,10,8");
|
| 107 |
|
| 108 | expect(minHeap.poll()).toBe(3);
|
| 109 | expect(minHeap.toString()).toBe("5,8,7,10");
|
| 110 |
|
| 111 | expect(minHeap.poll()).toBe(5);
|
| 112 | expect(minHeap.toString()).toBe("7,8,10");
|
| 113 |
|
| 114 | expect(minHeap.poll()).toBe(7);
|
| 115 | expect(minHeap.toString()).toBe("8,10");
|
| 116 |
|
| 117 | expect(minHeap.poll()).toBe(8);
|
| 118 | expect(minHeap.toString()).toBe("10");
|
| 119 |
|
| 120 | expect(minHeap.poll()).toBe(10);
|
| 121 | expect(minHeap.toString()).toBe("");
|
| 122 | expect(minHeap.isEmpty()).toBe(true);
|
| 123 | });
|
| 124 |
|
| 125 | test("MinHeap delete test", () => {
|
| 126 | const minHeap = new MinHeap<number>();
|
| 127 | minHeap.add(5);
|
| 128 | minHeap.add(15);
|
| 129 | minHeap.remove(5);
|
| 130 | expect(minHeap.find(5)).toBeNull();
|
| 131 | minHeap.add(5);
|
| 132 | minHeap.add(7);
|
| 133 | minHeap.remove(5);
|
| 134 | expect(minHeap.find(5)).toBeNull();
|
| 135 | minHeap.add(12);
|
| 136 | minHeap.add(6);
|
| 137 | minHeap.remove(6);
|
| 138 | minHeap.remove(item => item === 12);
|
| 139 | minHeap.remove(15);
|
| 140 | minHeap.remove(7);
|
| 141 | expect(minHeap.find(15)).toBeNull();
|
| 142 | expect(minHeap.Size).toBe(0);
|
| 143 |
|
| 144 | minHeap.add(6);
|
| 145 | minHeap.add(8);
|
| 146 | minHeap.add(10);
|
| 147 | minHeap.add(14);
|
| 148 | minHeap.add(5);
|
| 149 | minHeap.add(7);
|
| 150 |
|
| 151 | minHeap.remove(6);
|
| 152 | minHeap.remove(10);
|
| 153 | minHeap.remove(5);
|
| 154 | minHeap.remove(14);
|
| 155 | minHeap.remove(8);
|
| 156 | minHeap.remove(7);
|
| 157 |
|
| 158 | expect(minHeap.Size).toBe(0);
|
| 159 | });
|
| 160 |
|
| 161 | test("MinHeap empty test", () => {
|
| 162 | const minHeap = new MinHeap<number>();
|
| 163 | minHeap.add(5);
|
| 164 | minHeap.add(15);
|
| 165 | minHeap.clear();
|
| 166 | expect(minHeap.Size).toBe(0);
|
| 167 | });
|
| 168 | });
|
| 169 |
|
| 170 | describe("Heap Gen test", () => {
|
| 171 | test("MaxHeap Gen test", () => {
|
| 172 | const maxHeap = new MaxHeap<{value: number}>("value");
|
| 173 | maxHeap.add({value: 10});
|
| 174 | expect(maxHeap).toBeDefined();
|
| 175 | expect(maxHeap.isEmpty()).toBe(false);
|
| 176 | expect(maxHeap.peek()).toEqual({value: 10});
|
| 177 |
|
| 178 | maxHeap.add({value: 5});
|
| 179 | expect(maxHeap.peek()).toEqual({value: 10});
|
| 180 |
|
| 181 | maxHeap.add({value: 12});
|
| 182 | expect(maxHeap.peek()).toEqual({value: 12});
|
| 183 |
|
| 184 | maxHeap.add({value: 3});
|
| 185 | expect(maxHeap.peek()).toEqual({value: 12});
|
| 186 |
|
| 187 | maxHeap.add({value: 7});
|
| 188 | expect(maxHeap.peek()).toEqual({value: 12});
|
| 189 |
|
| 190 | expect(maxHeap.poll()).toEqual({value: 12});
|
| 191 | expect(maxHeap.poll()).toEqual({value: 10});
|
| 192 | expect(maxHeap.poll()).toEqual({value: 7});
|
| 193 | expect(maxHeap.poll()).toEqual({value: 5});
|
| 194 | expect(maxHeap.poll()).toEqual({value: 3});
|
| 195 |
|
| 196 | expect(maxHeap.isEmpty()).toBe(true);
|
| 197 | });
|
| 198 |
|
| 199 | test("MinHeap Gen test", () => {
|
| 200 | const minHeap = new MinHeap<{value: number}>("value");
|
| 201 | minHeap.add({value: 10});
|
| 202 | expect(minHeap.isEmpty()).toBe(false);
|
| 203 | expect(minHeap.peek()).toEqual({value: 10});
|
| 204 |
|
| 205 | minHeap.add({value: 5});
|
| 206 | expect(minHeap.peek()).toEqual({value: 5});
|
| 207 |
|
| 208 | minHeap.add({value: 7});
|
| 209 | expect(minHeap.peek()).toEqual({value: 5});
|
| 210 |
|
| 211 | minHeap.add({value: 8});
|
| 212 | expect(minHeap.peek()).toEqual({value: 5});
|
| 213 |
|
| 214 | minHeap.add({value: 3});
|
| 215 | expect(minHeap.peek()).toEqual({value: 3});
|
| 216 |
|
| 217 | expect(minHeap.poll()).toEqual({value: 3});
|
| 218 | expect(minHeap.poll()).toEqual({value: 5});
|
| 219 | expect(minHeap.poll()).toEqual({value: 7});
|
| 220 | expect(minHeap.poll()).toEqual({value: 8});
|
| 221 | expect(minHeap.poll()).toEqual({value: 10});
|
| 222 |
|
| 223 | expect(minHeap.isEmpty()).toBe(true);
|
| 224 | });
|
| 225 | });
|