[Algorithm] 우선순위 큐 - 힙

배열로 구현한 우선순위 큐의 비효율성에 따른 힙(Heap)을 이용한 우선순위 큐 구현

• 힙(Heap)은 하나의 자료구조이다. 이 때 우선순위 큐는 정확히 말해서 자료구조는 아니고, 우선순위를 두고 자료를 꺼내도록 구현하는 기능상의 정의라고 생각하면 될 것 같다.
• 힙의 특징 :
  1. 반드시 부모요소가 자식요소보다 작거나 같은 값을 가지고 있어야한다.
  2. 완전 이진트리로, 높이 0에서부터 왼쪽부터 차례로 자료를 채워나간다. 따라서, 오른쪽 자식 노드가 있는데, 왼쪽 자식노드가 없는 경우는 존재하지 않는다.
  **자식 노드가 단 두개로 이루어져있는 '이진트리'에 왼쪽부터 차례로 자료를 채우는 속성이 추가되어 완전 이진트리가 되는 것
  3. 부모일수록 우선순위가 높다. 따라서 pop을 하면 root요소가 pop된다.
  4. 힙의 높이는 0부터 시작한다는 관점에서 log2N(밑을 2로하는) 이다. 여기서 N은 전체 노드의 개수이다. 즉, 전체 노드의 개수가 8개면 이 힙은 높이 3을 가진 완전 이진트리가 되는 것이다. 예를 들어, 아래와 같은 이진트리는 높이가 2인 이진트리라고 할 수 있다(0부터 시작한다 했을 때).
  출처 : 블로그 링크
  5. 힙의 '삽입'에는 logN의 시간복잡도가 걸린다. 이유는 삽입시에는 완전 이진트리의 속성에 맞게 왼쪽부터 차례로 봤을 때 가장 마지막에 빈 부분부터 채워넣는데, 예를 들어, 위의 그림에서는 6의 오른쪽 자식요소로 채워넣게 될 것이다. 그러나, 만약에 채워넣는 수가 2라고 하면, 힙의 특성상 부모요소는 무조건 자식요소보다 작아야하기 때문에 만약 채워넣은 수가 부모요소보다 작으면 둘을 교환해줘야 한다(이 때, 왼쪽 자식 노드는 이미 부모요소보다 작은 것이 확정이므로 새로 넣은 요소와는 비교해볼 필요가 없다).
  6. 그렇게 교환을 했다면? 또 다시, 그 부모요소와 비교를 해야한다. 이런식으로 결국 root 요소까지 비교를 해나갈텐데 그 시행 회수가 최악의 경우 높이만큼 이뤄지므로 logN의 시간복잡도를 가지는 것이다.
  7. 삽입에 이어 삭제 또한 logN의 시간복잡도를 가진다. 힙의 삭제는 먼저 루트노드부터 삭제를 하게되는데, 이 때, 삭제하고 끝이 아니라 힙의 속성에 맞게 재배열하는 과정을 거쳐야한다. 그전에 맨끝요소를 루트노드에 넣고, 재배열을 하는데, 맨 아래 요소까지 새로 바뀐 루트노드와의 비교 과정이 필요하기 때문에 결국 높이만큼의 시간복잡도가 걸리는 것이다.
  8. top() 메서드는 굉장히(조회) 쉽다. 단지 root 노드를 출력해주기만 하면 된다.

특성을 바탕으로 실제 구현해본 힙(Heap) - push, pop, top

• push 메서드

• pop 메서드 (push보다 복잡한 로직이 필요함)

  
  > const pop = () => {
    [heap[1],heap[heap.length-1]] = [heap[heap.length-1],heap[1]]
    heap.pop();
  
    let idx = 1;
    let left = undefined;
    let right = undefined;
    let std = undefined;
  
    let height = Math.floor(Math.log2(heap.length-1));
    let cnt = 0;
    while (true) {
      cnt += 1
      std = heap[idx];
      idx *= 2;
      left = heap[idx];
      right = heap[idx+1];
      if (left && right) {
        if (left < right && std > left) {
          [heap[idx/2],heap[idx]] = [heap[idx],heap[idx/2]];
        } else if (right<=left && std>right) {
          [heap[idx/2],heap[idx+1]] = [heap[idx+1],heap[idx/2]];
        } else {
          break;
        }
      } else if (left && !right) {
        if (std>left) {
          [heap[idx/2],heap[idx]] = [heap[idx],heap[idx/2]];
        } else {
          break;
        }
      } else {
        break;
      }
      idx += 1;
      if (cnt === height) {
        break;
      } 
    }
  }
  
  

• 매우 간단한 top메서드

• 위에서 구현을 할 때 특별히 알아둘 부분은 heap을 만들 때 배열을 이용했지만, 그 배열의 인덱스의 0은 비워놓는다는 점이다. 이는 힙의 특성상 노드의 개수가 2의 배수 단위로 증가할 때마다 높이가 한칸씩 +되는 것을 이용해 pop이나 push를 할 때 직계 부모요소 혹은 직계 자식 요소의 인덱스를 쉽게 구하려고 나누기 2를 하거나(부모요소), 곱하기 2를 해주는(자식 요소) 부분과 관련이 있다.

• 무슨 말인가 하면, 예를 들어, [2,3,5,4,6,7]

         2
     3      5
   4   6  7
  

  위와 같은 힙이 있다고 했을 때,
  배열로 표현한 힙의 인덱스 0을 0으로 그냥 비워두면,
  [0,2,3,5,4,6,7]이 되는데,
  그러면 예를 들어, 인덱스 7에 새로운 요소를 예를 들어, 8을 넣는다고 했을 때, 8이 그 부모요소보다 작은지 큰지를 비교하기 위해
  코드상에서 부모요소의 인덱스를 구할 수 있어야한다(할 때마다 탐색을 할 수는 없다..). 그 방법으로 새로 넣는 요소의 인덱스(이 경우에는 7)에 2를 나눠주면 7//2 = 3 => 인덱스 3의 값은 5로 맨 아래의 7의 오른쪽 노드로 8이 들어간다 했을 때 정확히 그의 부모요소는 5가 되는 것을 알 수 있다. 그러나, 인덱스 0을 0으로 비워놓지 않으면 이 계산이 통하지 않음을 알 수 있다. 역으로 pop을 할 때는 자식요소와 비교를 하는 것이 필요한데, 그 때는 부모요소의 인덱스에 2를 곱해주거나(왼쪽 자식 노드의 인덱스), 2를 곱한 다음에 1을 더해주면(오른쪽 자식 노드의 인덱스) 원하는 값을 얻을 수 있다.

• 실제로.. 이전에 배열로 만든 우선순위 큐와 for문으로 100000번의 push, pop을 시행하여(똑같은 조건으로) 비교해보니 실제 걸리는 시간 자체도 확연히 차이가 난다(시간복잡도 O(N)과 O(logN)의 차이는 어마무시하다는 것..) .