Heap Sort / 힙정렬

문제

힙정렬은 최대힙 혹은 최소힙을 이용하는 정렬이다. 먼저 최대힙 혹은 최소힙을 만들어야 한다.

기본 개념

우선순위 큐

우선순위 개념을 큐에 도입한 자료구조. 즉 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나가는 자료구조이다. 스택, 큐, 우선순위 큐의 차이점은 아래와 같다.

자료구조	삭제되는 요소
스택 Stack	가장 최근에 들어온 데이터
큐 Queue	가장 먼저 들어온 데이터
우선순위 큐 Priority Queue	가장 우선순위가 높은 데이터

우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다. 그 중 힙으로 하는 것이 가장 효율적이다.

구현방식	삽입	삭제
순서 없는 배열	O(1)	O(n)
순서 없는 연결리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결리스트	O(n)	O(1)
힙	O(logn)	O(logn)

힙 Heap

힙이란? 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조. 완전이진트리란? 마지막 레벨을 제외하고 모든 노드가 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 왼쪽으로 채워져 있다. 마지막 레벨 h에서 $2^h - 1$개의 노드를 가질 수 있다. 힙은 일종의 느슨한 정렬 상태(반정렬상태)를 유지하고 있다. 부모 노드의 키 값이 자식 노드의 키 값보다 큰(작은) 이진트리라고 정의할 수 있겠다. 이진 탐색트리에서는 중복값을 허용하지 않지만 힙 트리에서는 허용한다.

힙의 구현

• 보통 배열을 사용한다.
• 쉬운 구현을 위해 배열의 첫 인덱스(0)는 사용하지 않는다.
• 특정 위치의 노드 번호는 변하지 않는다. 새로운 노드가 삽입되거나 노드가 삭제되어도 특정 노드의 번호는 변하지 않는다.
• 왼쪽 자식의 인덱스 = 부모 인덱스 _ 2 오른쪽 자식의 인덱스 = 부모 인덱스 _ 2 + 1 부모 인덱스 = (int) 자식 인덱스 / 2

Javascript를 이용한 힙의 구현

function swap(idx1, idx2, arr) {
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

function getParentIdx(idx) {
  return Math.floor(idx / 2);
}

function insert(heap, item) {
  heap.push(item);
  let itemIdx = heap.length - 1;
  let parentIdx = getParentIdx(itemIdx);
  while (heap[parentIdx] < heap[itemIdx]) {
    swap(itemIdx, parentIdx, heap);
    itemIdx = parentIdx;
    parentIdx = getParentIdx(itemIdx);
  }
  return heap;
}

const binaryHeap = function (arr) {
  return arr.reduce((heap, item) => {
    return insert(heap, item);
  },[Number.MAX_SAFE_INTEGER]).slice(1);
};

힙을 이용한 힙정렬

function removeRoot(heap) {
  let end = heap.length;
  while (end > 0) {
    swap(0, end - 1, heap); // 제일 작은 값이 제일 뒤로 간다.
    end--;
    let curIdx;
    let minIdx = 0;
    while (curIdx !== minIdx) {
      curIdx = minIdx;
      let left = curIdx * 2 + 1;
      let right = curIdx * 2 + 2;
      if (left < end && heap[left] < heap[minIdx]) {
        minIdx = left;
      }
      if (right < end && heap[right] < heap[minIdx]) {
        minIdx = right;
      }
      swap(minIdx, curIdx, heap);
    }
  }
  return heap;
}

const heapSort = function (arr) {
  let minHeap = binaryHeap(arr);
  return removeRoot(minHeap).reverse();
};