2023-09-09 15:49:53 +00:00
|
|
|
<!DOCTYPE html>
|
2023-09-26 04:49:33 +00:00
|
|
|
<html lang='en'>
|
2023-09-09 15:49:53 +00:00
|
|
|
<head>
|
2023-09-26 04:49:33 +00:00
|
|
|
<meta charset='UTF-8'>
|
2023-09-19 09:00:25 +00:00
|
|
|
<title>CDN Test</title>
|
2023-11-22 09:18:37 +00:00
|
|
|
<!-- <script src="../../dist/umd/data-structure-typed.min.js"></script>-->
|
2023-12-29 03:15:19 +00:00
|
|
|
<script src="../../dist/umd/data-structure-typed.js"></script>
|
|
|
|
|
<!-- <script src='https://cdn.jsdelivr.net/npm/data-structure-typed/dist/umd/data-structure-typed.min.js'></script>-->
|
2023-11-20 11:27:25 +00:00
|
|
|
<!-- <script src='https://cdn.jsdelivr.net/npm/data-structure-typed@1.42.2/dist/umd/data-structure-typed.min.js'></script>-->
|
|
|
|
|
<!-- <script src='https://cdn.jsdelivr.net/npm/data-structure-typed@1.43.3/dist/umd/data-structure-typed.min.js'></script>-->
|
|
|
|
|
<!-- <script src='https://cdn.jsdelivr.net/npm/data-structure-typed@1.44.0/dist/umd/data-structure-typed.min.js'></script>-->
|
2023-11-20 09:30:55 +00:00
|
|
|
|
2023-11-13 04:50:33 +00:00
|
|
|
<script src='https://unpkg.com/js-sdsl@4.4.2/dist/umd/js-sdsl.js'></script>
|
2024-01-26 10:20:15 +00:00
|
|
|
<script>
|
|
|
|
|
const logPerf = function (label = 'function running cost', fn, args, thisArg) {
|
|
|
|
|
const start = performance.now();
|
|
|
|
|
let result;
|
|
|
|
|
if (thisArg) {
|
|
|
|
|
if (args && args.length > 0) result = fn.apply(thisArg, args);
|
|
|
|
|
else result = fn.apply(thisArg);
|
|
|
|
|
} else {
|
|
|
|
|
if (args && args.length > 0) result = fn(...args);
|
|
|
|
|
else result = fn();
|
|
|
|
|
}
|
|
|
|
|
console.log(`${(performance.now() - start).toFixed(2)} ms, ${label}, ${result}`);
|
|
|
|
|
}
|
|
|
|
|
</script>
|
2023-09-09 15:49:53 +00:00
|
|
|
</head>
|
|
|
|
|
<body>
|
2023-09-26 04:49:33 +00:00
|
|
|
<div id='app'>
|
|
|
|
|
<ul class='modules'>
|
2023-09-19 09:00:25 +00:00
|
|
|
|
|
|
|
|
</ul>
|
|
|
|
|
</div>
|
|
|
|
|
<script defer>
|
|
|
|
|
|
2023-11-21 09:30:57 +00:00
|
|
|
const $modules = document.querySelector('.modules');
|
2023-09-19 09:00:25 +00:00
|
|
|
|
2023-10-05 02:37:42 +00:00
|
|
|
try {
|
2023-11-21 09:30:57 +00:00
|
|
|
const { Queue } = dataStructureTyped;
|
2023-10-05 02:37:42 +00:00
|
|
|
const queue = new Queue();
|
2023-11-21 09:30:57 +00:00
|
|
|
const n = 1000000;
|
2024-01-26 10:20:15 +00:00
|
|
|
logPerf(`Queue ${n.toLocaleString()} enqueue`, () => {
|
|
|
|
|
for (let i = 0; i < n; i++) {
|
|
|
|
|
queue.push(i);
|
|
|
|
|
}
|
|
|
|
|
})
|
2023-10-05 02:37:42 +00:00
|
|
|
|
2024-01-26 10:20:15 +00:00
|
|
|
let last = 0;
|
2023-10-05 02:37:42 +00:00
|
|
|
|
2024-01-26 10:20:15 +00:00
|
|
|
logPerf(`Queue ${n.toLocaleString()} dequeue `, () => {
|
|
|
|
|
for (let i = 0; i < n; i++) {
|
|
|
|
|
last = queue.shift();
|
|
|
|
|
}
|
|
|
|
|
})
|
2023-10-05 02:37:42 +00:00
|
|
|
|
2023-10-25 07:51:50 +00:00
|
|
|
} catch (e) {
|
2023-10-05 02:37:42 +00:00
|
|
|
console.error(e);
|
2023-09-19 09:00:25 +00:00
|
|
|
}
|
2023-11-12 16:03:42 +00:00
|
|
|
try {
|
2023-11-21 09:30:57 +00:00
|
|
|
const { AVLTree } = dataStructureTyped;
|
|
|
|
|
|
2023-11-12 16:03:42 +00:00
|
|
|
const avlTree = new AVLTree();
|
|
|
|
|
const $avlTree = document.createElement('li');
|
|
|
|
|
const $avlTreeSpan = document.createElement('span');
|
|
|
|
|
$avlTreeSpan.innerText = 'AVLTree';
|
|
|
|
|
$avlTree.append($avlTreeSpan);
|
|
|
|
|
for (let i = 1; i < 31; i++) {
|
|
|
|
|
avlTree.add(i, i);
|
|
|
|
|
}
|
2023-11-21 09:30:57 +00:00
|
|
|
console.log(avlTree.bfs(), `avlTree.bfs()`);
|
|
|
|
|
avlTree.print();
|
2023-11-12 16:03:42 +00:00
|
|
|
$modules.append($avlTree);
|
|
|
|
|
} catch (e) {
|
|
|
|
|
console.error(e);
|
|
|
|
|
}
|
2023-09-19 09:00:25 +00:00
|
|
|
|
2023-11-10 03:01:49 +00:00
|
|
|
try {
|
2023-11-16 03:55:40 +00:00
|
|
|
const { BinaryTree } = dataStructureTyped;
|
2023-11-10 03:01:49 +00:00
|
|
|
const tree = new BinaryTree();
|
|
|
|
|
tree.add(3);
|
|
|
|
|
tree.add(12);
|
2023-11-13 05:07:28 +00:00
|
|
|
tree.addMany([1, 6, 9, 8, 5, 2, 3, 4, 7])
|
2023-11-10 03:01:49 +00:00
|
|
|
tree.add(10);
|
2023-11-21 09:30:57 +00:00
|
|
|
console.log(tree.isPerfectlyBalanced(), `tree.isPerfectlyBalanced()`);
|
2023-11-22 09:18:37 +00:00
|
|
|
tree.print(undefined, { isShowUndefined: true });
|
2023-11-10 03:01:49 +00:00
|
|
|
|
|
|
|
|
const node3 = tree.getNode(3);
|
|
|
|
|
if (node3) node3.right = tree.createNode(1);
|
2023-11-21 09:30:57 +00:00
|
|
|
console.log(tree.isPerfectlyBalanced(), `tree.isPerfectlyBalanced()`);
|
2023-11-10 03:01:49 +00:00
|
|
|
tree.print();
|
|
|
|
|
|
|
|
|
|
tree.clear();
|
|
|
|
|
tree.addMany([1, null, 2, null, 3, null, 4, null, 5, null, 6, null]);
|
2023-11-21 09:30:57 +00:00
|
|
|
console.log(tree.isPerfectlyBalanced(), `tree.isPerfectlyBalanced()`);
|
2023-11-22 09:18:37 +00:00
|
|
|
tree.print(undefined, { isShowNull: true });
|
2023-11-10 03:01:49 +00:00
|
|
|
} catch (e) {
|
|
|
|
|
console.error(e);
|
|
|
|
|
}
|
2023-11-12 16:03:42 +00:00
|
|
|
|
|
|
|
|
|
|
|
|
|
try {
|
2023-11-16 03:55:40 +00:00
|
|
|
const { OrderedMap } = sdsl;
|
2023-11-21 09:30:57 +00:00
|
|
|
const { RedBlackTree } = dataStructureTyped;
|
2023-11-20 09:30:55 +00:00
|
|
|
const cRBTree = new OrderedMap();
|
|
|
|
|
const rbTree = new RedBlackTree();
|
2023-11-13 04:50:33 +00:00
|
|
|
const tS = performance.now();
|
2023-11-20 09:30:55 +00:00
|
|
|
const n = 100000;
|
2023-11-21 09:30:57 +00:00
|
|
|
for (let i = 0; i < n; i++) {
|
2023-11-20 09:30:55 +00:00
|
|
|
rbTree.add(i, i);
|
2023-11-12 16:03:42 +00:00
|
|
|
}
|
2023-11-22 09:18:37 +00:00
|
|
|
console.log((performance.now() - tS).toFixed(2), `RedBlackTree ${n.toLocaleString()} add`);
|
2023-11-21 09:30:57 +00:00
|
|
|
console.log(`rbTree.size`, rbTree.size);
|
2023-11-22 13:29:44 +00:00
|
|
|
for (let i = 0; i < n - 8; i++) {
|
2023-11-21 09:30:57 +00:00
|
|
|
rbTree.delete(i)
|
|
|
|
|
}
|
2023-11-22 09:18:37 +00:00
|
|
|
rbTree.print(rbTree.root, { isShowRedBlackNIL: true });
|
2023-11-13 04:50:33 +00:00
|
|
|
const cS = performance.now();
|
2023-11-20 09:30:55 +00:00
|
|
|
for (let i = 1; i < 100000; i++) {
|
|
|
|
|
cRBTree.setElement(i, i);
|
2023-11-13 04:50:33 +00:00
|
|
|
}
|
2023-11-21 09:30:57 +00:00
|
|
|
console.log((performance.now() - cS).toFixed(2), `CRedBlackTree ${n.toLocaleString()} add`);
|
|
|
|
|
console.log(cRBTree.size(), `cRBTree.size()`);
|
2023-11-12 16:03:42 +00:00
|
|
|
} catch (e) {
|
|
|
|
|
console.error(e);
|
|
|
|
|
}
|
2023-11-13 04:50:33 +00:00
|
|
|
|
|
|
|
|
try {
|
2023-11-16 03:55:40 +00:00
|
|
|
const { PriorityQueue: CPriorityQueue } = sdsl;
|
|
|
|
|
const { PriorityQueue } = dataStructureTyped;
|
2023-12-25 02:56:04 +00:00
|
|
|
const pq = new PriorityQueue([], { comparator: (a, b) => b - a });
|
2023-11-13 04:50:33 +00:00
|
|
|
|
|
|
|
|
const tS = performance.now();
|
2023-11-20 09:30:55 +00:00
|
|
|
const n = 1000000;
|
|
|
|
|
for (let i = 0; i < n; i++) {
|
2023-11-13 04:50:33 +00:00
|
|
|
pq.add(i);
|
|
|
|
|
}
|
|
|
|
|
|
2023-11-20 09:30:55 +00:00
|
|
|
for (let i = 0; i < n; i++) {
|
2023-12-25 02:56:04 +00:00
|
|
|
pq.poll();
|
2023-11-13 04:50:33 +00:00
|
|
|
}
|
2023-11-22 09:18:37 +00:00
|
|
|
console.log((performance.now() - tS).toFixed(2), `PriorityQueue ${n.toLocaleString()} add`);
|
2023-11-21 09:30:57 +00:00
|
|
|
console.log(pq.size, `pq.size`);
|
2023-11-13 04:50:33 +00:00
|
|
|
const cS = performance.now();
|
|
|
|
|
const cpq = new CPriorityQueue();
|
|
|
|
|
|
2023-11-20 09:30:55 +00:00
|
|
|
for (let i = 0; i < n; i++) {
|
2023-11-13 04:50:33 +00:00
|
|
|
cpq.push(i);
|
|
|
|
|
}
|
|
|
|
|
|
2023-11-20 09:30:55 +00:00
|
|
|
for (let i = 0; i < n; i++) {
|
2023-11-13 04:50:33 +00:00
|
|
|
cpq.pop();
|
|
|
|
|
}
|
2023-11-21 09:30:57 +00:00
|
|
|
console.log((performance.now() - cS).toFixed(), `CPriorityQueue ${n.toLocaleString()} add`);
|
|
|
|
|
console.log(cpq.size(), `cpq.size()`);
|
2023-11-13 04:50:33 +00:00
|
|
|
} catch (e) {
|
|
|
|
|
console.error(e);
|
|
|
|
|
}
|
2023-11-22 13:29:44 +00:00
|
|
|
|
|
|
|
|
try {
|
|
|
|
|
const { BST, RedBlackTree, AVLTree } = dataStructureTyped;
|
|
|
|
|
|
|
|
|
|
const bst = new BST();
|
|
|
|
|
bst.add(11);
|
|
|
|
|
bst.add(3);
|
|
|
|
|
bst.addMany([15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5]);
|
|
|
|
|
bst.size === 16; // true
|
|
|
|
|
bst.has(6); // true
|
|
|
|
|
const node6 = bst.getNode(6); // BSTNode
|
|
|
|
|
bst.getHeight(6) === 2; // true
|
|
|
|
|
bst.getHeight() === 5; // true
|
|
|
|
|
bst.getDepth(6) === 3; // true
|
|
|
|
|
|
|
|
|
|
bst.getLeftMost()?.key === 1; // true
|
|
|
|
|
|
|
|
|
|
bst.delete(6);
|
|
|
|
|
bst.get(6); // undefined
|
|
|
|
|
bst.isAVLBalanced(); // true
|
|
|
|
|
bst.bfs()[0] === 11; // true
|
|
|
|
|
bst.print();
|
|
|
|
|
|
|
|
|
|
const objBST = new BST();
|
|
|
|
|
|
|
|
|
|
objBST.add(11, { "name": "Pablo", "age": 15 });
|
|
|
|
|
objBST.add(3, { "name": "Kirk", "age": 1 });
|
|
|
|
|
|
|
|
|
|
objBST.addMany([15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5], [
|
|
|
|
|
{ "name": "Alice", "age": 15 },
|
|
|
|
|
{ "name": "Bob", "age": 1 },
|
|
|
|
|
{ "name": "Charlie", "age": 8 },
|
|
|
|
|
{ "name": "David", "age": 13 },
|
|
|
|
|
{ "name": "Emma", "age": 16 },
|
|
|
|
|
{ "name": "Frank", "age": 2 },
|
|
|
|
|
{ "name": "Grace", "age": 6 },
|
|
|
|
|
{ "name": "Hannah", "age": 9 },
|
|
|
|
|
{ "name": "Isaac", "age": 12 },
|
|
|
|
|
{ "name": "Jack", "age": 14 },
|
|
|
|
|
{ "name": "Katie", "age": 4 },
|
|
|
|
|
{ "name": "Liam", "age": 7 },
|
|
|
|
|
{ "name": "Mia", "age": 10 },
|
|
|
|
|
{ "name": "Noah", "age": 5 }
|
|
|
|
|
]
|
|
|
|
|
);
|
|
|
|
|
objBST.print()
|
|
|
|
|
|
|
|
|
|
objBST.delete(11);
|
|
|
|
|
objBST.print()
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
const rbTree = new RedBlackTree();
|
|
|
|
|
rbTree.addMany([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5])
|
|
|
|
|
rbTree.isAVLBalanced(); // true
|
|
|
|
|
rbTree.delete(10);
|
|
|
|
|
rbTree.isAVLBalanced(); // true
|
|
|
|
|
console.log(`rbTree.delete(10)`);
|
|
|
|
|
rbTree.print();
|
|
|
|
|
|
|
|
|
|
rbTree.delete(14);
|
|
|
|
|
rbTree.print()
|
|
|
|
|
|
|
|
|
|
const avlTree = new AVLTree();
|
|
|
|
|
avlTree.addMany([11, 3, 15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5])
|
|
|
|
|
avlTree.isAVLBalanced(); // true
|
|
|
|
|
avlTree.delete(10);
|
|
|
|
|
avlTree.isAVLBalanced(); // true
|
|
|
|
|
avlTree.print()
|
|
|
|
|
avlTree.delete(14);
|
|
|
|
|
avlTree.print()
|
|
|
|
|
} catch (e) {
|
|
|
|
|
console.error(e);
|
|
|
|
|
}
|
2023-11-26 12:11:29 +00:00
|
|
|
|
2023-11-25 14:49:54 +00:00
|
|
|
try {
|
2023-11-26 12:11:29 +00:00
|
|
|
const {
|
2023-11-25 14:49:54 +00:00
|
|
|
AVLTree,
|
2023-11-26 12:11:29 +00:00
|
|
|
BinaryTree,
|
|
|
|
|
BST,
|
|
|
|
|
Deque,
|
|
|
|
|
DoublyLinkedList,
|
|
|
|
|
HashMap,
|
|
|
|
|
Heap,
|
|
|
|
|
MaxPriorityQueue,
|
|
|
|
|
MinHeap,
|
|
|
|
|
MinPriorityQueue,
|
|
|
|
|
Queue,
|
|
|
|
|
RedBlackTree,
|
|
|
|
|
SinglyLinkedList,
|
|
|
|
|
Stack,
|
2024-01-08 14:22:41 +00:00
|
|
|
TreeMultiMap,
|
2023-11-26 12:11:29 +00:00
|
|
|
Trie
|
2023-11-25 14:49:54 +00:00
|
|
|
} = dataStructureTyped;
|
|
|
|
|
const orgArr = [6, 1, 2, 7, 5, 3, 4, 9, 8];
|
|
|
|
|
const orgStrArr = ["trie", "trial", "trick", "trip", "tree", "trend", "triangle", "track", "trace", "transmit"];
|
|
|
|
|
const entries = [[6, 6], [1, 1], [2, 2], [7, 7], [5, 5], [3, 3], [4, 4], [9, 9], [8, 8]];
|
|
|
|
|
|
|
|
|
|
const queue = new Queue(orgArr);
|
2023-11-27 02:12:15 +00:00
|
|
|
queue.print(); // [6, 1, 2, 7, 5, 3, 4, 9, 8]
|
2023-11-25 14:49:54 +00:00
|
|
|
|
|
|
|
|
const deque = new Deque(orgArr);
|
2023-11-27 02:12:15 +00:00
|
|
|
deque.print(); // [6, 1, 2, 7, 5, 3, 4, 9, 8]
|
2023-11-25 14:49:54 +00:00
|
|
|
|
|
|
|
|
const sList = new SinglyLinkedList(orgArr);
|
2023-11-27 02:12:15 +00:00
|
|
|
sList.print(); // [6, 1, 2, 7, 5, 3, 4, 9, 8]
|
2023-11-25 14:49:54 +00:00
|
|
|
|
|
|
|
|
const dList = new DoublyLinkedList(orgArr);
|
2023-11-27 02:12:15 +00:00
|
|
|
dList.print(); // [6, 1, 2, 7, 5, 3, 4, 9, 8]
|
2023-11-25 14:49:54 +00:00
|
|
|
|
|
|
|
|
const stack = new Stack(orgArr);
|
2023-11-27 02:12:15 +00:00
|
|
|
stack.print(); // [6, 1, 2, 7, 5, 3, 4, 9, 8]
|
2023-11-25 14:49:54 +00:00
|
|
|
|
|
|
|
|
const minHeap = new MinHeap(orgArr);
|
2023-11-27 02:12:15 +00:00
|
|
|
minHeap.print(); // [1, 5, 2, 7, 6, 3, 4, 9, 8]
|
2023-11-25 14:49:54 +00:00
|
|
|
|
|
|
|
|
const maxPQ = new MaxPriorityQueue(orgArr);
|
2023-11-27 02:12:15 +00:00
|
|
|
maxPQ.print(); // [9, 8, 4, 7, 5, 2, 3, 1, 6]
|
2023-11-25 14:49:54 +00:00
|
|
|
|
|
|
|
|
const biTree = new BinaryTree(entries);
|
|
|
|
|
biTree.print();
|
2023-11-27 02:12:15 +00:00
|
|
|
// ___6___
|
|
|
|
|
// / \
|
|
|
|
|
// ___1_ _2_
|
|
|
|
|
// / \ / \
|
|
|
|
|
// _7_ 5 3 4
|
|
|
|
|
// / \
|
|
|
|
|
// 9 8
|
2023-11-25 14:49:54 +00:00
|
|
|
|
|
|
|
|
const bst = new BST(entries);
|
|
|
|
|
bst.print();
|
2023-11-27 02:12:15 +00:00
|
|
|
// _____5___
|
|
|
|
|
// / \
|
|
|
|
|
// _2_ _7_
|
|
|
|
|
// / \ / \
|
|
|
|
|
// 1 3_ 6 8_
|
|
|
|
|
// \ \
|
|
|
|
|
// 4 9
|
|
|
|
|
|
2023-11-25 14:49:54 +00:00
|
|
|
|
|
|
|
|
const rbTree = new RedBlackTree(entries);
|
|
|
|
|
rbTree.print();
|
2023-11-27 02:12:15 +00:00
|
|
|
// ___4___
|
|
|
|
|
// / \
|
|
|
|
|
// _2_ _6___
|
|
|
|
|
// / \ / \
|
|
|
|
|
// 1 3 5 _8_
|
|
|
|
|
// / \
|
|
|
|
|
// 7 9
|
|
|
|
|
|
2023-11-25 14:49:54 +00:00
|
|
|
|
|
|
|
|
const avl = new AVLTree(entries);
|
|
|
|
|
avl.print();
|
2023-11-27 02:12:15 +00:00
|
|
|
// ___4___
|
|
|
|
|
// / \
|
|
|
|
|
// _2_ _6___
|
|
|
|
|
// / \ / \
|
|
|
|
|
// 1 3 5 _8_
|
|
|
|
|
// / \
|
|
|
|
|
// 7 9
|
2023-11-25 14:49:54 +00:00
|
|
|
|
2024-01-08 14:22:41 +00:00
|
|
|
const treeMulti = new TreeMultiMap(entries);
|
2023-11-25 14:49:54 +00:00
|
|
|
treeMulti.print();
|
2023-11-27 02:12:15 +00:00
|
|
|
// ___4___
|
|
|
|
|
// / \
|
|
|
|
|
// _2_ _6___
|
|
|
|
|
// / \ / \
|
|
|
|
|
// 1 3 5 _8_
|
|
|
|
|
// / \
|
|
|
|
|
// 7 9
|
2023-11-25 14:49:54 +00:00
|
|
|
|
|
|
|
|
const hm = new HashMap(entries);
|
2023-11-27 02:12:15 +00:00
|
|
|
hm.print() // [[6, 6], [1, 1], [2, 2], [7, 7], [5, 5], [3, 3], [4, 4], [9, 9], [8, 8]]
|
|
|
|
|
|
2023-11-25 14:49:54 +00:00
|
|
|
const rbTreeH = new RedBlackTree(hm);
|
|
|
|
|
rbTreeH.print();
|
2023-11-27 02:12:15 +00:00
|
|
|
// ___4___
|
|
|
|
|
// / \
|
|
|
|
|
// _2_ _6___
|
|
|
|
|
// / \ / \
|
|
|
|
|
// 1 3 5 _8_
|
|
|
|
|
// / \
|
|
|
|
|
// 7 9
|
2023-11-25 14:49:54 +00:00
|
|
|
|
|
|
|
|
const pq = new MinPriorityQueue(orgArr);
|
2023-11-27 02:12:15 +00:00
|
|
|
pq.print(); // [1, 5, 2, 7, 6, 3, 4, 9, 8]
|
|
|
|
|
|
2023-11-25 14:49:54 +00:00
|
|
|
const bst1 = new BST(pq);
|
|
|
|
|
bst1.print();
|
2023-11-27 02:12:15 +00:00
|
|
|
// _____5___
|
|
|
|
|
// / \
|
|
|
|
|
// _2_ _7_
|
|
|
|
|
// / \ / \
|
|
|
|
|
// 1 3_ 6 8_
|
|
|
|
|
// \ \
|
|
|
|
|
// 4 9
|
2023-11-25 14:49:54 +00:00
|
|
|
|
|
|
|
|
const dq1 = new Deque(orgArr);
|
2023-11-27 02:12:15 +00:00
|
|
|
dq1.print(); // [6, 1, 2, 7, 5, 3, 4, 9, 8]
|
2023-11-25 14:49:54 +00:00
|
|
|
const rbTree1 = new RedBlackTree(dq1);
|
|
|
|
|
rbTree1.print();
|
2023-11-27 02:12:15 +00:00
|
|
|
// _____5___
|
|
|
|
|
// / \
|
|
|
|
|
// _2___ _7___
|
|
|
|
|
// / \ / \
|
|
|
|
|
// 1 _4 6 _9
|
|
|
|
|
// / /
|
|
|
|
|
// 3 8
|
2023-11-27 03:24:23 +00:00
|
|
|
|
2023-11-25 14:49:54 +00:00
|
|
|
|
|
|
|
|
const trie2 = new Trie(orgStrArr);
|
2023-11-27 02:12:15 +00:00
|
|
|
trie2.print(); // ['trie', 'trial', 'triangle', 'trick', 'trip', 'tree', 'trend', 'track', 'trace', 'transmit']
|
2023-11-25 14:49:54 +00:00
|
|
|
const heap2 = new Heap(trie2, { comparator: (a, b) => Number(a) - Number(b) });
|
2023-11-27 02:12:15 +00:00
|
|
|
heap2.print(); // ['transmit', 'trace', 'tree', 'trend', 'track', 'trial', 'trip', 'trie', 'trick', 'triangle']
|
2023-11-25 14:49:54 +00:00
|
|
|
const dq2 = new Deque(heap2);
|
2023-11-27 02:12:15 +00:00
|
|
|
dq2.print(); // ['transmit', 'trace', 'tree', 'trend', 'track', 'trial', 'trip', 'trie', 'trick', 'triangle']
|
2023-11-25 14:49:54 +00:00
|
|
|
const entries2 = dq2.map((el, i) => [i, el]);
|
|
|
|
|
const avl2 = new AVLTree(entries2);
|
|
|
|
|
avl2.print();
|
2023-11-27 02:12:15 +00:00
|
|
|
// ___3_______
|
|
|
|
|
// / \
|
|
|
|
|
// _1_ ___7_
|
|
|
|
|
// / \ / \
|
|
|
|
|
// 0 2 _5_ 8_
|
|
|
|
|
// / \ \
|
|
|
|
|
// 4 6 9
|
2023-11-27 03:24:23 +00:00
|
|
|
|
2023-11-26 12:11:29 +00:00
|
|
|
} catch (e) {
|
2023-11-25 14:49:54 +00:00
|
|
|
console.error(e);
|
|
|
|
|
}
|
2024-01-24 10:38:34 +00:00
|
|
|
|
|
|
|
|
function heapTest() {
|
|
|
|
|
const heap = new dataStructureTyped.Heap([], { comparator: (a, b) => b - a });
|
|
|
|
|
|
|
|
|
|
heap.add(10);
|
|
|
|
|
heap.add(5);
|
|
|
|
|
heap.add(15);
|
|
|
|
|
|
|
|
|
|
const max = heap.poll();
|
|
|
|
|
console.log(max); // 15
|
|
|
|
|
|
|
|
|
|
const max2 = heap.peek();
|
|
|
|
|
console.log(max2); // 15
|
|
|
|
|
|
|
|
|
|
let isEmpty = heap.isEmpty();
|
|
|
|
|
console.log(isEmpty); // false
|
|
|
|
|
|
|
|
|
|
heap.clear();
|
|
|
|
|
isEmpty = heap.isEmpty();
|
|
|
|
|
console.log(isEmpty); // true
|
|
|
|
|
|
|
|
|
|
const minNumHeap = new dataStructureTyped.MinHeap([1, 6, 2, 0, 5]);
|
|
|
|
|
minNumHeap.add(9);
|
|
|
|
|
minNumHeap.has(1) // true
|
|
|
|
|
minNumHeap.has(2) // true
|
|
|
|
|
minNumHeap.poll() // 0
|
|
|
|
|
minNumHeap.poll() // 1
|
|
|
|
|
minNumHeap.peek() // 2
|
|
|
|
|
minNumHeap.has(1); // false
|
|
|
|
|
minNumHeap.has(2); // true
|
|
|
|
|
|
|
|
|
|
const arrFromHeap = minNumHeap.toArray();
|
|
|
|
|
arrFromHeap.length // 4
|
|
|
|
|
arrFromHeap[0] // 2
|
|
|
|
|
arrFromHeap[1] // 5
|
|
|
|
|
arrFromHeap[2] // 9
|
|
|
|
|
arrFromHeap[3] // 6
|
|
|
|
|
minNumHeap.sort() // [2, 5, 6, 9]
|
|
|
|
|
|
|
|
|
|
const maxHeap = new dataStructureTyped.MaxHeap([], { comparator: (a, b) => b.keyA - a.keyA });
|
|
|
|
|
const obj1 = { keyA: 'a1' }, obj6 = { keyA: 'a6' }, obj5 = { keyA: 'a5' }, obj2 = { keyA: 'a2' },
|
|
|
|
|
obj0 = { keyA: 'a0' }, obj9 = { keyA: 'a9' };
|
|
|
|
|
|
|
|
|
|
maxHeap.add(obj1);
|
|
|
|
|
maxHeap.has(obj1) // true
|
|
|
|
|
maxHeap.has(obj9) // false
|
|
|
|
|
maxHeap.add(obj6);
|
|
|
|
|
maxHeap.has(obj6) // true
|
|
|
|
|
maxHeap.add(obj5);
|
|
|
|
|
maxHeap.add(obj2);
|
|
|
|
|
maxHeap.add(obj0);
|
|
|
|
|
maxHeap.add(obj9);
|
|
|
|
|
maxHeap.has(obj9) // true
|
|
|
|
|
|
|
|
|
|
const peek9 = maxHeap.peek();
|
|
|
|
|
console.log(peek9.keyA) // 'a9'
|
|
|
|
|
|
|
|
|
|
const heapToArr = maxHeap.toArray();
|
|
|
|
|
console.log(heapToArr.map(ele => ele?.keyA)); // ['a9', 'a2', 'a6', 'a1', 'a0', 'a5']
|
|
|
|
|
|
|
|
|
|
const values = ['a9', 'a6', 'a5', 'a2', 'a1', 'a0'];
|
|
|
|
|
let i = 0;
|
|
|
|
|
while (maxHeap.size > 0) {
|
|
|
|
|
const polled = maxHeap.poll();
|
|
|
|
|
console.log(polled.keyA) // values[i]
|
|
|
|
|
i++;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
2023-09-19 09:00:25 +00:00
|
|
|
</script>
|
2023-09-09 15:49:53 +00:00
|
|
|
|
|
|
|
|
</body>
|
2023-09-19 09:00:25 +00:00
|
|
|
</html>
|
2023-09-21 16:53:34 +00:00
|
|
|
|
