우선순위큐

큐는 먼저 들어간 자료가 먼저 나오게되는 자료구조인데, 우선순위 큐는 큐에 들어가는 자료마다 우선순위가 있어서 우선순위가 높은 요소가 먼저 나가는 큐를 말한다.

힙

우선순위 큐를 구현하기 위한 방법 중 하나로, 이진트리 형태를 가지며, 요소가 삽입, 삭제될때마다 바로 정렬이 되는 특징이 있다.

우선순위가 높은 요소를 루트에 둔다. 참고로 단순히 수의 값을 우선순위라고 했을때, 숫자가 큰게 우선순위가 높으면 최대힙, 숫자가 낮은게 우선순위가 높으면 최소힙이라고 한다.

힙과 우선순위큐는 같은 말이 아니다.

힙 요소 삽입

힙의 구현 포인트는 요소가 추가될 때, 추가되는 요소가 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꿔준다는 것이다. 부모 정점이 우선순위가 더 높은 요소로 바뀌었다면, 다시 부모 정점의 부모 정점과 비교가 가능해질 것이고, 이 과정을 반복하면 O(logN)의 시간복잡도를 가지게 된다.

힙 요소 삭제

요소 제거는 루트 정점만 할 수 있다. 루트 정점을 제거하면 제일 마지막에 추가된 정점을 루트로 올리게 된다. 힙 요소 삽입의 역과정으로 루트 요소의 자식 요소들과 우선순위를 비교하여, 우선순위에 따라 부모 정점과 자식 정점을 바꿔준다. 이 과정을 삽입과 같이 반복하면 힙이 우선순위에 따라 정렬되게 된다.

힙구현

class MaxHeap {
  constructor() {
    this.heap = [null];
  }
  push(val) {
    this.heap.push(val);
    let currNode = this.heap.length - 1;
    let parentNode = Math.floor(currNode / 2);

    while (parentNode !== 0 && this.heap[parentNode] < val) {
      const temp = this.heap[parentNode];
      this.heap[parentNode] = val;
      this.heap[currNode] = temp;

      currNode = parentNode;
      parentNode = Math.floor(currNode / 2);
    }
  }

  pop() {
    const returnVal = this.heap[1];
    this.heap[1] = this.heap.pop();

    let currNode = 1;
    let leftNode = 2;
    let rightNode = 3;
    while (
      this.heap[currNode] < this.heap[leftNode] ||
      this.heap[currNode] < this.heap[rightNode]
    ) {
      if (this.heap[leftNode] < this.heap[rightNode]) {
        const temp = this.heap[currNode];
        this.heap[currNode] = this.heap[rightNode];
        this.heap[rightNode] = temp;
        currNode = rightNode;
      } else {
        const temp = this.heap[currNode];
        this.heap[currNode] = this.heap[leftNode];
        this.heap[leftNode] = temp;
        currNode = leftNode;
      }
      leftNode = currNode * 2;
      rightNode = currNode * 2 + 1;
    }
    return returnVal;
  }
}

class MinHeap {
  constructor() {
    this.heap = [null];
  }
  push(val) {
    this.heap.push(val);
    let currNode = this.heap.length - 1;
    let parentNode = Math.floor(currNode / 2);

    while (parentNode !== 0 && this.heap[parentNode] > val) {
      const temp = this.heap[parentNode];
      this.heap[parentNode] = val;
      this.heap[currNode] = temp;

      currNode = parentNode;
      parentNode = Math.floor(currNode / 2);
    }
  }

