힙 정렬과 우선순위 큐

오늘은 힙 정렬(Heap Sort)과 우선순위 큐(Priority Queue)에 관해 써보려 한다. 힙 정렬과 우선순위 큐를 알기 전 힙(Heap)에 대해 먼저 알 필요가 있다.

힙(Heap)

힙을 알기 전 이진 트리(Binary Tree) 개념을 먼저 짚어보겠다. 이진 트리는 데이터를 표현할 때, 데이터를 각 노드에 담은 뒤 그 노드를 2개씩 이어 붙이는 구조를 뜻한다. 이때 트리 구조에 맞춰 부모노드에서 자식노드로 가지가 뻗혀나간다. 위 그림과 같이 모든 노드의 자식노드가 2개 이하인 구조다.

완전 이진 트리(Complete Binary Tree)는 제일 위인 루트(Root)부터 시작해 자식노드가 왼쪽, 오른쪽 순으로 차근히 들어가는 구조다. 완전 이진 트리는 노드가 중간에 비어있지 않고 위에서부터 빽빽히 가득 찬 구조이며 항상 왼쪽 자식노드부터 데이터가 들어간다.

힙(Heap)은 최소값, 최대값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리 구조이다. 힙은 최대 힙과 최소 힙이 존재한다.

• 최대 힙: 부모 노드가 자식 노드보다 노드 값이 크다.
• 최소 힙: 부모 노드가 자식 노드보다 노드 값이 작다.

힙 정렬(Heap Sort)

모든 트리가 최대 힙 혹은 최소 힙 구조를 가지도록 정렬하는 것을 힙 정렬이라 부른다. 힙 정렬을 수행하기 위해서는 힙 생성 알고리즘(Heapify Algorithm)을 사용한다.

최대 힙 생성 알고리즘은 기준을 삼은 노드의 두 자식노드 중 더 큰 자식과 자신을 비교했을 때, 자식노드가 더 크다면 서로 위치를 바꾸는 알고리즘이다. 최소 힙 생성 알고리즘은 반대로 자식노드 중 더 작은 자식과 자신을 비교해, 자식노드가 더 작다면 위치를 바꾸면 된다. 위치를 바꾼 뒤에도 최대 힙, 최소 힙을 만족하지 않는다면 만족할 때까지 반복한다.

힙 구조를 만족한 뒤, 루트 노드를 맨 마지막 노드와 스위치한 후 바뀐 루트 노드가 힙 구조를 만족하는지 확인한다. 이후 새로운 루트 노드를 마지막 직전 노드와 스위치하고, 바뀐 루트 노드가 또다시 힙 구조를 만족하는지 확인한다.

이 모든 과정을 마친 힙 정렬의 전체 시간 복잡도는 O(N * logN)이다.

코드

// 최대 힙 정렬, Bottom-Up 방식

function maxHeapify(arr, n) {
  for (let i = 1; i < n; i++) {
    let c = i;

    do {
      const root = parseInt((c - 1) / 2);
      if (arr[root] < arr[c]) {
        const tmp = arr[root];
        arr[root] = arr[c];
        arr[c] = tmp;
      }
      c = root;
    } while (c !== 0);
  }

  for (let i = n - 1; i > 0; i--) {
    let tmp = arr[0];
    arr[0] = arr[i];
    arr[i] = tmp;

    let root = 0;
    let c = 0;

    do {
      c = 2 * root + 1;

      if (c < i - 1 && arr[c] < arr[c + 1]) c++;

      if (c < i && arr[root] < arr[c]) {
        tmp = arr[root];
        arr[root] = arr[c];
        arr[c] = tmp;
      }

      root = c;
    } while (c < i);
  }

  return arr;
}

const arr = [7, 6, 5, 8, 3, 5, 9, 1, 6];
console.log(maxHeapify(arr, 9));

// 최소 힙 정렬, Bottom-Up 방식

