- JavaScript Algorithms and Data Structures Masterclass(Udemy Course)

힙 : 트리의 하위 자료 구조 중 하나

최대 힙 : 부모 노드가 자식 노드보다 큰 힙

최소 힙 : 부모 노드가 자식 노드보다 작은 힙

이진 힙은 '우선순위 큐'를 구현하거나, 그래프를 순회하는데 사용된다.

• 이진 힙은 이진 검색 트리와는 달리 left, right 포인터가 아닌 list를 사용한다.

• list에 최상위 노드부터 추가하는 형식이므로, 부모 자식간의 인덱스 관계는 위와 같이 표현된다.

이진 최대 힙

이진 최대 힙의 프로퍼티는 리스트 하나이다.

const MaxBinaryHeap = {
  init: function () {
    this.values = [];
  },
};

const mbh = Object.create(MaxBinaryHeap);
mbh.init();

insert

1. push로 밀어 넣는다.

2. 부모 자식 간의 인덱스 관계를 고려하여 올바른 위치로 재정렬한다.

const MaxBinaryHeap = {
  init: function () {
    this.values = [41, 39, 33, 18, 27, 12];
  },
  insert: function (val) {
    this.values.push(val);

    let indexOfInserted = this.values.length - 1;

    while (indexOfInserted > 0) {
      let indexOfParent = Math.floor((indexOfInserted - 1) / 2);

      const parentVal = this.values[indexOfParent];

      if (parentVal < val) {
        this.values[indexOfParent] = val;
        this.values[indexOfInserted] = parentVal;
        indexOfInserted = indexOfParent;
        debugger;
        continue;
      }
      break;
    }
    return this.values;
  },
};

const mbh = Object.create(MaxBinaryHeap);
mbh.init();

mbh.insert(55);

• 시간복잡도는 log n

extractMax

1. 가장 최근에 추가된 원소를 최대값으로 대체한다.

2. 최대 힙 규칙에 맞게 위치를 재정렬한다(삼투)

const MaxBinaryHeap = {
  // 생략
  extractMax: function () {
    if (this.values.length == 0) {
      return;
    }
    const max = this.values.shift();
    const lastItem = this.values.pop();
    if (!lastItem) {
      debugger;
      return max;
    }
    this.values.unshift(lastItem);

    let indexOfTarget = 0;

    while (true) {
      const idxOfLeftChild = indexOfTarget * 2 + 1;
      const idxOfRightChild = indexOfTarget * 2 + 2;
      const leftChild = this.values[idxOfLeftChild];
      const rightChild = this.values[idxOfRightChild];

      function swap(direction) {
        const child = direction == "left" ? leftChild : rightChild;
        const idxOfChild =
          direction == "left" ? idxOfLeftChild : idxOfRightChild;
        this.values[indexOfTarget] = child;
        this.values[idxOfChild] = lastItem;
        indexOfTarget = idxOfChild;
      }

      // 자식이 하나도 없을 때
      if (!leftChild) {
        // 힙이 배열임을 감안했을 때, 자식이 없는 노드에 추가되는 자식은 항상 왼쪽 자식이 먼저이다.
        // 왼쪽 자식이 없다는 것은 오른쪽 자식도 없다는 것이므로 더 이상 내려갈 수 없다는 것
        debugger;
        return max;
      }

      // 오른쪽 자식이 없을 때
      if (!rightChild) {
        if (leftChild > lastItem) {
          swap.call(this, "left");
          debugger;
          continue;
        }
        debugger;
        return max;
      }

      // 두 자식이 모두 있을 때 && 두 자식의 값이 같을 때
      // 최대 힙의 구조상 bubbleDown되는 자식이 어디서 올라왔건
      // 두 자식보다 모두 클 수는 없다.
      // 그런데 두 자식의 값이 같다는 것은 bubbleDown되는 자식이
      // 두 자식보다 작다는 것을 의미
      // 그러니 왼쪽이든 오른쪽이든 내려가야 한다.
      if (leftChild == rightChild) {
        swap.call(this, "left");
        debugger;
        continue;
      }

      //두 자식이 모두 있을 때 && 오른쪽으로 스왑해야 할 때
      if (leftChild < rightChild && rightChild > lastItem) {
        // 오른쪽 자식이 존재하면서 오른쪽 자식이 왼쪽 자식보다 큰 경우,
        // 그리고 그 오른쪽 자식이 lastItem보다 큰 경우 오른쪽으로 스왑한다.
        swap.call(this, "right");
        debugger;
        continue;
      }

      //두 자식이 모두 있을 때 && 왼쪽으로 스왑해야 할 때
      if (leftChild > rightChild && leftChild > lastItem) {
        swap.call(this, "left");
        debugger;
        continue;
      }
    }
  },
};