  pop() {
    const returnVal = this.heap[1];
    this.heap[1] = this.heap.pop();

    let currNode = 1;
    let leftNode = 2;
    let rightNode = 3;
    while (
      this.heap[currNode] > this.heap[leftNode] ||
      this.heap[currNode] > this.heap[rightNode]
    ) {
      if (this.heap[leftNode] > this.heap[rightNode]) {
        const temp = this.heap[currNode];
        this.heap[currNode] = this.heap[rightNode];
        this.heap[rightNode] = temp;
        currNode = rightNode;
      } else {
        const temp = this.heap[currNode];
        this.heap[currNode] = this.heap[leftNode];
        this.heap[leftNode] = temp;
        currNode = leftNode;
      }
      leftNode = currNode * 2;
      rightNode = currNode * 2 + 1;
    }
    return returnVal;
  }
}
const maxHeap = new MaxHeap();
maxHeap.push(1);
maxHeap.push(3);
maxHeap.push(10);
maxHeap.push(2);
maxHeap.push(4);
maxHeap.push(5);
maxHeap.push(8);
maxHeap.push(6);
maxHeap.push(9);
maxHeap.push(7);
console.log(maxHeap.heap);
//[null, 10, 9, 8, 6, 7, 3, 5, 1, 4, 2]
const maxArray = [];
maxArray.push(maxHeap.pop());
maxArray.push(maxHeap.pop());
maxArray.push(maxHeap.pop());
maxArray.push(maxHeap.pop());
maxArray.push(maxHeap.pop());
maxArray.push(maxHeap.pop());
maxArray.push(maxHeap.pop());
maxArray.push(maxHeap.pop());
maxArray.push(maxHeap.pop());
maxArray.push(maxHeap.pop());
console.log(maxArray);
//[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
const minHeap = new MinHeap();
minHeap.push(1);
minHeap.push(3);
minHeap.push(10);
minHeap.push(2);
minHeap.push(4);
minHeap.push(5);
minHeap.push(8);
minHeap.push(6);
minHeap.push(9);
minHeap.push(7);
console.log(minHeap.heap);
//[null, 1, 2, 5, 3, 4, 10, 8, 6, 9, 7]
const minArray = [];
minArray.push(minHeap.pop());
minArray.push(minHeap.pop());
minArray.push(minHeap.pop());
minArray.push(minHeap.pop());
minArray.push(minHeap.pop());
minArray.push(minHeap.pop());
minArray.push(minHeap.pop());
minArray.push(minHeap.pop());
minArray.push(minHeap.pop());
minArray.push(minHeap.pop());
console.log(minArray);
//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

트라이

자동완성이나 사전등을 만드는데 유용한 자료구조이다!
문자열을 키 값으로 가지는 트리를 만드는데, 루트 정점은 값을 비워놓고, 문자열의 맨 앞글자를 자식 정점으로, 그 자식 정점의 자식은 문자열의 맨 앞글자의 다음글자.... 이런식으로 트리가 구성이 된다.
ex) trie : t->tr->tri->trie

이렇게 정점을 구성해 놓고 정점의 값을 해쉬테이블의 키값으로 처리하면 아주 빠른속도로 원하는 값에 접근을 할 수 있는 원리이다!

단점은 각각의 단어마다 공간을 할당해줘야 하기 때문에 메모리를 많이 차지한다는점,,, 그래도 장점이 워낙 뚜렷하기에 현재 대부분 트라이를 쓰이고 있다고 한다!

트라이구현

class Node {
  constructor(val = "") {
    this.val = val;
    this.children = new Map();
  }
}

class Trie {
  constructor() {
    this.root = new Node();
  }

  insert(str) {
    let currNode = this.root;

    for (const char of str) {
      if (!currNode.children.has(char)) {
        currNode.children.set(char, new Node(currNode.val + char));
      }
      currNode = currNode.children.get(char);
    }
  }

  has(str) {
    let currNode = this.root;

    for (const char of str) {
      if (!currNode.children.has(char)) {
        return false;
      }
      currNode = currNode.children.get(char);
    }
    return true;
  }
}

const trie = new Trie();
trie.insert("tri");
trie.insert("try");
console.log(trie.has("tr")); //true
console.log(trie.has("tri")); //true
console.log(trie.has("try")); //true
console.log(trie.has("trr")); //false

Array.from(Array(n),()=>[]) vs Array(n).fill([])

언뜻보기에는 둘다 n 크기의 배열을 만들고 배열의 요소로 빈 배열을 할당하는것 같지만,

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/fill
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/from

위의 두 링크에 들어가서 유심히 살펴보면 fill메서드를 사용할경우 정적인 값, 즉, 하나의 배열 주소를 n개만큼 할당해서 사실 Array(n).fill([])로 만들어진 배열들은 사실 하나의 똑같은 배열들을 주욱 이어놓은거라는 사실을 오늘 알게되었다.

요즘 원래 살던것 보다 열심히 사느라 진땀 좀 뺍니다... 오늘은 여기까지,,,