电脑配置
CPU：AMD X4 640
内存： 宏想 DDR3 1600MHz 8g
主板：华擎 980DE3/U3S3 R2.0
浏览器：chrome 79.0.3945.88（正式版本） （64 位）
时间测试函数
function testRunTime(fn) {
let start = new Date();
let end = null;
fn();
end = new Date();
console.log(`运行时间: ${(end - start) / 1000}秒`);
}
参考书籍:《算法第4版》
数据结构
存储相关
集合 存储的元素唯一
链表
队列 先进先出
栈 后进先出
最大堆 最大元素排最前面，数组实现
排序相关
数组
查找相关
并查集
映射 根据key返回value
二叉查找树
自平衡二叉查找树
红黑树
哈希表
数组
// 数组
class MyArray {
constructor(capacity=10) {
this._data = new Array(capacity);
this._size = 0;
}
get length() {
return this._size;
}
get capacity() {
return this._data.length;
}
// 插入指定位置
insert(index, e) {
if (index < 0 || index >= this._data.length) {
throw new RangeError("index is invalid");
}
for (let i=this._size-1; i>=index; i--) {
this._data[i+1] = this._data[i];
}
this._data[index] = e;
this._size++;
}
// 添加到最后
insertLast(e) {
this.insert(this._size, e);
}
// 添加到开头
insertFirst(e) {
this.insert(0, e);
}
// 获取位置为index的元素
get(index) {
if (index < 0 || index >= this._data.length) {
throw new RangeError("index is invalid");
}
return this._data[index];
}
// 删除位置为index的元素
remove(index) {
if (index < 0 || index >= this._data.length) {
throw new RangeError("index is invalid");
}
let ret = this._data[index];
for (let i=index,len=this._size-1; i<=len; i++) {
this._data[i] = this._data[i+1];
}
this._size--;
return ret;
}
// 更新元素
set(index, e) {
if (index < 0 || index >= this._data.length) {
throw new RangeError("index is invalid");
}
if (this._data[index]) {
this._data[index] = e;
} else { // 不存在就添加
this.insertLast(e);
}
}
// 是否包含元素
includes(e) {
for (let i=0,len=this._size; i<len; i++) {
if (Object.is(this._data[i], e)) {
return true;
}
}
return false;
}
// 查找元素, 返回索引
find(e) {
for (let i=0,len=this._size; i<len; i++) {
if (Object.is(this._data[i], e)) {
return i;
}
}
return -1;
}
toString() {
let str = "[";
for (let i=0,len=this._size; i<len; i++) {
str += this._data[i];
if (i != len-1) {
str += ",";
}
}
str += "]";
return str;
}
}
export default MyArray;
链表
单向链表
// 链表
class LinkedListNode {
constructor(e, next=null) {
this.e = e;
this.next = next;
}
}
class LinkedList {
constructor() {
this._dummyhead = new LinkedListNode(null);
this._tail = null; // 尾指针
this._size = 0;
}
get length() {
return this._size;
}
get isEmpty() {
return this._size == 0;
}
// 插入元素
insert(index, e) {
if (index < 0 || index>this._size) {
throw new RangeError("index is invalid");
}
let cur = this._dummyhead;
for (let i=0; i<index; i++) {
cur = cur.next;
}
cur.next = new LinkedListNode(e, cur.next);
if (this._size === index) {
this._tail = cur.next;
}
this._size++;
}
// 插入表头
insertFirst(e) {
this._dummyhead.next = new LinkedListNode(e, this._dummyhead.next);
if (this._size == 0) {
this._tail = this._dummyhead.next;
}
this._size++;
}
// 插入表尾
insertLast(e) {
if (this._size == 0) {
this._dummyhead.next = new LinkedListNode(e);
this._tail = this._dummyhead.next;
} else {
this._tail.next = new LinkedListNode(e);
this._tail = this._tail.next;
}
this._size++;
}
// 删除元素
removeElement(e) {
if (this.isEmpty) {
return new Error("Element is empty");
}
let prev = this._dummyhead;
while (prev != null) {
if (Object.is(prev.next.e,e)) {
break;
}
prev = prev.next;
}
if (prev != null) {
let ret = prev.next;
prev.next = ret.next;
ret.next = null;
if (Object.is(ret.e, this._tail.e)) {
this._tail = prev;
}
this._size--;
return ret;
}
return null;
}
// 根据位置删除元素
removeIndex(index) {
if (index < 0 || index>this._size) {
throw new RangeError("index is invalid");
}
if (this.isEmpty) {
return new Error("Element is empty");
}
let prev = this._dummyhead;
let ret;
for (let i=0; i<index; i++) {
prev = prev.next;
}
ret = prev.next;
prev.next = ret.next;
ret.next = null;
if (Object.is(ret.e, this._tail.e)) {
this._tail = prev;
}
this._size--;
return ret;
}
// 查找元素
find(e) {
let cur = this._dummyhead.next;
let index = 0;
while (cur !== null) {
if (Object.is(cur.e, e)) {
break;
}
index++;
cur = cur.next;
}
if (cur == null) {
return -1;
} else {
return index;
}
}
contains(e) {
let result = this.find(e);
return result != -1 ? true : false;
}
// 访问元素
get(index) {
if (index < 0 || index>this._size) {
throw new RangeError("index is invalid");
}
let cur = this._dummyhead.next;
for (let i=0; i<index; i++) {
cur = cur.next;
}
return cur;
}
toString() {
let res = "";
let cur = this._dummyhead.next;
for (let i=0,len=this._size; i<len; i++) {
res += cur.e;
if (i != len-1) {
res += " > ";
}
cur = cur.next;
}
return res;
}
}
export default LinkedList;
双向链表
class LinkedListNode {
constructor(item, next = null, prev = null) {
this.item = item;
this.next = next;
this.prev = prev;
}
}
// 双向链表
class LinkedList {
constructor() {
this._dummyhead = new LinkedListNode(null);
this._tail = null; // 尾指针
this._size = 0;
}
get size() {
return this._size;
}
get isEmpty() {
return this._size === 0;
}
// 插入元素
insert(index, e) {
if (index < 0 || index > this._size) {
throw new RangeError("index is invalid");
}
let cur = this._dummyhead;
for (let i = 0; i < index; i++) {
cur = cur.next;
}
cur.next = new LinkedListNode(e, cur.next, cur);
if (cur.next.next) {
cur.next.next.prev = cur.next;
}
if (this._size === index) {
this._tail = cur.next;
}
this._size++;
}
// 插入表头
unshift(e) {
this._dummyhead.next = new LinkedListNode(e, this._dummyhead.next);
if (this._size == 0) {
this._tail = this._dummyhead.next;
}
this._size++;
}
// 插入表尾
push(e) {
if (this._size == 0) {
this._dummyhead.next = new LinkedListNode(e, null, this._dummyhead);
this._tail = this._dummyhead.next;
} else {
this._tail.next = new LinkedListNode(e, null, this._tail);
this._tail = this._tail.next;
}
this._size++;
}
// 删除元素
removeElement(e) {
if (this.isEmpty) {
return new Error("Element is empty");
}
let prev = this._dummyhead;
while (prev != null) {
if (prev.next !== null && Object.is(prev.next.item, e)) {
break;
}
prev = prev.next;
}
if (prev != null) {
let ret = prev.next;
prev.next = ret.next;
if (ret.next) {
ret.next.prev = prev; // 调整上一个元素指向
}
ret.next = null;
if (Object.is(ret.item, this._tail.item)) {
this._tail = prev;
}
this._size--;
return ret;
}
return null;
}
// 根据位置删除元素
removeIndex(index) {
if (index < 0 || index > this._size) {
throw new RangeError("index is invalid");
}
if (this.isEmpty) {
return new Error("Element is empty");
}
let prev = this._dummyhead;
let ret;
for (let i = 0; i < index; i++) {
prev = prev.next;
}
ret = prev.next;
prev.next = ret.next;
if (ret.next) {
ret.next.prev = prev; // 调整上一个元素指向
}
ret.next = null;
if (Object.is(ret.item, this._tail.item)) {
this._tail = prev;
}
this._size--;
return ret;
}
pop() {
return this.removeIndex(this.size - 1);
}
shift() {
return this.removeIndex(0);
}
// 查找元素
find(e) {
let cur = this._dummyhead.next;
let index = 0;
while (cur !== null) {
if (Object.is(cur.item, e)) {
break;
}
index++;
cur = cur.next;
}
if (cur == null) {
return -1;
} else {
return index;
}
}
contains(e) {
let result = this.find(e);
return result != -1 ? true : false;
}
// 访问元素
get(index) {
if (index < 0 || index > this._size) {
throw new RangeError("index is invalid");
}
let cur = this._dummyhead.next;
for (let i = 0; i < index; i++) {
cur = cur.next;
}
return cur;
}
toString() {
let res = "";
let cur = this._dummyhead.next;
for (let i = 0, len = this._size; i < len; i++) {
res += cur.item;
if (i != len - 1) {
res += " > ";
}
cur = cur.next;
}
return res;
}
iterator() { // 迭代器
return {
_item: this._dummyhead,
next() {
if (this.hasNext()) {
let ret = this._item.next;
this._item = this._item.next;
return ret;
}
return null;
},
hasNext() {
return this._item.next !== null;
}
}
}
}
栈
- 数组实现
class Stack {
constructor() {
this._data = [];
}
push(e) {
this._data.push(e);
}
pop() {
return this._data.pop();
}
peek() {
return this._data[0];
}
isEmpty() {
return this._data.length == 0;
}
get length() {
return this._data.length;
}
}
export default Stack;
- 链表实现
import LinkedList from "./LinkedList.js";
// 先引入链表
class Stack {
constructor() {
this._data = new LinkedList();
}
push(e) {
this._data.insertFirst(e);
}
pop() {
return this._data.removeIndex(0);
}
peek() {
return this._data.get(0);
}
get isEmpty() {
return this._data.isEmpty;
}
get lenght() {
return this._data.length;
}
}
export default Stack;
队列
- 数组实现
class Queue {
constructor() {
this._data = [];
}
enqueue(e) {
this._data.push(e);
}
dequeue() {
return this._data.shift();
}
front() {
return this._data[0];
}
get isEmpty() {
return this._data.length == 0;
}
get length() {
return this._data.length;
}
toString() {
return "Front ["+this._data.toString+"]";
}
}
export default Queue;
- 链表实现
import LinkedList from "./LinkedList.js";
class Queue {
constructor() {
this._data = new LinkedList();
}
// 进队
enqueue(e) {
this._data.insertLast(e);
}
// 出队
dequeue() {
return this._data.removeIndex(0);
}
// 队首元素
front() {
return this._data.get(0);
}
get isEmpty() {
return this._data.length == 0;
}
get length() {
return this._data.length;
}
toString() {
return "Front "+this._data.toString();
}
}
export default Queue;
二叉查找树
最好情况O(log2^n), 最坏情况 O(n)
最坏的情况时会退化成链表。于是有了自平衡二叉树,在任何情况都能保持O(log2^n)
class Node {
constructor(key, value, size = 0) {
this.key = key;
this.value = value;
this.size = size;
this.left = this.right = null;
}
}
class BST {
constructor() {
this.root = null;
}
get size() {
return this._getSize(this.root);
}
_getSize(node) {
if (node === null) {
return 0;
} else {
return node.size;
}
}
get(key) {
function _get(node, key) {
if (node === null) return null;
if (key > node.key) {
return _get(node.right, key);
} else if (key < node.key) {
return _get(node.left, key);
} else {
return node.value;
}
}
key = this._strToNum(key);
return _get(this.root, key);
}
put(key, value) {
let _this = this;
key = this._strToNum(key);
this.root = _put(this.root, key, value);
function _put(node, key, value) {
if (node === null) { return new Node(key, value) };
if (key < node.key) {
node.left = _put(node.left, key, value);
} else if (key > node.key) {
node.right = _put(node.right, key, value);
} else {
node.value = value;
}
node.size = _this._getSize(node.left) + _this._getSize(node.right) + 1;
return node;
}
}
contains(key) {
return this.get(key) !== null;
}
delete(key) {
// 删除思路：拿到被删除元素的右子树最小的元素，放到当前位置。因为被删除元素的右子树最小的元素 满足 大于左子树任意一个且小于右子树任意一个，不会打破顺序。
let ret = null;
let _this = this;
key = this._strToNum(key);
function _delete(node, key) {
if (node === null) { return null }
if (key < node.key) {
node.left = _delete(node.left, key);
} else if (key > node.key) {
node.right = _delete(node.right, key)
} else {
ret = node;
if (node.right === null) return node.left;
if (node.left === null) return node.right;
node = _this._min(node.right);
_this._deleteMin(node.right);
}
node.size = _this._getSize(node.left) + _this._getSize(node.right) + 1;
return node;
}
this.root = _delete(this.root, key);
return ret;
}
// 前序遍历
preOrder() {
_preOrder(this.root);
function _preOrder(node) {
if (node == null) {
return;
}
console.log(node.value);
_preOrder(node.left);
_preOrder(node.right);
}
}
// 中序遍历
inOrder() {
_inOrder(this.root);
function _inOrder(node) {
if (node == null) {
return;
}
_inOrder(node.left);
console.log(node.value);
_inOrder(node.right);
}
}
// 后序序遍历
postOrder() {
_postOrder(this.root);
function _postOrder(node) {
if (node == null) {
return;
}
_postOrder(node.left);
_postOrder(node.right);
console.log(node.value);
}
}
// 层序遍历
levelOrder() {
let queue = []; // 引入队列
let node;
queue.push(this.root);
while (queue.length) {
node = queue.shift();
console.log(node.value);
if (node.left != null) {
queue.push(node.left);
}
if (node.right != null) {
queue.push(node.right);
}
}
}
_min(node = this.root) { // 是按键值转成数字的大小比较，并非按照value比较，所以最小的指的是键值转成数字后的大小
if (node === null) { return null }
return _min(node);
function _min(node) {
if (node.left === null) return node;
return _min(node.left);
}
}
_deleteMin(node = this.root) { // 最左边那个就是最小的
let ret = this._min(this.root);
let _this = this;
if (ret === null) { return null }
this.root = _deleteMin(node);
return ret;
function _deleteMin(node) {
if (node === null) { return node }
if (node.left === null) {
node = node.right;
} else if (node.left.left === null) {
node.left = node.left.right;
} else {
node.left = _deleteMin(node.left);
}
if (node) {
node.size = _this._getSize(node.left) + _this._getSize(node.right) + 1;
}
return node;
}
}
_strToNum(key) { // 将字符串转成数字，方便比较大小
if (typeof key !== "string") { throw ("key need string type") }
let num = "";
for (let i = 0; i < key.length; i++) {
num += String(key.charAt(i).charCodeAt());
}
return Number(num);
}
}
自平衡二叉查找树
查找复杂度：O(log2^n)
插入和删除都要判断平衡，进行相应的旋转
// 学习前提：需要了解自平衡二叉树的4种倾斜状态、4种倾斜状态对应的旋转操作、判断是否平衡:左右子树高度差大于等于2为不平衡
// key 最终以数字形式保存，目的是方便比较。如果key有用处于，可以在比较时再进行转换，但是这需要额外的成本
// 自平衡的关键：旋转操作、用平衡因子判断属于哪种倾斜然后使用哪种旋转操作
// 节点高度 = 子节点高度最高那个。默认为1
class Node {
constructor(key, value, height = 1) {
this.key = key;
this.value = value;
this.height = height;
this.left = this.right = null;
}
}
class AVL {
constructor() {
this.root = null;
}
get height() {
return this._getHeight(this.root);
}
_getHeight(node) {
if (node === null) {
return 0;
} else {return node.height}
}
_leftRotate(node) { // 右倾斜使用
let n = node;
node = node.right;
n.right = node.left;
node.left = n;
n.height = Math.max(this._getHeight(n.left), this._getHeight(n.right))+1;
node.height = Math.max(this._getHeight(node.left), this._getHeight(node.right))+1;
return node;
}
_rightRotate(node) { // 左倾斜使用
let n = node;
node = node.left;
n.left = node.right;
node.right = n;
n.height = Math.max(this._getHeight(n.left), this._getHeight(n.right))+1;
node.height = Math.max(this._getHeight(node.left), this._getHeight(node.right))+1;
return node;
}
_rlRotate(node) { // 右-左倾斜使用
node.right = this._rightRotate(node.right);
node = this._leftRotate(node);
return node;
}
_lrRotate(node) { // 左-右倾斜使用
node.left = this._leftRotate(node.left);
node = this._rightRotate(node);
return node;
}
_getBalanceFactor(node) { // 获取平衡因子用于判断倾斜状态
if(node == null) {
return 0;
}
return this._getHeight(node.left) - this._getHeight(node.right);
}
_rotate(node) { // 用于平衡二叉树
let balanceFactor = this._getBalanceFactor(node);
if (Math.abs(balanceFactor) > 1) { // 任意一边倾斜 任意一边高度差高于2
if (balanceFactor > 1 && this._getBalanceFactor(node.left) >= 0) { // 左倾斜
node = this._rightRotate(node);
}
if (balanceFactor < -1 && this._getBalanceFactor(node.right) <= 0) { // 右倾斜
node = this._leftRotate(node);
}
if(balanceFactor > 1 && this._getBalanceFactor(node.left) < 0) { // 左-右倾斜
node = this._lrRotate(node);
}
if (balanceFactor < -1 && this._getBalanceFactor(node.right) > 0) { // 右-左倾斜
node = this._rlRotate(node);
}
}
return node;
}
get(key) {
function _get(node, key) {
if (node === null) return null;
if (key > node.key) {
return _get(node.right, key);
} else if (key < node.key) {
return _get(node.left, key);
} else {
return node.value;
}
}
key = this._strToNum(key);
return _get(this.root, key);
}
put(key, value) {
let _this = this;
key = this._strToNum(key);
this.root = _put(this.root, key, value);
function _put(node, key, value) {
if (node === null) { return new Node(key, value) };
if (key < node.key) {
node.left = _put(node.left, key, value);
} else if (key > node.key) {
node.right = _put(node.right, key, value);
} else {
node.value = value;
}
node.height = Math.max(_this._getHeight(node.left), _this._getHeight(node.right))+1;
return _this._rotate(node);
}
}
contains(key) {
return this.get(key) !== null;
}
delete(key) {
// 删除思路：拿到被删除元素的右子树最小的元素，放到当前位置。
// 因为被删除元素的右子树最小的元素 满足 大于左子树任意一个且小于右子树任意一个，不会打破顺序。
let ret = null;
let _this = this;
key = this._strToNum(key);
function _delete(node, key) {
if (node === null) { return null }
if (key < node.key) {
node.left = _delete(node.left, key);
} else if (key > node.key) {
node.right = _delete(node.right, key)
} else {
ret = node;
if (node.right === null) return node.left;
if (node.left === null) return node.right;
node = _this._min(node.right);
_this._deleteMin(node.right);
}
node.height = Math.max(_this._getHeight(node.left), _this._getHeight(node.right))+1;
return _this._rotate(node);
}
this.root = _delete(this.root, key);
return ret;
}
// 前序遍历
preOrder() {
_preOrder(this.root);
function _preOrder(node) {
if (node == null) {
return;
}
console.log(node.value);
_preOrder(node.left);
_preOrder(node.right);
}
}
// 中序遍历
inOrder() {
_inOrder(this.root);
function _inOrder(node) {
if (node == null) {
return;
}
_inOrder(node.left);
console.log(node.value);
_inOrder(node.right);
}
}
// 后序序遍历
postOrder() {
_postOrder(this.root);
function _postOrder(node) {
if (node == null) {
return;
}
_postOrder(node.left);
_postOrder(node.right);
console.log(node.value);
}
}
// 层序遍历
levelOrder() {
let queue = []; // 引入队列
let node;
queue.push(this.root);
while (queue.length) {
node = queue.shift();
console.log(node.value);
if (node.left != null) {
queue.push(node.left);
}
if (node.right != null) {
queue.push(node.right);
}
}
}
_min(node = this.root) { // 是按键值转成数字的大小比较，并非按照value比较，所以最小的指的是键值转成数字后的大小
if (node === null) { return null }
return _min(node);
function _min(node) {
if (node.left === null) return node;
return _min(node.left);
}
}
_deleteMin(node = this.root) { // 最左边那个就是最小的
let ret = this._min(this.root);
let _this = this;
if (ret === null) { return null }
this.root = _deleteMin(node);
return ret;
function _deleteMin(node) {
if (node === null) { return node }
if (node.left === null) {
node = node.right;
} else if (node.left.left === null) {
node.left = node.left.right;
} else {
node.left = _deleteMin(node.left);
}
if (node) {
node.size = _this._getSize(node.left) + _this._getSize(node.right) + 1;
}
return node;
}
}
_strToNum(key) { // 将字符串转成数字，方便比较大小
if (typeof key !== "string") { throw ("key need string type") }
let num = "";
for (let i = 0; i < key.length; i++) {
num += String(key.charAt(i).charCodeAt());
}
return Number(num);
}
}
集合
- 数组实现
class Set {
constructor() {
this._data = [];
}
contains(e) {
return this._data.includes(e);
}
add(e) {
if (!this.contains(e)) {
this._data.push(e);
}
}
remove(e) {
let index = this._data.indexOf(e);
this._data.splice(index,1);
return this._data[index];
}
get length() {
return this._data.length;
}
get isEmpty() {
return this.length == 0;
}
}
export default Set;
- 链表实现
import LinkedList from "./LinkedList.js";
class Set {
constructor() {
this._data = new LinkedList();
}
contains(e) {
return this._data.contains(e);
}
add(e) {
if (!this.contains(e)) {
this._data.insertFirst(e);
}
}
remove(e) {
return this._data.removeElement(e);
}
get length() {
return this._data.length;
}
get isEmpty() {
return this.length == 0;
}
}
export default Set;
映射
| 插入数据量 | 双向链表映射 | 数组映射 | 二叉查找树 | js对象 |
|---|---|---|---|---|
| 3万 | 9.965秒 | 0.108秒 | 0.037秒 | 0.018秒 |
| 10万 | 33.22秒 | 0.247秒 | 0.064秒 | 0.043秒 |
}
**数组实现**
查找和插入 log2^n
```javascript
// key 最终以数字形式保存，目的是方便比较。如果key有用处于，可以在比较时再进行转换，但是这需要额外的成本
// 使用两个数组，1保存key,2保存value。
// 插入时使用二分法插入排序。插完元素后是有序的，key-value插入的位置在两个数组中也是一致的
// 因为key-value位置一致，所以用二分法找到key的索引，对应的就是value数组的索引
class ArrayMap {
constructor() {
this.keys = [];
this.values = [];
}
get size() {return this.keys.length;}
get isEmpty() {return this.keys.length === 0}
get(key) {
key = this._strToNum(key);
let i = this._search(key,0, this.size-1);
return i !== -1 ? this.values[i] : null;
}
put(key, value) {
key = this._strToNum(key);
let index = this._search(key,0,this.size-1);
if (index !== -1) {
this.values[index] = value;
} else {
let begin = 0;
let end = this.size-1;
let middle = Math.floor(end/2);
while (begin < end && this.keys[middle] != key) { // 二分排序法
if (this.keys[middle] > key) {
end = middle-1;
} else if (this.keys[middle] < key) {
begin = middle+1;
}
middle = Math.floor(begin+(end-begin)/2);
}
if (this.keys[middle] > key) { // 最后找到的中间值，只有两种结果
this.keys.splice(middle-1,0,key);
this.values.splice(middle-1,0,value);
} else {
this.keys.splice(middle+1,0,key);
this.values.splice(middle+1,0,value);
}
}
}
contains(key) {
key = this._strToNum(key);
return this._search(key,0, this.size-1) != -1;
}
delete(key) {
key = this._strToNum(key);
let i = this._search(key,0, this.size-1);
if (i!==-1) {
this.keys.splice(i,1);
return this.values.splice(i,1)[0];
} else {
return null
}
}
_strToNum(key) { // 这里将key转成数字类型，这样就可以使用二分查找了
if (typeof key !== "string") {throw("key need string type")}
let num = "";
for (let i=0; i<key.length; i++) {
num += String(key.charAt(i).charCodeAt());
}
return Number(num);
}
_search(key, begin, end) { // 二分查找
if (begin > end) {
return -1;
}
let middle = Math.floor(begin+(end-begin)/2);
if (key === this.keys[middle]) {
return middle;
} else if (key < this.keys[middle]) {
return this._search(key, begin, middle-1);
} else if (key > this.keys[middle]) {
return this._search(key, middle+1, end);
}
}
}
最大堆
从底部到顶部，O(log2^n）
// 数组从1开始计算，这样左子元素索引=2*k,右子元素=2*k+1;
// 如果从0开始计算，左子元素索引=2*k+1,右子元素=2*k+2;
// 插入时进行上浮操作，移到相应位置
// 弹出最大元素后再进行下沉操作，将现有最大元素排到顶部
class MaxHeap {
constructor() {
this.list = [-1];
}
get isEmpty() {return this.list.length-1 === 0}
get size() {return this.list.length-1}
get max() {
return this.list[1];
}
exch(k,p) {
let list = this.list;
let t = list[k];
list[k] = list[p];
list[p] = t;
}
// 上浮,大的往上走
swim() {
let k = this.size;
let p = Math.floor(k/2);
let list = this.list;
while (p != 0 && list[k] > list[p]) {
this.exch(k,p);
k = p;
p = Math.floor(k/2);
}
}
// 下沉，小的往小走
sink() {
let k = 1;
let list = this.list;
let left = 2*k;
let right = 2*k+1
while (left <= this.size) {
if (right <= this.size) {
if (list[left] > list[right] && list[k] < list[left]) {
this.exch(left,k);
k = left;
} else if (list[left] < list[right] && list[k] < list[right]) {
this.exch(right,k);
k = right;
} else {
break;
}
} else {
if (list[left] > list[k]) {
this.exch(left,k);
k = left;
}
}
left = 2*k;
right = 2*k+1
}
}
push(item) {
this.list.push(item);
this.swim();
}
pop() {
let ret = this.list[1];
this.list[1] = this.list[this.size];
this.list.splice(this.size,1);
this.sink();
return ret;
}
}
优先队列
import MaxHeap from "./MaxHeap.js";
class PriorityQueue {
constructor() {
this._data = new MaxHeap();
}
get length() {
return this._data.length;
}
get isEmpty() {
return this._data.isEmpty;
}
enqueue(e) {
this._data.add(e);
}
dequeue() {
return this._data.remove();
}
front() {
return this._data.get();
}
}
export default PriorityQueue;
前缀树
class Node {
constructor(isWord=false) {
this.isWord = isWord;
this.next = {};
}
}
class Trie {
constructor() {
this._root = new Node();
this._size = 0;
}
get size() {
return this._size;
}
add(word) {
let cur = this._root;
for (let i=0; i<word.length; i++) {
let key = word.charAt(i);
if (cur.next[key] == undefined) {
cur.next[key] = new Node();
}
cur = cur.next[key];
}
if (!cur.isWord) {
cur.isWord = true;
this._size++;
}
}
contains(word) {
let cur = this._root;
for(let i=0; i<word.length; i++) {
let key = word.charAt(i);
if (cur.next[key] == undefined) {
return false;
}
cur = cur.next[key];
}
return cur.isWord;
}
isPrefix(prefix) {
let cur = this._root;
for(let i=0; i<prefix.length; i++) {
let key = prefix.charAt(i);
if (cur.next[key] == undefined) {
return false;
}
cur = cur.next[key];
}
return true;
}
}
export default Trie;
并查集
class UnionFind {
constructor(size) { // size 集合数量
if (!size) {
throw new TypeError("size is empty");
}
this._parent = new Array(size);
this._rank = new Array(size); // 优先级
for (let i=0; i<this._parent.length; i++) {
this._parent[i] = i;
this._rank[i] = 1;
}
}
get size() {
return this._parent.length;
}
_find(p) { // 查找所属集合
if (p<0 && p>=parent.length) {
throw new RangeError(`${p} is invalid`);
}
while (p != this._parent[p]) {
this._parent[p] = this._parent[this._parent[p]];
p = this._parent[p];
}
return p;
}
isConnected(p, q) {
return this._find(p) == this._find(q);
}
unionElement(p, q) {
let pRoot = this._find(p);
let qRoot = this._find(q);
if (pRoot == qRoot) {
return;
}
if (this._rank[pRoot] < this._rank[qRoot]) { // 小的合并到大的集合
this._parent[pRoot] = qRoot;
} else if (this._rank[pRoot] > this._rank[qRoot]) {
this._parent[qRoot] = pRoot;
} else {
this._parent[qRoot] = pRoot;
this._rank[pRoot] += 1;
}
}
}
export default UnionFind;
哈希表
class HashTable {
constructor(capacity) {
if (!capacity) {
throw new RangeError("capacity is empty");
}
this._data = new Array(capacity);
this._size = 0;
for (let i=0; i<capacity; i++) {
this._data[i] = {}; // 冲突时保持到对象里
}
}
hashCode(key) { // 根据不同场景设计不同的哈希函数
let hash = 5381;
for (let i = 0; i < key.length; i++) {
hash = ((hash << 5) + hash) + key.charCodeAt(i);
}
return Math.abs(hash % this._data.length);
}
get size() {
return this._size;
}
add(key, value) {
let map = this._data[this.hashCode(key)];
if (map[key]) {
map[key] = value;
} else {
map[key] = value;
this._size++;
}
}
remove(key) {
let map = this._data[this.hashCode(key)];
let ret = map[key];
if (map[key]) {
delete map[key];
this._size--;
}
return ret;
}
get(key) {
return this._data[this.hashCode(key)][key];
}
set(key, value) {
let map = this._data[this.hashCode(key)];
if (!map[key]) {
throw new RangeError("key is not found");
}
map[key] = value;
}
contains(key) {
return !!(this.get(key));
}
}
export default HashTable;
图
// 邻接矩阵
class DenseGraph {
constructor(n, directed) {
this._n = n; // 点
this._m = 0; // 边
this._directed = directed; // 是否有向图
this._g = [];
for (let i = 0; i < n; i++) {
let arr = new Array(n).fill(false);
this._g.push(arr);
}
}
get V() { return this._n }
get E() { return this._m }
addEdge(v, w) {
if (this.hasEdge(v, w)) return;
this._g[v][w] = true;
if (!this._directed) {
this._g[w][v] = true;
}
this._m++;
}
hasEdge(v, w) {
if (v < 0 || v >= this._n) throw RangeError(v + " not exist");
if (w < 0 || w >= this._n) throw RangeError(w + " not exist");
return this._g[v][w];
}
DFS(v) { // 深度优先遍历
if (!this._g[0].includes(v)) {throw new RangeError(v+" is not exist")}
let visited = [];
let _this = this;
_dfs(v);
function _dfs(v) {
visited[v] = true;
console.log(v);
for (let i = v; i < _this._g.length; i++) {
for (let j = 0; j < _this._g[i].length; j++) {
if (_this._g[i][j] && !visited[j]) {
_dfs(j);
}
}
}
// 防止孤立的点没被遍历到
// for (let i = 0; i < _this._g.length; i++) {
// for (let j = 0; j < _this._g[i].length; j++) {
// if (_this._g[i][j] && !visited[j]) {
// _dfs(j);
// }
// }
// }
}
}
BFS(v) { // 广度优先遍历
if (!this._g[0].includes(v)) {throw new RangeError(v+" is not exist")}
let queue = [];
let visited = [];
let node;
queue.push(v);
while (queue.length) {
visited[v] = true;
node = queue.shift();
console.log(node);
for (let i=node; i<this._g.length; i++) {
for (let j=0; j<this._g[i].length; j++) {
if (this._g[i][j] && !visited[j]) {
queue.push(j);
visited[j] = true;
}
}
}
}
}
}
// 邻接表
class SparseGraph {
constructor(directed) {
this._n = []; // 点
this._edge = {};
this._m = 0; // 边
this._directed = directed; // 是否有向图
}
get V() { return this._n.length }
get E() { return this._m }
addEdge(v, w) {
if (!this._edge[v]) {
this._edge[v] = new Set();
this._n.push(v);
}
if (!this._edge[v].has(w)) {
this._edge[v].add(w);
this._m++;
}
if (!this._directed) {
if (!this._edge[w]) {
this._edge[w] = new Set();
this._n.push(w);
}
this._edge[w].add(v);
}
}
DFS(v) {
if (!this._edge[v]) {throw new RangeError(v+" is not exist")}
let visited = {};
let _this = this;
_dfs(v);
function _dfs(v) {
visited[v] = true;
console.log(v);
for (let key in _this._edge) {
_this._edge[key].forEach(item=>{
if (!visited[item]) {
_dfs(item);
visited[item] = true;
}
})
}
}
}
BFS(v) {
if (!this._edge[v]) {throw new RangeError(v+" is not exist")}
let visited = {};
let queue = [];
let node;
visited[v] = true;
queue.push(v);
while (queue.length) {
node = queue.shift();
console.log(node);
this._edge[node].forEach(item=>{
if (!visited[item]) {
queue.push(item);
visited[item] = true;
}
})
}
}
}
红黑树
// 前提
// 了解红黑树的性质,满足红黑树的性质就达到了平衡
// 了解插入时不满足红黑树性质进行的操作（颜色翻转、旋转操作)
const RED = true;
const BLACK = false;
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.left = null;
this.right = null;
this.color = RED;
}
}
class RBTree {
constructor() {
this.root = null;
this.size = 0;
}
get getsize() {
return this.size;
}
get isEmpty() {
return this.size == 0;
}
put(key, value) {
let _this = this;
this.root = put(this.root, this._strToNum(key), value);
this.root.color = BLACK;
function put(node, key, value) {
if (node == null) {
_this.size++;
//默认红色
return new Node(key, value);
}
if (key < node.key) {
node.left = put(node.left, key, value);
} else if (key > node.key) {
node.right = put(node.right, key, value);
} else {
node.value = value;
}
if (_this.isRed(node.right) && !_this.isRed(node.left)) {
node = _this.leftRotate(node);
}
if (_this.isRed(node.left) && _this.isRed(node.left.left)) {
node = _this.rightRotate(node);
}
if (_this.isRed(node.left) && _this.isRed(node.right)) {
_this.flipColors(node);
}
return node;
}
}
remove(key) {
let node = this.getNode(this.root, this._strToNum(key));
let _this = this;
if (node != null) {
this.root = remove(this.root, this._strToNum(key));
return node.value;
}
function remove(node, key) {
if (node == null) {
return null;
}
if (key < node.key) {
node.left = remove(node.left, key);
return node;
} else if (key > node.key) {
node.right = remove(node.right, key);
return node;
} else {
if (node.left == null) {
let rightNode = node.right;
node.right = null;
_this.size--;
return rightNode;
} else if (node.right == null) {
let leftNode = node.left;
node.left = null;
_this.size--;
return leftNode;
} else {
//待删除节点左右子树都不为空的情况
//调用minimum方法，寻找右子树中的最小节点
let successor = _this.minimum(node.right);
//removeMin操作中已经维护过size了
successor.right = _this.removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
}
return null;
}
get(key) {
let node = this.getNode(this.root, this._strToNum(key));
return node == null ? null : node.value;
}
contains(key) {
return this.getNode(this.root, this._strToNum(key)) != null;
}
// 前序遍历
preOrder() {
_preOrder(this.root);
function _preOrder(node) {
if (node == null) {
return;
}
console.log(node.value);
_preOrder(node.left);
_preOrder(node.right);
}
}
// 中序遍历
inOrder() {
_inOrder(this.root);
function _inOrder(node) {
if (node == null) {
return;
}
_inOrder(node.left);
console.log(node.value);
_inOrder(node.right);
}
}
// 后序序遍历
postOrder() {
_postOrder(this.root);
function _postOrder(node) {
if (node == null) {
return;
}
_postOrder(node.left);
_postOrder(node.right);
console.log(node.value);
}
}
// 层序遍历
levelOrder() {
let queue = []; // 引入队列
let node;
queue.push(this.root);
while (queue.length) {
node = queue.shift();
console.log(node.value);
if (node.left != null) {
queue.push(node.left);
}
if (node.right != null) {
queue.push(node.right);
}
}
}
// 左旋
leftRotate(node) {
let x = node.right;
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
// 右旋
rightRotate(node) {
let x = node.left;
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
// 颜色反转
flipColors(node) {
node.color = RED;
node.right.color = BLACK;
node.left.color = BLACK;
}
// 判断节点node的颜色
isRed(node) {
if (node == null) {
return BLACK;
}
return node.color;
}
_strToNum(key) { // 将字符串转成数字，方便比较大小
if (typeof key !== "string") { throw ("key need string type") }
let num = "";
for (let i = 0; i < key.length; i++) {
num += String(key.charAt(i).charCodeAt());
}
return Number(num);
}
minimum(node = this.root) {
if (this.size === 0) throw ("size 0");
return minimum(node);
function minimum(node) {
if (node.left == null) {
return node;
}
return minimum(node.left);
}
}
removeMin(node = this.root) {
let _this = this;
return removeMin(node);
function removeMin(node) {
if (node.left == null) {
let rightNode = node.right;
node.right = null;
_this.size--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
}
// 返回以node为根节点的二分搜索树中key所在的节点
getNode(node, key) {
if (node == null) {
return null;
}
if (key == node.key) {
return node;
} else if (key < node.key) {
return this.getNode(node.left, key);
} else {
return this.getNode(node.right, key);
}
}
}