数据结构

# 数据结构

# 集合

// 去重
const arr1 = [1, 1, 2, 3];
const arr2 = [...new Set(arr1)];

// 判断元素是否在集合中
const set = new Set(arr);
const has = set.has(3);

// 求交集
const set2 = new Set([2, 3]);
const set3 = new Set([...set].filter((item) => set2.has(item)));

// add
set.add(elem);

// delete
set.delete(elem);

# 字典

// 唯一值数据结构
const m = new Map();

// 增
m.set("a", "aa");
m.set("b", "bb");

// 删
m.delete("b");
m.clear();

// 改
m.set("a", "aaa");

#

# 深度优先遍历(DFS)

// 1. 访问根节点
// 2. 对根节点的children挨个进行深度优先遍历
const dfs = (root) => {
  console.log(root.value);
  root.children.forEach((child) => dfs(child));
};

# 广度优先遍历(BFS)

// 1. 新建一个队列,把根节点入队
// 2. 把对头出队并访问
// 3. 把对头的children挨个入队
// 4. 重复2、3步,直到队列为空
const bfs = (root) => {
  const q = [root];
  while (q.length) {
    const n = q.shift();
    console.log(n.value);
    n.children.forEach((child) => q.push(child));
  }
};

# 先序遍历(根左右)

// 递归版
const preorder = (root) => {
  if (!root) {
    return;
  }
  console.log(root.value);
  preorder(root.left);
  preorder(root.right);
};

// 非递归版
const preorder = (root) => {
  if (!root) {
    return;
  }
  const stack = [root];
  while (stack.length) {
    const n = stack.pop();
    console.log(n.value);
    if (n.right) stack.push(n.right);
    if (n.left) stack.push(n.left);
  }
};

# 中序遍历(左根右)

// 递归版
const inorder = (root) => {
  if (!root) {
    return;
  }
  inorder(root.left);
  console.log(root.value);
  inorder(root.right);
};

// 非递归版
const inorder = (root) => {
  if (!root) {
    return;
  }
  const stack = [];
  let p = root;
  while (stack.length || p) {
    while (p) {
      stack.push(p);
      p = p.left;
    }
    const n = stack.pop();
    console.log(n.val);
    p = n.right;
  }
};

# 后序遍历(左右根)

// 递归版
const postorder = (root) => {
  if (!root) {
    return;
  }
  postorder(root.left);
  postorder(root.right);
  console.log(root.value);
};

// 非递归版
// 用一个栈存储先序遍历的改版(根右左)
// 再将这个栈逆序输出
const postorder = (root) => {
  if (!root) {
    return;
  }
  const outputStack = [];
  const stack = [root];
  while (stack.length) {
    const n = stack.pop();
    outputStack.push(n);
    if (n.left) stack.push(n.left);
    if (n.right) stack.push(n.right);
  }
  while (outputStack.length) {
    const n = outputStack.pop();
    console.log(n.value);
  }
};

#

class MinHeap {
  constructor(){
    this.heap = []
  }

  swap(i1, i2) {
    [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]
  }

  getParentIndex(i) {
    return (i - 1) >> 1
  }

  getLeftIndex(i) {
    return i * 2 + 1
  }

  getRightIndex(i) {
    return i * 2 + 2
  }

  shiftUp(index) {
    if(index == 0) return
    const parentIndex = this.getParentIndex(index)
    if(this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index)
      this.shiftUp(parentIndex)
    }
  }

  shiftDown(index) {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if(this.heap[leftIndex] < this.heap[index]) {
      this.swap(leftIndex, index)
      this.shiftDown(leftIndex)
    }
    if(this.heap[rightIndex] < this.heap[index]) {
      this.swap(rightIndex, index)
      this.shiftDown(rightIndex)
    }
  }

  // 插入元素,要保证小顶堆特性
  // 如果该元素小于父元素,则需要将该元素和父元素对换,直至堆顶
  insert(value) {
    this.heap.push(value)
    this.shiftUp(this.heap.length - 1);
  }

  // 删除堆顶
  // 用数组尾部元素替换堆顶(直接删除堆顶会破坏堆结构)
  // 然后下移:将新堆顶和它的子节点进行交换,直到子节点大于等于这个新堆顶
  pop() {
    this.heap[0] = this.heap.pop()
    this.shiftDown(0)
  }

  // 获取堆顶
  peek() {
    return this.heap[0]
  }

  size() {
    return this.heap.length
  }
}