[Coding Test] Javascript stack, queue, heap

작성일 | In

Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Stack {
  constructor() {
    this._arr = [];
  }
  push(item) {
    this._arr.push(item);
  }
  pop() {
    return this._arr.pop();
  }
  peek() {
    return this._arr[this._arr.length - 1];
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop(); // 3

Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Queue {
  constructor() {
    this._arr = [];
  }
  enqueue(item) {
    this._arr.push(item);
  }
  dequeue() {
    return this._arr.shift();
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.dequeue(); // 1

Heap (조금 더 범용성있게 수정)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class BinaryHeap {
  constructor() {
    this.heap = [];
    this.key ='';
    this.count = 0;
  }

  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
    this.count++
  }
    
  getValue(obj){
      if (this.key == '') return obj
      return obj[this.key]
  }

  bubbleUp() {
    let currentIndex = this.heap.length - 1;

    while (currentIndex > 0) {
      let current = this.heap[currentIndex];
      let parentIndex = Math.floor((currentIndex - 1) / 2);
      let parent = this.heap[parentIndex];

      if (this.getValue(parent) >= this.getValue(current)) break;
      this.heap[currentIndex] = parent;
      this.heap[parentIndex] = current;
      currentIndex = parentIndex;
    }
  }

  extractMaxValue() {
    if (this.count === 0)
      return null
    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.sinkDown(0);
    this.count--;

    return max;
  }

  sinkDown(index) {
    let left = 2 * index + 1;
    let right = 2 * index + 2;
    let largest = index;
    const length = this.heap.length;

    if (left <= length && this.getValue(this.heap[left]) > this.getValue(this.heap[largest])) {
      largest = left;
    }
    if (right <= length && this.getValue(this.heap[right]) > this.getValue(this.heap[largest])) {
      largest = right;
    }
    // swap
    if (largest !== index) {
      [this.heap[index], this.heap[largest]] = [
        this.heap[largest],
        this.heap[index],
      ];

      this.sinkDown(largest);
    }
  }
}

const heap = new BinaryHeap()
heap.insert(5)
heap.insert(3)
console.log(heap.extractMaxValue())
console.log(heap.extractMaxValue())
console.log(heap.extractMaxValue())

Reference:
https://helloworldjavascript.net/pages/282-data-structures.html
https://jeongw00.tistory.com/172