const mbh = Object.create(MaxBinaryHeap);
mbh.init();

• 이 경우의 시간복잡도 역시 log n

전체 코드

const MaxBinaryHeap = {
  init: function () {
    this.values = [41, 39, 33, 18, 27, 12];
  },
  insert: function (val) {
    this.values.push(val);

    let indexOfInserted = this.values.length - 1;

    while (indexOfInserted > 0) {
      let indexOfParent = Math.floor((indexOfInserted - 1) / 2);

      const parentVal = this.values[indexOfParent];

      if (parentVal < val) {
        this.values[indexOfParent] = val;
        this.values[indexOfInserted] = parentVal;
        indexOfInserted = indexOfParent;
        debugger;
        continue;
      }
      break;
    }
    return this.values;
  },
  extractMax: function () {
    if (this.values.length == 0) {
      return;
    }
    const max = this.values.shift();
    const lastItem = this.values.pop();
    if (!lastItem) {
      debugger;
      return max;
    }
    this.values.unshift(lastItem);

    let indexOfTarget = 0;

    while (true) {
      const idxOfLeftChild = indexOfTarget * 2 + 1;
      const idxOfRightChild = indexOfTarget * 2 + 2;
      const leftChild = this.values[idxOfLeftChild];
      const rightChild = this.values[idxOfRightChild];

      function swap(direction) {
        const child = direction == "left" ? leftChild : rightChild;
        const idxOfChild =
          direction == "left" ? idxOfLeftChild : idxOfRightChild;
        this.values[indexOfTarget] = child;
        this.values[idxOfChild] = lastItem;
        indexOfTarget = idxOfChild;
      }

      // 자식이 하나도 없을 때
      if (!leftChild) {
        // 힙이 배열임을 감안했을 때, 자식이 없는 노드에 추가되는 자식은 항상 왼쪽 자식이 먼저이다.
        // 왼쪽 자식이 없다는 것은 오른쪽 자식도 없다는 것이므로 더 이상 내려갈 수 없다는 것
        debugger;
        return max;
      }

      // 오른쪽 자식이 없을 때
      if (!rightChild) {
        if (leftChild > lastItem) {
          swap.call(this, "left");
          debugger;
          continue;
        }
        debugger;
        return max;
      }

      // 두 자식이 모두 있을 때 && 두 자식의 값이 같을 때
      // 최대 힙의 구조상 bubbleDown되는 자식이 어디서 올라왔건
      // 두 자식보다 모두 클 수는 없다.
      // 그런데 두 자식의 값이 같다는 것은 bubbleDown되는 자식이
      // 두 자식보다 작다는 것을 의미
      // 그러니 왼쪽이든 오른쪽이든 내려가야 한다.
      if (leftChild == rightChild) {
        swap.call(this, "left");
        debugger;
        continue;
      }

      //두 자식이 모두 있을 때 && 오른쪽으로 스왑해야 할 때
      if (leftChild < rightChild && rightChild > lastItem) {
        // 오른쪽 자식이 존재하면서 오른쪽 자식이 왼쪽 자식보다 큰 경우,
        // 그리고 그 오른쪽 자식이 lastItem보다 큰 경우 오른쪽으로 스왑한다.
        swap.call(this, "right");
        debugger;
        continue;
      }

      //두 자식이 모두 있을 때 && 왼쪽으로 스왑해야 할 때
      if (leftChild > rightChild && leftChild > lastItem) {
        swap.call(this, "left");
        debugger;
        continue;
      }
    }
  },
};

const mbh = Object.create(MaxBinaryHeap);
mbh.init();

우선순위 큐

• 각각의 원소가 우선순위를 갖는 자료구조이다.

• 일반적으로 숫자가 작을수록 우선순위가 높다고 간주하기 때문에 최소 힙으로 구현한다.