function minHeapify(arr, n) {
  for (let i = 1; i < n; i++) {
    let c = i;
    do {
      const root = parseInt((c - 1) / 2);
      if (arr[root] > arr[c]) {
        const tmp = arr[root];
        arr[root] = arr[c];
        arr[c] = tmp;
      }
      c = root;
    } while (c !== 0);
  }

  for (let i = n - 1; i > 0; i--) {
    let tmp = arr[0];
    arr[0] = arr[i];
    arr[i] = tmp;

    let root = 0;
    let c = 0;

    do {
      c = 2 * root + 1;

      if (c < i - 1 && arr[c] > arr[c + 1]) c++;

      if (c < i && arr[root] > arr[c]) {
        tmp = arr[root];
        arr[root] = arr[c];
        arr[c] = tmp;
      }

      root = c;
    } while (c < i);
  }

  return arr;
}

const arr = [7, 6, 5, 8, 3, 5, 9, 1, 6];
console.log(minHeapify(arr, 9));

우선순위 큐(Priority Queue)

일반적인 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 구조인 선입선출(FIFO) 구조이다. 우선순위 큐는 기존의 큐와 다르게 우선순위를 기준으로 삭제한다. 만약 우선순위가 같다면 큐에 들어간 시점을 기준으로 삭제한다. 배열, 연결리스트, 힙 기반으로 구현할 수 있으며 각각의 시간복잡도가 다르다. 가장 효율적인 방법은 힙 기반 구현이다.

시간복잡도

배열, 연결리스트 기반

• 삽입: O(n)
• 삭제: O(1)

힙 기반

• 삽입: O(logN)
• 삭제: O(logN)

자바스크립트는 다른 언어와 달리 우선순위 큐가 구현되어 있지 않다. 아래 코드는 Myungho님 velog에서 참고한 것이다.

코드

// 우선순위 큐에 삽입되는 데이터 클래스
class QElement {
  constructor(element, priority) {
    this.element = element;
    this.priority = priority;
  }
}

// 우선순위 큐
class PriorityQueue {
  constructor() {
    this.queue = [];
  }
}

// 데이터의 우선순위에 따라 큐의 적절한 위치에 삽입
enqueue(element, priority) {
  // QElement 객체 생성
  const qElement = new QElement(element, priority);
  let isContain = false;
  
  // 전체 데이터를 순회하면서 자신의 우선순위가 더 높은 위치를  탐색
  // splice 함수는 배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경
  // array.splice(startIndex, deleteCount, item1, item2, ...)
  for(let i=0, j=this.queue.length; i<j; i++) {
    if(this.queue[i].priority < element.priority) {
      this.queue.splice(i, 0, qElement);
      isContain = true;
      break;
    }
  }
  
  // 큐에 자신보다 더 낮은 우선순위를 가진 요소가 없을 때, 큐의 맨 마지막에 삽입
  if(!isContain) {
    this.queue.push(qElement);
  }
}

dequeue() {
  // 큐가 비어있을 때는 오류를 발생시킨다.
  // 비어있지 않다면 첫번째 요소를 삭제하고 반환한다.
  if(this.queue.length === 0) {
    return new Error("우선순위 큐에 데이터가 없습니다.");
  }
  return this.queue.shift();
}

front() {
  // 큐가 비어있을 때는 오류를 발생시킨다.
  // 비어있지 않다면 첫번째 요소를 반환한다.
  if(this.queue.length === 0) {
    return new Error("우선순위 큐에 데이터가 없습니다.");
  }
  return this.queue[0];
}

rear() {
  // 큐가 비어있을 때는 오류를 발생시킨다.
  // 비어있지 않다면 마지막 요소를 반환한다.
  if(this.queue.length === 0) {
    return new Error("우선순위 큐에 데이터가 없습니다.");
  }
  return this.queue[this.queue.length-1];
}

isEmpty() {
  // 큐의 길이를 0과 비교하여 큐가 비어있는지 반환한다.
  return this.queue.length === 0;
}

print() {
  // ES6 Array.forEach 메소드로 큐를 순회하면서 문자열을 만들어낸다.
  let str = "";
  this.queue.forEach(item => str += item.element + " ");
  return str;
}

--

참고

• 10. 힙 정렬(Heap Sort)_안경잡이개발자님 블로그
• 자바스크립트로 우선순위 큐 구현하기_Myungho님 Velog