각각의 원소는 우선순위를 갖는다.

const Node = {
  init: function (val, priority) {
    this.val = val;
    this.priority = priority;
  },
};

• 우선순위를 기준으로 동작하기 때문에 값이 중요한 것이 아니다.

전체 코드

const Node = {
  init: function (val, priority) {
    this.val = val;
    this.priority = priority;
  },
};

const PriorityQueue = {
  init: function () {
    this.values = [];
  },
  enqueue: function (val, priority) {
    const newNode = Object.create(Node);
    newNode.init(val, priority);

    this.values.push(newNode);

    let idxOfNewNode = this.values.length - 1;

    while (idxOfNewNode > 0) {
      const idxOfParentNode = Math.floor((idxOfNewNode - 1) / 2);

      const parentNode = this.values[idxOfParentNode];

      if (priority < parentNode.priority) {
        this.values[idxOfParentNode] = newNode;
        this.values[idxOfNewNode] = parentNode;
        idxOfNewNode = idxOfParentNode;
        debugger;
        continue;
      }
      break;
    }
    return this.values;
  },
  dequeue: function () {
    if (this.values.length == 0) {
      return;
    }
    const dequeued = this.values.shift();
    const lastItem = this.values.pop();
    if (!lastItem) {
      debugger;
      return dequeued;
    }
    this.values.unshift(lastItem);

    let idxOfTarget = 0;

    while (true) {
      let idxOfLeftChild = idxOfTarget * 2 + 1;
      let idxOfRightChild = idxOfTarget * 2 + 2;
      let leftChild = this.values[idxOfLeftChild];
      let rightChild = this.values[idxOfRightChild];

      function swap(direction) {
        const idxOfChild =
          direction == "left" ? idxOfLeftChild : idxOfRightChild;
        const child = direction == "left" ? leftChild : rightChild;
        this.values[idxOfChild] = this.values[idxOfTarget];
        this.values[idxOfTarget] = child;
        idxOfTarget = idxOfChild;
      }

      // 자식이 없을 때
      if (!leftChild) {
        // 자식이 추가될 때는 왼쪽 자식부터 추가되는 힙의 구조상 왼쪽 자식이 없다는 건,
        // 오른쪽 자식도 없다는 것이다.
        // 따라서 더 이상 내려갈 수 없다.
        debugger;
        return dequeued;
      }

      // 오른쪽 자식이 없을 때
      if (!rightChild) {
        if (leftChild.priority < lastItem.priority) {
          swap.call(this, "left");
          debugger;
          continue;
        }
        debugger;
        return dequeued;
      }

      // 두 자식이 모두 존재하면서, 두 자식의 우선순위가 같을 때
      // 최소 힙의 구조상 bubbleDown되는 노드가 어느 쪽에서 올라왔든,
      // 두 자식 모두의 우선순위보다 높을(작을) 수는 없다
      // 그런데 두 자식의 우선순위가 같다는 것은,
      // bubbleDown되는 노드의 우선순위가 두 자식의 우선순위보다 낮다는(크다는) 것이므로,
      // 왼쪽이든 오른쪽이든 내려가야 한다.
      if (leftChild.priority == rightChild.priority) {
        swap.call(this, "left");
        debugger;
        continue;
      }

      if (
        leftChild.priority < rightChild.priority &&
        leftChild.priority < lastItem.priority
      ) {
        // 두 자식이 모두 존재할 때 && 왼쪽으로 swap할 때
        swap.call(this, "left");
        debugger;
        continue;
      }

      // 두 자식이 모두 존재할 때 && 오른쪽으로 swap할 때
      if (
        rightChild.priority < leftChild.priority &&
        rightChild.priority < lastItem.priority
      ) {
        swap.call(this, "right");
        debugger;
        continue;
      }
    }
  },
};

const pq = Object.create(PriorityQueue);
pq.init();

pq.enqueue("가벼운 감기", 5);
pq.enqueue("총상", 1);
pq.enqueue("고열", 4);
pq.enqueue("전치 3주", 2);
pq.enqueue("팔 골절", 3);

결론

• 삽입 및 삭제의 시간복잡도는 log n

• 탐색의 시간 복잡도는 n

• 힙을 이용한 정렬은 n * log n
  (삭제를 n번 해주면 되므로)